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

扩展欧几里德算法是求解一元一次不定方程 ax+by=gcd(a,b) 的算法，其中 a, b 为整数，x, y 为整数解，gcd(a,b) 表示 a 和 b 的最大公约数。在求解模逆元的问题中，我们需要求解的是 ax ≡ 1 (mod n) 的解 x，其中 n 是模数，也是一个整数。

为了使用扩展欧几里德算法求解模逆元，我们需要将上述一元一次不定方程转化为 ax+ny=1 的形式。这里 n 就是模数，因为 ax ≡ 1 (mod n) 等价于 ax-ny=1，所以我们需要找到 a 和 n 的最大公约数 gcd(a,n)，如果 gcd(a,n) 不为 1，则方程无解；否则，我们就可以使用扩展欧几里德算法求解出 ax+ny=1 的一组整数解，其中 x 就是 a 在模 n 意义下的逆元。

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

def ext_gcd(a, b):
    if b == 0:
        return a, 1, 0
    else:
        d, x, y = ext_gcd(b, a % b)
        return d, y, x - (a // b) * y
 
def mod_inverse(a, n):
    d, x, y = ext_gcd(a, n)
    if d != 1:
        return None  # a 和 n 不互质，不存在模逆元
    else:
        return (x % n + n) % n  # 返回 a 在模 n 意义下的逆元

其中，`ext_gcd(a, b)` 函数用于求解一元一次不定方程 ax+by=gcd(a,b) 的整数解 (x, y) 和 gcd(a,b)。`mod_inverse(a, n)` 函数则是利用扩展欧几里德算法求解模逆元的函数，如果 a 和 n 不互质，即 gcd(a,n) != 1，则返回 `None` 表示不存在模逆元；否则，返回 a 在模 n 意义下的逆元 `(x % n + n) % n`。