裴蜀定理？

· · 算法·理论

以前上课时讲的裴蜀定理，实在是太吃操作了，现在貌似就看不懂了。

但是我想到了一个不那么吃操作的证法。

引理1

**证明：** 周期为 $k$，意味着有 $ax \equiv a(x+k) \pmod{b}$，可以推出 $0 \equiv ak \pmod{b}$。 因为我们希望周期最小，且 $ak \mod b = 0$，所以 $k = \frac{b}{\gcd(a,b)}$（也就是把 $a$ 可以提供的因子从 $b$ 中去除，剩下的东西就是 $a$ 提供不了、要 $x$ 提供的了）。 证毕。 **引理2** $ax + by = 1 \iff \gcd(a,b) = 1$。 我们先来证明： **"存在整数 $x, y$ 使得 $ax + by = 1$" $\implies$ $\gcd(a,b) = 1$** 我们知道，根据最大公约数的定义，有 $\gcd(a,b) \mid a$ 和 $\gcd(a,b) \mid b$。 再根据线性组合，就有 $\gcd(a,b) \mid ax + by$。 因为存在 $x, y$ 使得 $ax + by = 1$（已知），所以有 $\gcd(a,b) \mid 1$，所以 $\gcd(a,b) = 1$。 证毕。 现在我们来证明： **"存在整数 $x, y$ 使得 $ax + by = 1$" $\impliedby$ $\gcd(a,b) = 1$** 一眼望去，好像两者毫无关系。忽然，我们发现 $ax + by = 1$ 是一个经典的一次函数，于是有 $y = \frac{1 - ax}{b}$。 所以，如果存在整数 $x, y$ 使得 $y = \frac{1 - ax}{b}$ 成立，那么原命题成立。也就是说，我们希望存在 $x$ 使得 $b \mid 1 - ax$。 将其转换为同余形式：$0 \equiv 1 - ax \pmod{b}$。移项，得 $ax \equiv 1 \pmod{b}$。 根据**引理1**，我们知道 $ax \mod b$ 的周期为 $\frac{b}{\gcd(a,b)}$。因为 $\gcd(a,b) = 1$，所以自然有周期为 $b$。 那么，假如没有 $x$ 使得 $ax \equiv 1 \pmod{b}$，那么在 $ax \mod b$（$0 \le x \le b-1$）中，肯定存在一个余数出现了两次（不然 $b$ 个数凑不出 $b$ 个余数）。 但是由于周期为 $b$，而 $|x_1 - x_2|$ 的最大值为 $b - 1$（这里 $x_1, x_2$ 指的是重复出现的余数对应的两个 $x$），所以假设不成立。 所以，必然有 $x$ 使得 $ax \equiv 1 \pmod{b}$，所以原命题成立。 所以，"存在整数 $x, y$ 使得 $ax + by = 1$" $\impliedby$ $\gcd(a,b) = 1$。 **裴蜀定理** 对于 $a, b$，一定有整数 $x, y$ 使得 $ax + by = \gcd(a,b)$。 **证明：** 设 $A = \frac{a}{\gcd(a,b)}$，$B = \frac{b}{\gcd(a,b)}$。显然此时 $A, B$ 互质。 通过**引理2**可得，有整数 $X, Y$ 使得 $AX + BY = 1$。 将等式两边同时乘以 $\gcd(a,b)$，有 $aX + bY = \gcd(a,b)$。 证毕。