一、欧几里得算法的严格证明
设a，b是任意两个正整数。记r
-2
= a，r
-1
= b，反复运用带余除法，有
r
-2
= q
0
r
-1
+ r
0
, 0 ≤ r
0
< r
-1
r
-1
= q
1
r
0
+ r
1
, 0 ≤ r
1
< r
0
r
0
= q
2
r
1
+ r
2
, 0 ≤ r
2
< r
1
…
r
n-3
= q
n-1
r
n-2
+ r
n-1
, 0 ≤ r
n-1
< r
n-2
r
n-2
= q
n
r
n-1
+ r
n
, 0 ≤ r
n
< r
n-1
r
n-1
= q
n+1
r
n
+ r
n+1
, r
n+1
= 0
随着n的增加，r
n
减小，由于r
n+1
≥ 0，因此，r
n+1
= 0。
上述过程即从数列r
-2
，r
-1
，r
0
，…，r
n
前两项依次求出第三项，直到最后一项的过程。有（a，b）=（r
-2
，r
-1
）=（r
-1
，r
0
）= … =（r
n-1
，r
n
）=（r
n
，r
n+1
）=（r
n
，0）=r
n
。
如果将这一过程反方向写出，有
r
n
= r
n-2
– q
n
r
n-1
r
n-1
= r
n-3
– q
n-1
r
n-2
…
r
2
= r
0
– q
2
r
1
r
1
= r
-1
– q
1
r
0
r
0
= r
-2
– q
0
r
-1
即r
n
，r
n-1
，…，r
1
，r
0
中每一项均可以用后两项表示。于是r
n
可以用r
-2
，r
-1
表示，即可以找到整数s，t，使得
sa + tb = rn = （a，b）
二、扩展欧几里得算法
定理1.13
设a，b是任意两个正整数，则
s
n
a
+
t
n
b
=
(
a
,
b
)
（式
1.3
）
s_na + t_nb = (a,b)（式1.3）
s
n
a
+
t
n
b
=
(
a
,
b
)
（式
1.3
）
对于j = 0，1，…，n-1，这里s
j
，t
j
归纳定义为
s
−
2
=
1
,
s
−
1
=
0
,
s
j
=
s
j
−
2
−
q
j
s
j
−
1
s_{-2} =1,s_{-1}=0,s_j=s_{j-2}-q_js_{j-1}
s
−
2
=
1
,
s
−
1
=
0
,
s
j
=
s
j
−
2
−
q
j
s
j
−
1
t
−
2
=
0
,
t
−
1
=
1
,
t
j
=
t
j
−
2
−
q
j
t
j
−
1
（式
1.4
）
t_{-2}=0,t_{-1}=1,t_j=t_{j-2} -q_jt_{j-1}（式1.4）
t
−
2
=
0
,
t
−
1
=
1
,
t
j
=
t
j
−
2
−
q
j
t
j
−
1
（式
1.4
）
其中j = 0，1，2，…，n-1，n。q
i
= [r
j-2
/ r
j-1
]是上式的不完全商。设x∈R，[x]表示不超过x的最大整数，称为实数x的整数部分。
证明：
只需证明：对于j = -2，-1，0，1，…，n-1
s
j
a
+
t
j
b
=
r
j
(
式
1.5
）
s_ja+t_jb =r_j(式1.5）
s
j
a
+
t
j
b
=
r
j
(
式
1.5
）
其中r
j
= r
j-2
– q
j
r
j-1
是（式1.5）中的余数。因为（a，b）= r
n
，所以
s
n
a
+
t
n
b
=
(
a
,
b
)
s_na+t_nb=(a,b)
s
n
a
+
t
n
b
=
(
a
,
b
)
对j用数学归纳法来证明式（1.5）。当j = -2时，有s
-2
= 1，t
-2
= 0以及
s
−
2
a
+
t
−
2
b
=
a
=
r
−
2
s_{-2}a+t_{-2}b=a=r_{-2}
s
−
2
a
+
t
−
2
b
=
a
=
r
−
2
式（1.5）对于j = -2成立。
j = -1时，有s
-1
= 0，t
-1
= 1，以及
s
−
1
a
+
t
−
1
b
=
b
=
r
−
1
s_{-1}a+t_{-1}b=b=r_{-1}
s
−
1
a
+
t
−
1
b
=
b
=
r
−
1
式（1.5）对于j = -1成立。
假设式（1.5）对于-2 ≤ j ≤ k-1成立，即
s
j
a
+
t
j
b
=
r
j
s_ja+t_jb=r_j
s
j
a
+
t
j
b
=
r
j
对于j = k，有
r
k
=
r
k
−
2
−
q
k
r
k
−
1
r_k=r_{k-2} – q_kr_{k-1}
r
k
=
r
k
−
2
−
q
k
r
k
−
1
利用归纳假设，得到
r
k
=
(
s
k
−
2
a
+
t
k
−
2
b
)
−
q
k
(
s
k
−
1
a
+
t
k
−
1
b
)
r_k =(s_{k-2}a+t_{k-2}b)-q_k(s_{k-1}a+t_{k-1}b)
r
k
=
(
s
k
−
2
a
+
t
k
−
2
b
)
−
q
k
(
s
k
−
1
a
+
t
k
−
1
b
)
r
k
=
(
s
k
−
2
−
q
k
s
k
−
1
)
a
+
(
t
k
−
2
−
q
k
t
k
−
1
)
b
r_k=(s_{k-2}-q_ks_{k-1})a+(t_{k-2}-q_kt_{k-1})b
r
k
=
(
s
k
−
2
−
q
k
s
k
−
1
)
a
+
(
t
k
−
2
−
q
k
t
k
−
1
)
b
r
k
=
s
k
a
+
t
k
b
r_k=s_ka+t_kb
r
k
=
s
k
a
+
t
k
b
因此，式（1.5）对于j = k成立。
根据数学归纳法，式（1.5）对所有的j = -2，-1，0，1，…，n-1成立。
下面根据上面的证明设计一个算法：假设a和b是不全为零的非负整数，计算s，t使得sa + tb =（a，b）。
首先，令
r
−
2
=
a
r
−
1
=
b
r_{-2}=a\qquad r_{-1}=b
r
−
2
=
a
r
−
1
=
b
s
−
2
=
1
s
−
1
=
0
s_{-2}=1\qquad s_{-1} = 0
s
−
2
=
1
s
−
1
=
0
t
−
2
=
0
t
−
1
=
1
t_{-2}=0\qquad t_{-1}=1
t
−
2
=
0
t
−
1
=
1
这是因为r
k
= s
k
a + t
k
b，所以r
-2
= s
-2
a + t
-2
b = 1✖a + 0✖b = a，r
-1
= s
-1
a + t
-1
b = 0✖a + 1✖b = b。
（1）如果r
-1
= 0，则令
s
=
s
−
2
t
=
t
−
2
s = s_{-2}\qquad t = t_{-2}
s
=
s
−
2
t
=
t
−
2
否则，计算
q
0
=
[
r
−
2
/
r
−
1
]
r
0
=
r
−
2
−
q
0
r
−
1
q_0=[r_{-2}/r_{-1}]\qquad r_0=r_{-2}-q_0r_{-1}
q
0
=
[
r
−
2
/
r
−
1
]
r
0
=
r
−
2
−
q
0
r
−
1
（2）如果r
0
= 0，则令
s
=
s
−
1
t
=
t
−
1
s=s_{-1}\qquad t = t_{-1}
s
=
s
−
1
t
=
t
−
1
否则，计算
s
0
=
s
−
2
−
q
0
s
−
1
t
0
=
t
−
2
−
q
0
t
−
1
s_0=s_{-2}-q_0s_{-1}\qquad t_0=t_{-2}-q_0t_{-1}
s
0
=
s
−
2
−
q
0
s
−
1
t
0
=
t
−
2
−
q
0
t
−
1
以及
q
1
=
[
r
−
1
/
r
0
]
r
1
=
r
−
1
−
q
1
r
0
q_1=[r_{-1}/r_0]\qquad r_1=r_{-1}-q_1r_0
q
1
=
[
r
−
1
/
r
0
]
r
1
=
r
−
1
−
q
1
r
0
（3）如果r
1
= 0，则令
s
=
s
0
t
=
t
0
s = s_0\qquad t = t_0
s
=
s
0
t
=
t
0
否则，计算
s
1
=
s
−
1
−
q
1
s
0
t
1
=
t
−
1
−
q
1
t
0
s_1=s_{-1}-q_1s_0\qquad t_1=t_{-1}-q_1t_0
s
1
=
s
−
1
−
q
1
s
0
t
1
=
t
−
1
−
q
1
t
0
以及
q
2
=
[
r
0
/
r
1
]
r
2
=
r
0
−
q
2
r
1
q_2 = [r_0/r_1]\qquad r_2 = r_0 – q_2r_1
q
2
=
[
r
0
/
r
1
]
r
2
=
r
0
−
q
2
r
1
.
.
.
…
…
（j+1）如果r
j-1
= 0（j ≥ 3），则令
s
=
s
j
−
2
t
=
t
j
−
2
s = s_{j-2}\qquad t = t_{j-2}
s
=
s
j
−
2
t
=
t
j
−
2
否则，计算
s
j
−
1
=
s
j
−
3
−
q
j
−
1
s
j
−
2
s_{j-1}=s_{j-3}-q_{j-1}s_{j-2}
s
j
−
1
=
s
j
−
3
−
q
j
−
1
s
j
−
2
t
j
−
1
=
t
j
−
3
−
q
j
−
1
t
j
−
2
t_{j-1}=t_{j-3}-q_{j-1}t_{j-2}
t
j
−
1
=
t
j
−
3
−
q
j
−
1
t
j
−
2
以及
q
j
=
[
r
j
−
2
/
r
j
−
1
]
r
j
=
r
j
−
2
−
q
j
r
j
−
1
q_j=[r_{j-2}/r_{j-1}]\quad r_j=r_{j-2}-q_jr_{j-1}
q
j
=
[
r
j
−
2
/
r
j
−
1
]
r
j
=
r
j
−
2
−
q
j
r
j
−
1
最后，一定有r
n+1
= 0。这时，令
s
=
s
n
t
=
t
n
s=s_n\qquad t=t_n
s
=
s
n
t
=
t
n
总之，可以找到整数s，t，使得
s
a
+
t
b
=
r
n
=
(
a
,
b
)
sa+tb=r_n=(a,b)
s
a
+
t
b
=
r
n
=
(
a
,
b
)
将上述算法可写成以下python代码：
算法代码实现
from euclid import *
def func(a, b):
r = [a, b]
q = [0, 0]
s = [1, 0]
t = [0, 1]
i = 2
if r[1] == 0:
return s[0], t[0]
else:
next_q = r[0] // r[1]
next_r = r[0] - next_q * r[1]
r.append(next_r)
q.append(next_q)
while r[i] != 0:
next_s = s[i-2] - q[i] * s[i-1]
next_t = t[i-2] - q[i] * t[i-1]
next_q = r[i-1] // r[i]
next_r = r[i-1] - next_q * r[i]
r.append(next_r)
q.append(next_q)
s.append(next_s)
t.append(next_t)
i += 1
return s[i-1], t[i-1]
print(func(202, 282))
print('202 *', func(202, 282)[0], ' + 282 *', func(202, 282)[1], '=', gcdIter(202, 282))
print(func(1613, 3589))
print('1613 *', func(1613, 3589)[0], ' + 3589 *', func(1613, 3589)[1], '=', gcdIter(1613, 3589))
print(func(1859, 1573))
print('1859 *', func(1859, 1573)[0], ' + 1573 *', func(1859, 1573)[1], '=', gcdIter(1859, 1573))
其中eculid模块是自己编写的用来求解最大公约数，详情可以参考信息安全数学基础——欧几里得算法
总结
本文主要介绍了扩展欧几里得算法，其在求解乘法逆元时会非常有帮助。