共计 439 个字符，预计需要花费 2 分钟才能阅读完成。
咱们在中学都学过这个问题：已知非零正整数 a,b 如何求解 a,b 的最大公约数？
答案是欧几里得公式，表达出来就是
gcd(a,b) = gcd(b,a mod b)
用 python 写进去就是
def gcd(a,b):
if b ==0:
return a
return gcd(b,a%b)接下来探讨引理：
a 在模 b 中有逆元，当且仅当 gcd(a,b)=1
这个引理指出了有逆元的条件，咱们来证实其充分性
如果存在整数 x,y，使得
a·x + b·y = 1 (模 b)
则 x 是 a 的逆元，因为 a·x =1 (模 b)
咱们能够应用扩大欧几里得算法来求解 x,y
ax + by = gcd(a,b)
bx1 + (a%b)y1 = gcd(b,a%b)
可推导出
x = y1
y = x1 – (a/b)*x
应用 python 写
def exgcd(a,b):
if b == 0:
return 1,0
x1,y1 = exgcd(b, a%b)
return y1, x1- int(a/b)*y1能求解 x，y
当 a,b 互质时，ax + by = gcd(a,b) = 1
充分性得证
必要性在这里不证实了，比较简单
x 即为 a 的逆元
正文完
