怎样利用扩展的欧几里得算法求乘法逆元

扩展的欧几里得算法可以求解形如 ax + by = gcd(a, b) 的一次不定方程的整数解，其中 a,b 是任意两个整数，gcd(a,b) 表示 a 和 b 的最大公约数。

对于求解乘法逆元，我们需要解的方程形式为 ax + by = 1，其中 a 是需要求逆的数，b 是取模的数（通常为一个质数），x 就是 a 的逆元。因此，我们只需将式子中的 1 替换成 1 % b，即可得到 ax + by = 1 % b 的形式。

具体求解的步骤如下：

1. 对于给定的 a 和 b，使用欧几里得算法求得它们的最大公约数 gcd(a, b)，并记录每一步的余数和系数。

2. 从最后一步开始，倒序向上推导，求得 x 的值。设最后一步的余数为 r，系数为 k，则有 r = k * a + (b % a)，因此有 r - k * a = b % a。注意这里要使用 b % a 而不是 r % a，因为 b 作为模数，是固定不变的。

3. 将上一步中求得的 x 带入前面的等式中，逐步向上推导，求得 y 的值。

4. 最终得到 x 就是 a 在模数 b 下的逆元。

下面是一个示例代码：

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

def mod_inv(a, b):
    gcd, x, y = ext_gcd(a, b)
    if gcd != 1:
        raise ValueError("a is not invertible mod b")
    else:
        return x % b

其中，ext_gcd 函数实现了扩展的欧几里得算法，mod_inv 函数则直接调用 ext_gcd 求解 a 在模数 b 下的逆元。注意，如果 a 在模数 b 下没有逆元，则会抛出 ValueError 异常。