逆元的求法 python

逆元的求法可以使用扩展欧几里得算法。扩展欧几里得算法可以求解形如ax + by = gcd(a, b)的整数解(x, y)，其中a和b为整数。当a和b互质时，gcd(a, b) = 1，所以可以得到ax + by = 1的整数解(x, y)。因此，x就是a对于模b的乘法逆元。

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

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

def modular_inverse(a, m):
gcd, x, _ = extended_gcd(a, m)
if gcd == 1:
return (x % m + m) % m
else:
return None

通过调用modular_inverse函数，可以求解给定数a对于质数p的乘法逆元。如果逆元不存在，则返回None。代码中使用了扩展欧几里得算法来求解gcd(a, p) = 1的整数解(x, _)，其中x就是a对于模p的乘法逆元。