用Python求两个数的乘法逆元

乘法逆元指的是在模p下，对于给定的a和p，找到一个数x，使得a*x ≡ 1 (mod p)。下面是一个用Python求两个数的乘法逆元的示例代码：

def gcd_extended(a, b):
    if a == 0:
        return b, 0, 1
    else:
        gcd, x1, y1 = gcd_extended(b % a, a)
        x = y1 - (b // a) * x1
        y = x1
        return gcd, x, y

def find_inverse(a, p):
    gcd, x, y = gcd_extended(a, p)
    if gcd != 1:
        return None
    else:
        return (x % p + p) % p

a = 3
p = 11
inverse = find_inverse(a, p)
if inverse is None:
    print("No inverse exists")
else:
    print("Inverse of {} modulo {} is {}".format(a, p, inverse))

输出：

Inverse of 3 modulo 11 is 4

这里定义了一个求扩展欧几里得算法的函数`gcd_extended`，然后通过该函数求出a在模p下的逆元。如果a和p的最大公因数不为1，则不存在逆元，返回None。否则返回逆元。在上面的示例中，我们求解了3在模11下的逆元，结果为4。