扩展欧几里得算法（英语：Extended Euclidean algorithm）是欧几里得算法（又叫辗转相除法）的扩展。已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式
ax+by=gcd(a,b)
如果a是负数，可以把问题转化成
|a|(-x) + by = gcd(|a|,b)
然后令x'=(-x)
通常谈到最大公约数时，我们都会提到一个非常基本的事实：给予二个整数a、b，必存在整数x、y使得ax + by = gcd(a,b)[1]。
有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解。
扩展欧几里得算法可以用来计算模反元素(也叫模逆元)，而模反元素在RSA加密算法中有举足轻重的地位。
例子
用类似辗转相除法，求二元一次不定方程 47x+30y=1
的整数解。
47=30 *1 +17
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*1+4*(-3)
然后把他们倒回去
1=13*1+4*（-3）
1=13*1+[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
实现
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)
print(x,y,q)
return x, y, q
