整环上的最大公约数理论简介（含饺子醋）

qiminghaonan · 2026-10-05 23:56:47 · 算法·理论

整环上的 \gcd 函数定义为：对于两个元素 a,b，如果存在 x 满足：x \mid a, x \mid b 且对于任意的 y \mid a, y \mid b 都有 y \mid x，则这样的 x 在相伴意义下唯一，可以任取一个记作 \gcd(a,b)。

可见，两个元素的 \gcd 是否存在以及具体值，只和它们的公因数集合有关。进而推出 \gcd 的基本性质：

这里 \sim 理解为同时存在或者同时不存在，且如果存在必然相伴。

UFD 里，因为唯一分解定理，任意两个元素的 \gcd 都存在，并且可以取为若干典范素数的乘积（或者零，当且仅当两个元素均为零）。因此，我们熟知的，整数 \gcd 的那些只涉及乘法的性质都能推广到 UFD。

贝祖定理即对于任意的 a,b，存在 x,y 满足 ax+by=\gcd(a,b)。它涉及加法，在一般 UFD 中不能成立。UFD 加贝祖定理等价于 PID，证明如下：

• 前推后：任取理想 I 和元素 a \in I。根据唯一分解定理，\gcd(a,x) 只有有限种取值，故而 \bigcup_{b \in I} \gcd(a,b) 是有限集，记作 \{d_1, \cdots, d_n\}。取数列 a_0 = 0 以及 a_k = \gcd(a_{k-1}, d_k)，则 I = (a_n)，I 是主理想。根据贝祖定理，a_n 可表为 I 中元素的线性组合，故 a_n \in I, (a_n) \subseteq I；反过来，I 中的任意元素都被 a_n 整除，故 I \subseteq (a_n)。
• 后推前：PID 推出 UFD 是经典结论，不再赘述；令 (a,b) = (d)，则 d \mid a, d \mid b 推出 d \mid \gcd(a,b)；反过来，d \in (a,b) 推出 \gcd(a,b) \mid d。故 d \sim \gcd(a,b)，则 \gcd(a,b) \in (a,b)，即贝祖定理。

令人深思的是，ED 似乎没有带来整除理论中更好的性质。

因此，很多适用于整数的定理是可以推广到 PID 甚至 UFD 的，只要它们的证明只用到了上述性质。举一例：如果 \gcd(a,b) = 1，那么 \gcd(a^m-b^m, a^n-b^n) \sim a^{\gcd(m,n)} - b^{\gcd(m,n)}。它的证明如下，适用于任意的 UFD。

注意到恒等式 $a^m-b^m=a^{m-n}(a^n-b^n)+b^n(a^{m-n}-b^{m-n})$ 且 $\gcd(a^n-b^n,b^n) = \gcd(a^n, b^n) = 1^n = 1$。则 $$\begin{aligned} \gcd(a^m-b^m, a^n-b^n) &= \gcd(a^{m-n}(a^n-b^n)+b^n(a^{m-n}-b^{m-n}), a^n-b^n) \\ &= \gcd(b^n(a^{m-n}-b^{m-n}), a^n-b^n) \\ &= \gcd(a^{m-n}-b^{m-n}, a^n-b^n) \\ \end{aligned}$$

然后是饺子醋：在 P1306 斐波那契公约数 的题解区，可以看到一篇题解，它证明 \gcd(F_m, F_n) = F_{\gcd(m,n)} 的思路大致如下：

记 \varphi = \tfrac{1 + \sqrt 5}{2}, \psi = \tfrac{1 - \sqrt 5}{2} 是斐波那契数列特征方程的两根，则 F_n = \tfrac{\varphi^n-\psi^n}{\varphi-\psi}。于是

&= \gcd\left(\dfrac{\varphi^m-\psi^m}{\varphi-\psi}, \dfrac{\varphi^n-\psi^n}{\varphi-\psi}\right) \\ &= \dfrac{\gcd({\varphi^m-\psi^m}, {\varphi^n-\psi^n})}{\varphi-\psi} \\ &= \dfrac{\varphi^{\gcd(m,n)}-\psi^{\gcd(m,n)}}{\varphi-\psi} \\ &= F_{\gcd(m,n)} \end{aligned}

这是啥？当你注意到 \varphi - \psi = \sqrt 5 的时候，能绷住的是圣人了。不过还是请看到这里的同学不要撤下这篇题解，因为我想留着给文章引流这个式子可以放在性质良好（ED）的 \mathbb Z[\varphi] 里理解。\psi = 1 - \varphi \in \mathbb Z[\varphi]，表明上述式子里的所有项都在其中；\varphi \psi = -1 表明 \varphi, \psi 都是单位，当然互素，可以把 \gcd 放到指数上。一切都是如此合理！

:::warning[再想想，真的合理吗？]

我们想求 \mathbb Z 里的 \gcd，而上面我们一直在讨论 \mathbb Z[\varphi] 里的 \gcd！我们还没证明这两个是一回事。而且，第三个等号应该改为相伴，才能与 \mathbb Z[\varphi] 里的定理一致。换句话说，我们当前仅仅证明了 \gcd_{\mathbb Z[\varphi]} (F_m, F_n) \sim F_{\gcd(m,n)}，而我们需要的是 \gcd_{\mathbb Z} (F_m, F_n) = F_{\gcd(m,n)}。这将需要以下两个引理。

• 若整环 R_1, R_2 间有同态 \phi，R_1 满足贝祖定理，那么对于任意的 d,a,b \in R_1 满足 d = \gcd_{R_1}(a,b)，都有 \gcd_{R_2}(\phi(a),\phi(b)) 存在，且与 \phi(d) 相伴。
• 代数整数（\mathbb Z 上首一整系数多项式的根）里的有理数只有整数。

第一个引理中，取 R_1 = \mathbb Z, R_2 = \mathbb Z[\varphi], \phi 为典范同态即得 \gcd_{\mathbb Z[\varphi]} (F_m, F_n) \sim \gcd_{\mathbb Z} (F_m, F_n)，再由相伴的传递性知 \gcd_{\mathbb Z} (F_m, F_n) \sim F_{\gcd(m,n)}。然后注意到 x=a+b\varphi 满足方程 x^2-(2a+b)x+(a^2+ab-b^2)，这表明 \mathbb Z[\varphi] 中都是代数整数，故其中有理数只有整数，所以有理单位只有 \pm 1，故而 \mathbb Z[\varphi] 中两个整数的相伴关系即为 \mathbb Z 中的相伴关系。斐波那契数列都是非负，故 \gcd_{\mathbb Z} (F_m, F_n) = F_{\gcd(m,n)}。

然后是这两个引理的证明。

• 设 x = p/q（其中 p,q 互素，q > 0）满足首一整系数一元 n 次方程 x^n + a_{n-1}x^{n-1} + \cdots + a_0 = 0，两边同乘 q^n 得 p^n + a_{n-1}p^{n-1}q + \cdots + a_0q^n = 0，只有第一项不显含 q 故 q \mid p^n。但 p,q 互素所以只能 q = 1。

:::

不过这方法到底还是歪门邪道，因为更强的结论是，对于任意的二阶整系数齐次线性递推数列 a_0 = 0, a_1 = 1, a_n = pa_{n-1}+qa_{n-2} 都有 \gcd(a_m,a_n) = a_{\gcd(m,n)}，证明可以参见 这篇文章。用本文中的方法处理似乎不可避免性质很差的环以及分类讨论，尤其是特征方程有重根的情况完全不知道怎么处理。