【OI考古】数论基础 | 扩展欧几里得算法

印象中之前每次复习扩展欧几里得算法时，Google到的大佬们对扩欧的解释常常晦涩难懂。因此，在这文章中，我将根据自己的理解，试图以一种优雅的方式解释扩展欧几里得算法，希望能够使读者对扩展欧几里得算法形成直观而专业的理解。

先决条件

欧几里得算法

在了解扩展欧几里得算法前，当然要先知道欧几里得算法是什么。

如果你还不会求GCD，请先到这里复习一下欧几里得算法。

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

裴蜀定理

裴蜀定理的描述是这样的：

$∀a,b∈Z,∃(x,y)∈Z, \quad$

$s.t. \quad ax+by=gcd(a,b)$

$ax+by=gcd(a,b)$ 被称为裴蜀等式。

这里不多解释，知道有这个定理就行。

扩展欧几里得算法

正如裴蜀定理所介绍的那样，扩展欧几里得算法的产生源自于对裴蜀等式的求解问题：

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

这里所说的求解当然是指要求 $x, y$ 的整数解。

推导

可以看出，这是一个不定方程，整数解有无穷多个。可以证明，如果我们找到一组解 $x_0, y_0$ ，则该方程的通解为：

$\begin{cases} x = x_0 + bt \\ y = y_0 - at \end{cases} \quad t∈Z$

在欧几里得算法中，我们用gcd(a, b)这个函数来计算 $a, b$ 的最大公约数，计算过程中需要递归地返回gcd(b, a % b)的值。

类比地，我们试图用exgcd(a, b, x, y)来求解裴蜀等式，此函数返回的仍然是 $a, b$ 的最大公约数，并利用C++的引用特性在计算过程中将我们所需的裴蜀等式的解 $x, y$ 带出。可以猜想，此过程中需要递归计算exgcd(b, a % b, x, y)，也就是求解以下方程：

$bx + (a\%b)y = gcd(b, a\%b)$

而 $gcd(b, a\%b)$ 其实就是 $gcd(a, b)$ 。

这里的 $x, y$ 应该不是裴蜀等式所需要求的 $x, y$ ，但是二者之间应该具有某种联系。可以尝试将这个方程的左式化简一下：

$bx + (a\%b)y = bx + (a - b \lfloor a/b\rfloor )y = ay + b(x - \lfloor a/b\rfloor y)$

然后我们就惊讶地发现下面这两个方程具有相同的结构：

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

$ay + b(x - \lfloor a/b\rfloor y) = gcd(a, b)$

欲解第一个方程，须先解第二个方程。换句话说，如果我们想利用 exgcd(a, b, x, y)这样的函数求解裴蜀等式，要先求exgcd(b, a%b, x, y)，获得 $x, y$ 值之后，令：

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

至此我们就完成了扩展欧几里得算法中，下层递归结果对上一层的转化。

在欧几里得算法中，递归的临界条件是输入的 $b=0$ ，此时 $a$ 就是所求的最大公约数。同样的，在扩展欧几里得算法中，如果我们向下一直递归，最终输入的 $a, b$ 中 $b$ 将为 $0$ ,此时无论 $a$ 如何取值，都有 $x=1, y=0$ ，因为：

$a \times 1 + b \times 0=gcd(a, 0)$

然后在回溯的过程中，通过上述算法，层层计算 $x,y$ 的值，最终可以得到最初的裴蜀等式的一组特解。

解决方案

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

后续步骤

至此你恭喜你已经学会了扩展欧几里得算法（如果我的文章写的还行的话），现在你可以使用扩展欧几里得算法愉快地解决以下问题了。

线性同余方程

求形如 $ax ≡ c(\mod b)$ 的线性同余方程。

这里 $gcd(a, b) | c$

乘法逆元

如果一个线性同余方程 $ax ≡ 1(\mod b)$ ，则 $x$ 称为 $a \mod b$ 的逆元，记作 $a^{-1}$ 。