扩展欧几里得算法求逆元py

扩展欧几里得算法是一种求解线性方程ax+by=gcd(a,b)的算法，其中a、b是整数，x和y是整数解，gcd(a,b)表示a和b的最大公约数。

扩展欧几里得算法可以被用来求解模反元素，模反元素也被称为逆元。逆元是模数n下的一个数x，满足(ax mod n) ≡ 1。

我们可以使用扩展欧几里得算法来求解逆元。具体步骤如下：

1. 初始化a=n，b=m，其中n是模数，m是要求逆元的数。
2. 初始化x=1，y=0。
3. 当b不等于0时，重复以下步骤：
a. 计算商数q = a // b和余数r = a % b。
b. 更新a = b，b = r。
c. 更新x = x_prev - q * x，y = y_prev - q * y。
4. 返回x作为逆元。

下面是一个使用Python实现的例子:

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

def invert_modulo(m, n):
    (x, _) = extended_gcd(n, m)
    return x % n

n = 17
m = 5
inverse = invert_modulo(m, n)
print(inverse)  # 输出7

在上面的例子中，我们想要求模数n=17下数字5的逆元。根据计算，我们得到逆元7。