扩展欧几里得算法

扩展欧几里得算法（Extended Euclidean algorithm）是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y，使它们满足贝祖等式

演算过程

求二元一次不定方程 的整数解。

47=30*1+17 // y=1, x=1
30=17*1+13 //    
17=13*1+4 // 同上
13=4*3+1 // 同上

然后把它们改写成“余数等于”的形式

17=47*1+30*(-1)
13=30*1+17*(-1)
4=17*1+13*(-1)
1=13+4*(-3)

然后把它们“倒回去”

1=13+4*(-3)
1=13+[17*1+13*(-1)]*(-3)
1=17*(-3)+13*4
1= 17*(-3)+[30*1+17*(-1)]*4
1=30*4+17*(-7)
1=30*4+[47*1+30*(-1)]*(-7)
1=47*(-7)+30*11

求得 x=-7，y=11。

python

def ext_euclid(a, b):
     if b == 0:
         return 1, 0, a
     else:
         x, y, q = ext_euclid(b, a % b) # q = gcd(a, b) = gcd(b, a%b)
         x, y = y, (x - (a // b) * y)
         return x, y, q

---

参考：

https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm