擴(kuò)展歐幾里得算法（Extended Euclidean algorithm）是歐幾里得算法（又叫輾轉(zhuǎn)相除法）的擴(kuò)展。已知整數(shù)a、b，擴(kuò)展歐幾里得算法可以在求得a、b的最大公約數(shù)的同時(shí)，能找到整數(shù)x、y，使它們滿足貝祖等式

演算過程

求二元一次不定方程 的整數(shù)解。

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

然后把它們改寫成“余數(shù)等于”的形式

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