扩展欧几里得算法证明及求乘法逆元

扩展欧几里得算法

已知整数a、b，扩展欧几里得算法可以在求得a、b的最大公约数的同时，能找到整数x、y，使它们满足贝祖等式：ax+by=gcd(a,b)

为什么一定存在贝祖等式呢，裴蜀定理如下：

设存在x，y使ax+by=d，d是ax+by取值中的最小正整数，d≠1。再设am+bn=e，则e≥d .若d不整除e，对e做带余除法.必定存在p，r使e=pd+r.r<d则r=e-pd=（m-px）a+（n-py）b.存在整数m-px，n-py使ax+by=r<d，与d的最小性矛盾。所以d整除e.令m=1，n=0，则d整除a；同理d整除b.所以d=gcd(a,b)

下面给出扩展欧几里得算法的证明

ax + by = gcd(a, b)
a'x' + b'y' = gcd(a', b') (其中a'= b, b' = a % b,)
我们要得到x,y与x',y'的关系
将a'= b, b' = a % b带入第一个等式
得：bx' + (a%b)y' = gcd(a', b')
因为a%b = a - b[a/b] ([a/b],取a除以b的整数)所以ay' + b(x' - [a/b]y') = gcd(a', b') = gcd(a,b)(由辗转相除得)
所以，x,y,x',y'的关系是：

x=y'
y=x' - [a/b] * y'

这样就可以用递推公式，不断向下得到x',y'。

下面给出对应的python代码

#扩展欧几里得算法求线性方程的x与y
def exten_(a, b):
	if b == 0:
		return 1, 0
	else:
		k = a // b
		remainder = a % b		
		x1, y1 = get_(b, remainder)
		x, y = y1, x1 - k * y1			
	return x, y

扩展欧几里得算法求乘法逆元

aa'=1(mod b) -> aa'=km+1 -> aa'-kb=1
令x=a' y=-k 即得ax+by=1，即可利用扩展欧几里得算法求得a'