扩展欧几里得算法求逆元

欧几里得算法是用于求解最大公约数的算法，而扩展欧几里得算法则在求解最大公约数的同时，还能找到一组整数解，使得这组解满足贝祖等式。在求逆元的问题中，可以利用扩展欧几里得算法来求解。

假设我们需要求解一个数a在模m下的逆元，即满足 (a * x) mod m = 1，其中 x 为 a 在模 m 下的逆元。

首先，使用扩展欧几里得算法求解 a 和 m 的最大公约数 d，并找到一组整数解 x 和 y，使得 ax + my = d。由于最大公约数为1，所以 d=1。

进一步观察贝祖等式 ax + my = 1，可以得到 ax ≡ 1 (mod m)。因此 x 就是 a 在模 m 下的逆元。

需要注意的是，当 a 和 m 不互质时，即最大公约数不为1时，a 在模 m 下没有逆元。

下面是一个使用扩展欧几里得算法求解逆元的示例代码（以Python为例）：

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

def mod_inverse(a, m):
    d, x, y = extended_gcd(a, m)
    if d != 1:
        raise ValueError("Inverse does not exist.")
    else:
        return x % m

# 示例使用
a = 5
m = 11
inverse = mod_inverse(a, m)
print(f"The inverse of {a} modulo {m} is {inverse}")

以上代码中，`mod_inverse(a, m)` 函数用于求解 a 在模 m 下的逆元，如果逆元不存在则会抛出 ValueError 异常。