扩展欧几里得算法学习笔记

#相关定理

欧几里得算法

$$\begin{array}{ll} \forall a, b \in \N, b \ne 0, \\ \gcd(a, b) = gcd(b, a \bmod b) \end{array}$$

Bézout 定理

对于任意整数 $a, b$，存在一对整数 $x, y$ 满足 $ax + by = gcd(a, b)$。

#扩展欧几里得算法

扩展欧几里得算法是用来求二元一次不定方程（如 $(1)$ 式）的一组特解的算法。

$$\tag{1} ax + by = c$$

$(1)$ 式有解当且仅当 $\gcd(a, b) ~|~ c$。

#实现

对于每次递归，

• 当 $b = 0$ 时，
  $ax + by = a$，故 $x = 1, y = 0$。
• 当 $b \ne 0$ 时，
  $x = x, y = y - \lfloor\frac{a}{b} \rfloor x$。

证明：

设 $d = \gcd(a, b)$，由欧几里得算法得：

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

则上述 $b \ne 0$ 情况中的式子成立。

证毕。

#代码

1
2
3
4
5
6
7
8
9
10

int exgcd(int a, int b, int& x, int& y) {
    if (!b) {
        x = 1, y = 0;
        return a;
    }

    int g = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return g;
}

#通解

求出特解 $x_0, y_0$ 后补齐次项即可：

$$\begin{array}{l} x = x_0 + bk \\ y = y_0 - ak \end{array}$$

方程的最小整数解的 $k = b / \gcd(a, b)$，$x = (x \bmod k + k ) \bmod k$。

#逆元

若 $ax \equiv 1 ~(\bmod~ b)$，且 $a, b$ 互质，则称 $x$ 为 $a$ 的逆元，记为 $a^{-1}$。

可将上式转化为：

$$\tag{2} ax + by = 1$$

这样可以就使用扩展欧几里得算法求出 $(2)$ 式的解，$x$ 的最小解即为 $a$ 的逆元。

#参考资料

1. 第 150 ~ 151 页，0x33 同余，《算法竞赛进阶指南》（ISBN 978-7-83009-313-6，河南电子音像出版社），李煜东，2019 年 5 月第 5 次修订版。
2. 1.3.4 扩展欧几里得算法，《信息学奥赛之数学一本通》（ISBN 978-7-5641-6576-5，东南大学出版社），林厚从，2019 年 11 月第 9 次修订版。
3. 1.4 逆元，《信息学奥赛之数学一本通》（ISBN 978-7-5641-6576-5，东南大学出版社），林厚从，2019 年 11 月第 9 次修订版。

2022-05-06: 感谢 iBug 指出本文中的错误。