用python代码实现欧几里得扩展算法 模运算求逆

欧几里得扩展算法（也称为中国剩余定理的简化版）用于计算两个整数的最大公约数（GCD）以及它们的模逆元。当需要找到a除以b的逆元模m（即gcd(a, m) = 1的情况下），可以同时求出a和b的逆元c和d。

Python实现如下：

def extended_gcd(a, b):
    """
    使用欧几里得扩展算法计算最大公约数并返回 a * c % m == 1 的c值（如果存在）
    """
    x, y, u, v = 0, 1, 1, 0
    while b != 0:
        q, r = divmod(a, b)
        a, b = b, r
        x, u = u - q * x, x
        y, v = v - q * y, y
    return a, u, v

# 示例：计算5和17的最小公倍数及模逆
a = 5
b = 17
gcd, inv_a, inv_b = extended_gcd(a, b)

if gcd == 1:  # 如果有模逆元
    lcm = a * b // gcd  # 最小公倍数
    print(f"5对17取模逆的结果是 {inv_a} (mod {b})")
    print(f"17对5取模逆的结果是 {inv_b} (mod {a})")
    print(f"5和17的最小公倍数是 {lcm}")
else:
    print("无法找到模逆元，因为gcd(5, 17) != 1")