关于数学:求解线性模运算中的逆元

咱们在中学都学过这个问题：已知非零正整数 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 的逆元