拓展欧几里得算法

介绍

扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。已知整数$a$，$b$扩展欧几里得算法可以在求得$a$，$b$的最大公约数的同时，找到整数$x$，$y$（其中一个可能是负数），使它们满足$ax+by=gcd(a,b)$。如果a是负数，可以把问题转化成$|a|(-x)+by=gcd(|a|,b)$，然后令$x’=(-x)$。

扩展欧几里得算法可以用来计算模反元素(也叫模逆元)，求出模反元素是RSA加密算法中获得所需公钥、私钥的必要步骤。

裴蜀定理

$$
∀a,b∈Z,∃(x,y)∈Z满足ax+by=gcd(a,b)
$$

证明

$∵ax+by=gcd(a,b)，gcd(a,b)=gcd(b,a\mod b)，a\mod b=a-[a/b]*b$

$∴bx+(a\mod b)y=gcd(b,a\mod b)=bx+(a-[a/b]*b)y=ay+b(x-[a/b]y)$

$令x’=y，y’=x-[a/b]y，得到ax’+by’=gcd(a,b)$

我们知道$gcd(a,b)=gcd(a’,0)$，即该表达式最后总能化简成$a’x+0y=gcd(a’,0)$的形式，而当$x=1，y=0$时该式子恒成立，C得证。

代码

C++版本

void exgcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, y, x);
    y -= a / b * x;
}

Python版本

def exgcd(a, b):
    if b == 0:
        x = 1
        y = 0
        return x, y
    x1, y1 = exgcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return x, y

应用

1. 求解不定方程

2. 求解模的逆元

   $ax=1\mod b$在啊$a，b$互质的情况下可转化为$ax+by=1$进行求解。

3. 求解线性同余方程