扩展欧几里得求逆元python

扩展欧几里得算法是一种求解两个整数a、b的最大公约数的同时，能找到整数x、y（其中一个很可能是负数），使它们满足贝祖等式ax+by=gcd(a,b)的算法。在求解乘法逆元时，我们可以使用扩展欧几里得算法来求解。假设a和n是两个互质的整数，那么a在模n意义下的逆元就是满足ax≡1(mod n)的x。根据扩展欧几里得算法，我们可以求出ax+ny=gcd(a,n)的一组解(x,y)，那么ax≡1(mod n)的解就是x mod n。因此，我们可以使用扩展欧几里得算法来求解a在模n意义下的逆元。

以下是求解乘法逆元的Python代码：

def gcd(a,b,s):
if a%b == 0:
return b,s
q = a//b
temp = s
s = s-q*s
s = temp
return gcd(b,a%b,s)

def ModReverse(a,n):
s = [1,0]
gcd(a,n,s)
if s==0:
return -1
elif s<0:
return n+s
else:
return s%n

其中，gcd函数是扩展欧几里得算法的实现，ModReverse函数是求解乘法逆元的实现。在ModReverse函数中，我们首先调用gcd函数求解ax+ny=gcd(a,n)的一组解(x,y)，然后判断是否存在逆元。如果不存在逆元，则返回-1；如果存在逆元且x为负数，则返回n+x；否则，返回x mod n。