如何优雅流畅且简洁易懂幽默风趣地证明欧几里得算法和裴蜀定理

c_legg · 2026-08-07 18:50:26 · 算法·理论

本文中的方法出自华罗庚的《数论导引》。

关于模的研究

话说这个东西到底叫什么，整数加法群的一个子群吗？

一个模是一个整数的集合，使得对于这个集合内的任意两个数 a, b，a+b 与 a-b 也在这个集合中。

例如，\{0, 3, -3, 6, -6, 9, -9,\cdots\} 和 0 还有 \varnothing 都是模，\{1, 2, 3\} 则不是（因为 2+3 不在集合中）。

然后我们来研究一些模的性质。

（1）如果一个模非空，那么 0 一定在这个模中。

因为模非空，所以至少一个整数 a 在这个模中，所以 a-a=0 也在。

（2）若 a, b 是整数，则 \{ax+by\mid x, y\in\mathbb{Z}\} 是一个模。

这是显然的。

（3）对于任意一个模（\{0\} 还有 \varnothing 除外），设a 是模中的最小的正整数，则这个模中所有元素都是 a 的整数倍。

假设存在一个 n=ka+r 且 0\lt r\lt a, r, k\in\mathbb{Z} 在模中。

因为 n 和 ka 都在模中，所以 r=n-ka 也在模中。

但是，0\lt r\lt a，所以 a 不是模中的最小正整数。

显然 a 是模中所有非零元素的 \gcd。

由此而来的裴蜀定理

考虑 ax+by=k 这个方程，判断它是否有解，只要判断 k 是否在 \{ax+by\mid x, y\in\mathbb{Z}\} 中。然而这个模中的最小正整数是 \gcd(a, b)，所以 k 在模中当且仅当 \gcd(a, b)\mid k。

欧几里得算法——最大公因数变成模

观察（3）的证明，我们可以发现，要求 \gcd(a, b)，就是要求模 S=\{ax+by\mid x, y\in\mathbb{Z}\} 中的最小正整数。

下面设 a\ge b。

令 r=a\operatorname{mod} b，如果它等于 0，\gcd(a, b)=b。否则 r 显然在 S 中，并且 \{rx+by\mid x, y\in\mathbb{Z}\} 与 S 是同一个模。于是 \gcd(a, b)=\gcd(b, r)，一直递归地做下去就行了。

关于它的复杂度

首先，有一个引理，在 CF 题目中曾经出现，具体证明可以查看该题题解：

当 x\gt y 时，x\operatorname{mod}y\lt\frac{x}{2}。

所以每次 a, b 有一个至少减半，复杂度是 O(\log n) 的。

在剩余的东西中找到扩展欧几里得算法

刚才我们知道了 ax+by=k 在什么时候有解，但这不够，更多时候我们要找到它的解。

首先我们已知这几个事实：

我们只要找到 ax+by=\gcd(a, b) 的解即可，因为假设它的一个解是 (x_0, y_0)，那么 ax+by=k 有一个解 (\frac{k}{\gcd(a, b)}x_0, \frac{k}{\gcd(a, b)}y_0)。

于是我们就可以在回溯时求出解了。假设已经找到一对 (x, y) 使 bx+ry=\gcd(b, r)，那么：

\begin{align*} \gcd(a, b) &= \gcd(b, r) \\ &= bx+ry \\ &= bx+(a-\lfloor\frac{a}{b}\rfloor b)y \\ &= ay+b(x-\lfloor\frac{a}{b}\rfloor y) \end{align*}

这也可以在递归的过程中实现：

std::tuple<int, int, int> exgcd(int a, int b) {
    if(!b) return {a, 1, 0};
    int g, x, y;
    std::tie(g, x, y)=exgcd(b, a%b);
    return {g, y, x-y*(a/b)};
}

希望你能从这篇文章中学到什么，谢谢！