扩展欧几里得算法（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
参考：
