扩展欧几里得算法：已知整数 $a$、$b$，求得 $x$、$y$ 满足 $ax+by=\gcd(a,b)$.

预备知识

欧几里得算法 (Euclidean algorithm)

常叫辗转相除法，其证明了 $\gcd(a,b)=\gcd(b,a\bmod b)$.

这里给出代码供下文参考：

int gcd(int a, int b)
{
    if (!b)
        return a;
    return gcd(b, a % b);
}

笔记链接：https://io.zouht.com/17.html

裴蜀定理 (Bézout's lemma)

对任何整数 $a$、$b$ 和 $m$，关于未知数 $x$ 和 $y$ 的线性丢番图方程（称为裴蜀等式）：

$$ ax+by=m $$

有整数解时当且仅当 $m$ 是 $a$ 及 $b$ 的最大公约数 $d$ 的倍数。

扩展欧几里得算法 (Extended Euclidean algorithm)

算法描述

已知整数 $a$、$b$，扩展欧几里得算法可以在求得 $a$、$b$ 的最大公约数的同时，能找到整数 $x$、$y$（其中一个很可能是负数），使它们满足贝祖等式：

$$ ax + by = \gcd(a, b) $$

算法过程

特解

在欧几里得算法中，递归边界时 $b=0$，$\gcd(a,0)=a$。此时裴蜀等式为：

$$ ax+0y=a $$

易得 $x=1,y=0$，然后返回 $(a,1,0)$，第一位代表最大公约数，第二、三位代表该层裴蜀等式的 $x$ 和 $y$.

在递归中间部分时，我们得到了 $\gcd(b,a\bmod b)=d,x,y$。此时裴蜀等式为（不妨令前面系数为 $y$，后面为 $x$）：

$$ \begin{align} by+(a\bmod b)x&=d\\ by+(a-\lfloor\frac{a}{b}\rfloor\cdot b)x&=d\\ ax+b(y-\lfloor\frac{a}{b}\rfloor\cdot x)&=d \end{align} $$

因此当层的解为：

$$ \begin{cases} x'=x\\ y'=y-\lfloor a/b\rfloor\cdot x\\ \end{cases} $$

于是返回 $(d,x',y')$.

通解

该算法求出的是一对满足条件的 $x_0$ 和 $y_0$，实际上答案不唯一，可以通过构造：

$$ a(x_0-k\cdot\frac{b}{d})+b(y_0+k\cdot\frac{a}{d})=d\ (k\in\mathbb{Z}) $$

得到通解：

$$ \begin{cases} x=x_0-k\cdot(b/d)\\ y=y_0+k\cdot(a/d)\\ \end{cases} $$

代码实现

代码中，返回值并未用三元组，而是返回最大公约数，同时通过引用传回了 $x$ 和 $y$，没有本质区别。

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

解决线性同余方程

扩展欧几里得算法可以解决形如 $ax\equiv b\pmod m$ 的线性同余方程，方式如下。

由 $ax\equiv b\pmod m$ 可知，存在 $y$，使 $ax=b+my$. 不妨将 $my$ 移动至等式左侧，负号放入 $y$ 中，则得到：

$$ ax+my=b $$

再令 $d=\gcd(a,m)$，那么关于未知数 $x'$ 和 $y'$ 的裴蜀等式可写为：

$$ ax'+by'=d $$

可使用扩展欧几里得算法得到 $x',y',d$ 的值。如果 $b$ 是 $d$ 的倍数，那么原线性同余方程有解，解为：

$$ \begin{cases} x=x'\cdot(b/d)\bmod m\\ y=y'\cdot(b/d)\bmod m\\ \end{cases} $$

解决模数非质数的乘法逆元

当 $p$ 为质数时，可使用费马小定理求出乘法逆元：

$$ a^{-1}\equiv a^{p-2}\pmod p $$

但当 $p$ 非质数时，该方法失效。此时可构造线性同余方程：

$$ ax\equiv1\pmod p $$

再使用上一节的方法，利用扩展欧几里得算法解该方程即可，代码如下：

int inv(int a, int p)
{
    int x, y;
    if (exgcd(a, p, x, y) != 1)
        return -1; // 无解
    return (x % p + p) % p;
}

注意无解的情况，由裴蜀定理的约束条件，$a$ 和 $x$ 必须满足 $\gcd(a,p)=1$ 才有解。

即：数 $a$ 与模数 $p$ 不互质时，$a$ 对于 $p$ 没有乘法逆元。