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

预备知识

欧几里得算法 (Euclidean algorithm)

常叫辗转相除法，其证明了 $gcd (a, b) = gcd (b, a mod 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$ 的线性丢番图方程（称为裴蜀等式）：

$a x + b y = m$

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

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

算法描述

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

$a x + b y = gcd (a, b)$

算法过程

特解

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

$a x + 0 y = a$

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

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

$\begin{aligned} b y + (a mod b) x & = d \\ b y + (a - ⌊ \frac{a}{b} ⌋ \cdot b) x & = d \\ a x + b (y - ⌊ \frac{a}{b} ⌋ \cdot x) & = d \end{aligned}$

因此当层的解为：

${\begin{cases} x^{'} = x \\ y^{'} = y - ⌊ a / b ⌋ \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 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;
}

解决线性同余方程

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

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

$a x + m y = b$

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

$a x^{'} + b y^{'} = d$

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

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

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

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

$a^{- 1} \equiv a^{p - 2} (\mod p)$

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

$a x \equiv 1 (\mod 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$ 没有乘法逆元。

数论 | 扩展欧几里得算法