模p下的乘法逆元

def extended_gcd(a, b):
    """
    扩展欧几里得算法，返回 (gcd(a, b), x, y) 其中 a*x + b*y = gcd(a, b)
    """
    if a == 0:
        return b, 0, 1
    else:
        g, x, y = extended_gcd(b % a, a)
        return g, y - (b // a) * x, x

def mod_inverse(a, p):
    """
    计算模 p 下的乘法逆元，即 a * x ≡ 1 (mod p)
    """
    a = a % p  # 将负数转换为其在模 p 下的等效正数
    g, x, _ = extended_gcd(a, p)
    if g != 1:
        raise ValueError(f"{a} 在模 {p} 下没有乘法逆元")
    else:
        return x % p

# 例子：计算模 17 下的乘法逆元，其中 a 是任意整数（包括负数）
a = 11
p = 23

inverse = mod_inverse(a, p)

print(f"模 {p} 下 {a} 的乘法逆元是 {inverse}")

运行结果

模 17 下 11 的乘法逆元是 14