扩展欧几里德算法求模逆元

扩展欧几里德算法可以用来求解模逆元，对于给定的正整数 a 和模数 m，模逆元 x 是满足 ax ≡ 1 (mod m) 的整数 x。以下是求解模逆元的步骤：

1. 使用扩展欧几里德算法求解 a 和 m 的最大公约数 gcd(a, m) 和一对整数 x0 和 y0，使得 ax0 + my0 = gcd(a, m)。

2. 如果 gcd(a, m) 不为 1，则 a 在模 m 下没有逆元。

3. 如果 gcd(a, m) 为 1，则 x0 是 a 在模 m 下的逆元。因为 ax0 ≡ 1 (mod m)，所以 x0 就是满足条件的 x。

4. 如果 x0 是负数，则可以加上 m 使其变为正数。

下面是求解模逆元的 Python 代码实现：

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

def mod_inverse(a, m):
    d, x, y = ext_euclid(a, m)
    if d != 1:
        return None  # a 在模 m 下没有逆元
    else:
        x %= m
        if x < 0:
            x += m
        return x

在上述代码中，ext_euclid 函数是扩展欧几里德算法的实现，mod_inverse 函数调用了 ext_euclid 函数来求解模逆元。如果 a 在模 m 下没有逆元，则返回 None，否则返回满足条件的 x 值。