欧几里得算法和扩展欧几里得算法数学

??欧几里得算法即辗转相除法，是求两个数的最大公因数的有效算法。而扩展欧几里得算法则可以求出等式sa+tb=gcd(a,b)中的s和t，该算法可以被用于求解模p运算的逆元，也是一个很有效的算法。
约定和解释

文章中所说的数除非特殊说明为非负整数
( a , b ) (a,b) (a,b)表示 a a a和 b b b的最大公因数

欧几里得算法（辗转相除法）算法描述有两个整数 a a a和 b b b, 并且 a > b a > b a>b, 则 a a a和 b b b有如下关系（欧几里得除法）（ a a a为被除数， b b b为除数，求出余数 r r r）：
a = q b + r ( 0 ≤ r < b ) a=qb+r \quad (0 \leq r < b) a=qb+r(0≤r 我们令 a 2 = b ,b 2 = r a_2=b, \ b_2=r a2?=b, b2?=r则类似的有（把除数 b b b和余数 r r r作为被除数和除数再次执行上述运算）
a 2 = q 2 b 2 + r 2 ( 0 ≤ r 2 < b 2 < b ) a_2=q_2 b_2 + r_2 \quad (0 \leq r_2 < b_2 < b) a2?=q2?b2?+r2?(0≤r2? 依次类推, 必然存在 a n ,b n ,r n a_n, \ b_n, \ r_n an?, bn?, rn?满足
a n = q n b n + r n ( r n = 0 ) a_n = q_n b_n + r_n \quad (r_n = 0) an?=qn?bn?+rn?(rn?=0)
即
a n = q n b n a_n = q_n b_n an?=qn?bn?
理由是 r > r 1 > r 2 . . . > r n r > r_1 > r_2...>r_n r>r1?>r2?...>rn?且 r i ( i = 1 , 2 , 3... , n ) r_i (i = 1,2,3...,n) ri?(i=1,2,3...,n)为大于等于0的整数， r i r_i ri?依次减小最终必然会到0
此时的 b n b_n bn?就是 a a a和 b b b的最大公因数
算法的正确性欧几里得算法之所以有效，基于这样一个事实
若 a = q b + r ( 0 ≤ r < b ) ，则 a 和 b 的最大公因数与 b 和 r 的最大公因素相同若a=qb+r \quad (0 \leq r < b)，则a和b的最大公因数与b和r的最大公因素相同若a=qb+r(0≤r 证明如下：
设 d = ( a ,b ) , d 1 = ( b ,r ) 则有 d∣( a ? q b ) ， d 1∣( q b + r ) 即 d∣r , 即 d 1∣a 所以有 d∣d ‘ 且 d 1∣d 所以 d = d 1 设d = (a, \ b),\quad d_1=(b, \ r) \\ 则有d \ | \ (a-qb)， \quad d_1 \ | \ (qb + r) \\ 即d \ | \ r , 即 d_1 \ | \ a \\ 所以有 d \ | \ d^` 且 d_1 \ | \ d \\ 所以 d = d_1 设d=(a, b),d1?=(b, r)则有d ∣ (a?qb)，d1? ∣ (qb+r)即d ∣ r,即d1? ∣ a所以有d ∣ d‘且d1? ∣ d所以d=d1?
我们利用这个性质，把求较大的两个数 a a a和 b b b的公因数的问题不断转换成求两个较小的数（除数和余数）最大公因数的问题，直到这两个较小的数中有一个为0了，由于0和任何一个数x$ 的最大公因数就是的最大公因数就是的最大公因数就是x$，因为就求出了最大公因数。
python实现

def gcd(big_num, small_num): remainder = big_num % small_num if remainder == 0: return small_num return gcd(small_num, remainder)

扩展欧几里得算法算法描述根据定理，对于任意整数 a a a和 b b b，必然存在整数 s s s和 t t t使得如下等式成立
s a + t b = ( a , b ) sa+tb=(a,b) sa+tb=(a,b)
要求出其中的 s s s和 t t t可以利用欧几里得算法求最大公因数的过程
【欧几里得算法和扩展欧几里得算法】在这里，为了更好的说明算法，我们使用 a 1 和 a 2 a_1和a_2 a1?和a2? ( a 1 > a 2 ) (a_1 > a_2) (a1?>a2?)来表示欧几里得算法中的 a 和 b a和b a和b，按照欧几里得算法，有如下求 a 1 和 a 2 a_1和a_2 a1?和a2?最大公因数 ( a 1 , a 2 ) (a_1,a_2) (a1?,a2?)的过程
a 1 = q 1 a 2 + a 3 a 2 = q 2 a 3 + a 4 a 3 = q 3 a 4 + a 5 . . . a n ? 3 = q n ? 3 a n ? 2 + a n ? 1 a n ? 2 = q n ? 2 a n ? 1 + a n a n ? 1 = q n ? 1 a n a_1=q_1a_2+a_3 \\ a_2=q_2a_3+a_4 \\ a_3=q_3a_4+a_5 \\ ... \\ a_{n-3}=q_{n-3}a_{n-2}+a_{n-1} \\ a_{n-2}=q_{n-2}a_{n-1}+a_n \\ a_{n-1} = q_{n-1}a_n a1?=q1?a2?+a3?a2?=q2?a3?+a4?a3?=q3?a4?+a5?...an?3?=qn?3?an?2?+an?1?an?2?=qn?2?an?1?+an?an?1?=qn?1?an?
a n a_n an?就是 a 1 和 a 2 a_1和a_2 a1?和a2?的最大公因数
首先根据欧几里得算法的求解过程，我们容易得到
( a 1 , a 2 ) = a n = a n ? 2 ? q n ? 2 a n ? 1 (a_1,a_2) = a_n = a_{n-2} - q_{n-2}a_{n-1} (a1?,a2?)=an?=an?2??qn?2?an?1?
根据上式子，可以得到对于 a n ? 2 和 a n ? 1 a_{n-2}和a_{n-1} an?2?和an?1?来说使等式
( a 1 , a 2 ) = s n ? 2?a n ? 2 + t n ? 2?a n ? 1 式 1 (a_1, a_2) = s_{n-2} \ \cdot \ a_{n-2} + t_{n-2} \ \cdot \ a_{n-1} \qquad 式1 (a1?,a2?)=sn?2? ? an?2?+tn?2? ? an?1?式1
成立的 s n ? 2 和 t n ? 2 s_{n-2}和t_{n-2} sn?2?和tn?2?的值，即
s n ? 2 = 1 t n ? 2 = ? q n ? 2 s_{n-2} = 1 \\t_{n-2} = -q_{n-2} sn?2?=1tn?2?=?qn?2?
现在我们想要计算对于 a n ? 3 和 a n ? 2 a_{n-3}和a_{n-2} an?3?和an?2?来说等式
( a 1 , a 2 ) = s n ? 3?a n ? 3 + t n ? 3?a n ? 2 式 2 (a_1, a_2) = s_{n-3} \ \cdot \ a_{n-3} + t_{n-3} \ \cdot \ a_{n-2} \qquad 式2 (a1?,a2?)=sn?3? ? an?3?+tn?3? ? an?2?式2
成立的 s n ? 3 和 t n ? 3 s_{n-3}和t_{n-3} sn?3?和tn?3?的值
根据欧几里得算法的求解过程，有如下等式对n>3都成立
a n ? 1 = a n ? 3 ? q n ? 3 a n ? 2 式 3 a_{n-1} = a_{n-3} - q_{n-3}a_{n-2} \qquad 式3 an?1?=an?3??qn?3?an?2?式3
将式3中 a n ? 1 a_{n-1} an?1?的表达式带入式1得到
( a 1 , a 2 ) = t n ? 2?a n ? 3 + ( s n ? 2 ? q n ? 3 ? t n ? 2 )?a n ? 2 式 4 (a1, a2) = t_{n-2} \ \cdot \ a_{n-3} + (s_{n-2}-q_{n-3} \cdot t_{n-2}) \ \cdot \ a_{n-2} \qquad 式4 (a1,a2)=tn?2? ? an?3?+(sn?2??qn?3??tn?2?) ? an?2?式4
可以看到，我们在式2中需要求的 s n ? 3 和 t n ? 3 s_{n-3}和t_{n-3} sn?3?和tn?3?求出来了，且这个关系也对n>3都成立
s n ? 3 = t n ? 2 t n ? 3 = s n ? 2 ? q n ? 3?t n ? 2 s_{n-3} = t_{n-2} \\ t_{n-3} = s_{n-2} - q_{n-3} \ \cdot \ t_{n-2} sn?3?=tn?2?tn?3?=sn?2??qn?3? ? tn?2?
按照这个关系，我们可以一直向前推，直到 s 1 和 t 1 s_1和t_1 s1?和t1?满足
( a 1 , a 2 ) = s 1? a 1 + t 1?a 2 (a_1,a_2)=s_1 \ \cdot a_1 + t_1 \ \cdot \ a_2 (a1?,a2?)=s1? ?a1?+t1? ? a2?
从而解出了想要求出的 s s s和 t t t。
注:s s s和 t t t不唯一的（只考虑绝对值不同），例如：
6720 × 46480 + ( ? 19713 ) × 39423 = 1 ( ? 22703 ) × 46480 + 26767 × 39423 = 1 6720 \times 46480 + (-19713) \times 39423 = 1 \\ (-22703) \times 46480 + 26767 \times 39423 = 1 6720×46480+(?19713)×39423=1(?22703)×46480+26767×39423=1
这似乎说明39423模46480的逆元有两个，但实际上有 ( ? 19713 ) + 46480 = 26767 (-19713) + 46480 = 26767 (?19713)+46480=26767
即 ? 19713 ≡ 26767( m o d46480 ) -19713 \equiv 26767 \ (mod \ 46480) ?19713≡26767 (mod 46480), 对于 a a a和 b b b不互质的情况，暂不清楚。
算法的应用该算法可以在 a a a和 p p p互质时被用来快速求 a a a模 p p p的逆元 a ‘ a^` a‘
因为若
s?a + t?p = 1 s \ \cdot \ a + t \ \cdot \ p = 1 \\ s ? a+t ? p=1
则有
s?a ≡ 1( m o dp ) s \ \cdot \ a \equiv 1 \ (mod \ p) s ? a≡1 (mod p)
其中 s s s就是 a a a的逆元 a ‘ a^` a‘
python实现

# 参数为两个数，大数在前小数在后 # 返回值为s,t和两个数的最大公因数 def gcd_ext(big_num, small_num): remainder = big_num % small_num iq = int(big_num / small_num) if small_num % remainder == 0: s = remainder t = -iq return (s, t, remainder) s_last, t_last, gcd = gcd_ext(small_num, remainder) s = t_last t = s_last - t_last * iq return (s, t, gcd)

参考资料信息安全数学基础（第2版）陈恭亮【清华大学出版社】