最大公因数

上一篇我们深入研究了素数——那些乘法世界里无法再拆分的"原子"，并用算术基本定理确立了每个正整数的唯一素因数分解。今天我们要把这把"素数钥匙"用在一个新的问题上：当两个整数放在一起，它们之间存在多大的"公共尺度"？准确地回答这个问题，需要引入本篇的核心概念——最大公因数（Greatest Common Divisor，简称 GCD）。

最大公因数的重要性远超它的定义看起来那么简单。它是分数约分的数学根基，是初中数论中公因数理论的枢纽，也是密码学、计算机算法与代数理论中反复出现的基本工具。欧几里得在公元前三世纪就完整地写下了求 GCD 的算法，并在两千多年后的今天依然被所有主流编程语言直接调用——这种跨越时代的有效性，值得我们用足够的耐心把它理解透彻。

从一个分配问题说起

假设你有 $48$ 颗糖和 $36$ 块饼干，要分给一群小朋友，要求每个人拿到的糖和饼干一样多，而且必须全部分完、不允许有剩余。那么每人最多能分到多少份？

换个角度想：我们需要找一个正整数 $d$，它既整除 $48$，又整除 $36$，而且要尽量大。$48$ 的正因数有 $1, 2, 3, 4, 6, 8, 12, 16, 24, 48$；$36$ 的正因数有 $1, 2, 3, 4, 6, 9, 12, 18, 36$。把两个列表对比，公共的有 $1, 2, 3, 4, 6, 12$，其中最大的是 $12$。确认一下：$48 = 12 \times 4$，$36 = 12 \times 3$，每人分 $12$ 份，两种零食都恰好分完，没有剩余。这就是"最大公因数"在实际场景中的面目——找到两数共同的最大"量尺"。

最大公因数的定义与基本性质

有了直觉图像，正式的定义就水到渠成了。

定义里有几个边界情形值得单独说清楚，以免日后踩坑。最大公因数对于参数的顺序是无所谓的，$\gcd(a, b) = \gcd(b, a)$，因为两者的公因数集合完全相同。对于负数，$\gcd(a, b) = \gcd(|a|, |b|)$，因为一个数的因数集合与其绝对值的因数集合相同。对于零，（其中 ），因为 能被任何非零整数整除，所以 的所有因数都是 与 的公因数，最大的当然是 本身。至于 ，不同教材处理不一，通常建议不去定义它，遇到时按具体约定走。

最大公因数满足几条值得内化的核心性质，$\gcd(a,b)$ 整除 $a$ 也整除 $b$，这是"公因数"二字的字面含义；更深刻的是它的"最大性"——若 $d$ 是 $a$ 和 $b$ 的任意公因数，则 $d\mid \gcd (a,b)$，即最大公因数统领所有公因数。这两条性质合在一起，意味着 不仅是公因数中最大的，而且是所有其他公因数的"上司"——任何公因数都能整除它。 此外， 说明放大两个数的公因数相当于按比例放大 GCD； 说明对其中一个数加上另一个的任意整数倍，GCD 不变——这正是辗转相除法的数学依据。

互质：GCD 等于 1 的特殊关系

最大公因数等于 $1$ 的情形有独立的名字和丰富的内涵，值得单独一节来介绍。若 $\gcd(a, b) = 1$，我们说 $a$ 与 $b$ 互质（coprime，或 relatively prime）。互质是两个数之间的关系，而不是某个数自身的属性——$8$ 和 $9$ 各自都是合数，但 ，它们彼此互质，合数之间完全可以互质。

有一个优雅的规律：相邻两个正整数永远互质，即 $\gcd(n, n+1) = 1$ 对所有正整数 $n$ 成立。证明是直接的：设正整数 $d$ 同时整除 $n$ 和 $n+1$，则 也整除它们的差 ，而唯一能整除 的正整数就是 本身，故 。这个论证本质上用的是整除的线性性——公因数必定整除两数的任意线性组合，特别是差——这是后续很多证明里反复出现的基本逻辑。

互质的重要性还体现在一条关键性质上：若 $\gcd(a, b) = 1$ 且 $a \mid bc$，则 $a \mid c$。这条定理叫做"欧几里得引理的基本形式"，是整除理论中的核心工具，后续的百射定理、素数乘积整除性等都以它为基础，我们在例题中会给出完整证明。

三种计算方法：直觉、速度与结构

求最大公因数有三种主要方法，它们各有侧重：短除法给直觉，辗转相除法给速度，素因数分解法给结构。理解三者各自适用的场合，比只会一种方法重要得多。

短除法：适合入门的直觉练习

短除法的思路是反复用公因数去除两数，直到两个商互质为止，左侧用过的因数连乘即为 GCD。以 $\gcd(48, 36)$ 为例，先用 $2$ 除两次，再用 $3$ 除一次，得到商 $4$ 和 $3$，两者互质，停止。左侧的因数 $2 \times 2 \times 3 = 12$ 就是答案。短除法的优点是直观，便于解释给初学者；缺点是依赖"每一步恰好选到公因数"的直觉，数字稍大时容易漏掉某些因子，不够可靠。

辗转相除法：两千年都没过时的算法

辗转相除法（欧几里得算法）是数学史上最早被严格记录的算法之一，欧几里得在公元前约 $300$ 年的《几何原本》第七卷中已有完整描述，中国的《九章算术》中也以"更相减损术"的形式独立发现了类似思想。它的核心等式简洁而深刻：

$\gcd(a, b) = \gcd(b,\ a \bmod b)$

其中 $a \bmod b$ 是 $a$ 除以 $b$ 的余数。这个等式的正确性不难证明：设 $a = bq + r$（带余除法），若正整数 $d$ 同时整除 和 ，则它也整除 ；反过来，若 同时整除 和 ，则它也整除 。因此 的公因数集合与 的公因数集合完全相同，最大值自然也相同。这就是等式成立的根本原因——不是技巧性的变形，而是公因数集合的完全等价。

以 $\gcd(252, 105)$ 为例：$252 = 105 \times 2 + 42$，$105 = 42 \times 2 + 21$，。余数序列 ，最后的非零余数是 ，故 。用素因数分解验证：，，公共素因子之积为 ，吻合。

辗转相除法的深层价值在于它的效率。数学家拉梅（Lamé）在 $1844$ 年证明，求 $\gcd(a,b)$ 所需的除法次数不超过较小数的十进制位数的五倍。对于现代计算机处理的数百位整数，其他方法（如先做素因数分解）完全无法胜任，而辗转相除法依然高效运转。这正是它"赢了两千年"的根本原因。

素因数分解法：理解结构而非快速计算

若已知 $a = p_1^{\alpha_1} p_2^{\alpha_2} \cdots p_k^{\alpha_k}$ 和 （缺的素因子指数取零），则

$\gcd(a, b) = p_1^{\min(\alpha_1,\beta_1)} \cdot p_2^{\min(\alpha_2,\beta_2)} \cdots p_k^{\min(\alpha_k,\beta_k)}$

直觉上，$\gcd$ 里每个素因子的指数是两数中该指数的较小值——公因数必须整除两数，所以每个素因子的指数不能超过两数中该指数的最小值，而这个最小值恰好是能达到的最大值。这个公式更多用于"理解结构"和"证明性质"，因为对大数而言，素因数分解本身就比辗转相除法慢得多，不适合作为实用的计算工具。

裴蜀定理：GCD 隐藏的线性表示能力

法国数学家艾田·裴蜀（Étienne Bézout，1730—1783）证明了关于最大公因数最令人惊喜的一条定理，它把 GCD 与整数的线性组合联系了起来：

这里 $x, y$ 被称为裴蜀系数（Bézout coefficients），可以是负数，且不唯一——满足条件的整数对 $(x, y)$ 有无穷多个。裴蜀定理最重要的特例是：$\gcd(a, b) = 1$ 当且仅当存在整数 $x, y$ 使得 $$。这个充要关系在证明时极为有用：想证明两数互质，就去构造满足条件的 ；反过来，已知互质，就能"召唤"线性表示来处理整除推导。

如何找到裴蜀系数？用辗转相除法跑完所有步骤后，从最后一步向前"倒代"即可。这个过程叫做扩展欧几里得算法，是密码学中 RSA 算法求模逆元的核心步骤。以 $\gcd(252, 105) = 21$ 为例：正向步骤给出 $42 = 252 - 105 \times 2$ 和 $21 = 105 - 42 \times 2$，将前者代入后者得

$21 = 105 - (252 - 105 \times 2) \times 2 = 105 \times 5 - 252 \times 2$

所以 $252 \times (-2) + 105 \times 5 = 21$，裴蜀系数为 $x = -2, y = 5$。验算：$-504 + 525 = 21$，正确。

利用 GCD 理解约分的本质

裴蜀定理有一个优美的推论，揭示了分数约分背后的数学结构：若 $\gcd(a, b) = d$，则 $\gcd\!\left(\dfrac{a}{d}, \dfrac{b}{d}\right) = 1$。也就是说，把两个数分别除以它们的最大公因数，得到的两个数必然互质。这正是分数约分的本质：把分子和分母同时除以 GCD，得到最简分数，新的分子分母互质，无法再继续约分。从这个角度看，"约分到最简"并非偶然，而是由最大公因数的结构性质所保证的必然结果。

例题精讲

例题一：辗转相除法的完整流程

题目：用辗转相除法求 $\gcd(1155, 693)$，并验证结果。

例题二：扩展欧几里得算法求裴蜀系数

题目：求整数 $x, y$ 使得 $56x + 15y = \gcd(56, 15)$。

例题三：互质条件下的整除传递

题目：证明：若 $\gcd(a, b) = 1$ 且 $a \mid bc$，则 $a \mid c$。

例题四：素因子分解法求 GCD

题目：用素因数分解法求 $\gcd(2^3 \times 3^4 \times 5^2,\; 2^5 \times 3^2 \times 7)$。

例题五：实际应用场景

题目：两段绳子，一段长 $84\,\text{cm}$，另一段长 $56\,\text{cm}$。要把两段绳子都剪成等长的小段，不允许有剩余，每小段最长可以是多少厘米？

例题六：约分即是除以 GCD

题目：已知 $\gcd(a, b) = d$，证明 $\gcd\!\left(\dfrac{a}{d}, \dfrac{b}{d}\right) = 1$。

一个迷人的极端情形：Fibonacci 数列的 GCD

Fibonacci 数列 $1, 1, 2, 3, 5, 8, 13, 21, 34, 55, \ldots$ 隐藏着一条与辗转相除法深度关联的定理：相邻两个 Fibonacci 数永远互质，即 $\gcd(F_n, F_{n+1}) = 1$ 对所有 成立。证明并不难——对 反复用辗转相除法，最终的余数序列恰好就是 Fibonacci 数列本身逆序往前推，最终终止于 。

更一般的结论是 $\gcd(F_m, F_n) = F_{\gcd(m,n)}$，即 Fibonacci 数的公因数结构与下标的公因数结构完全对应。当你对 Fibonacci 数运行辗转相除法时，它会用尽可能多的步数，因为每步余数只减少一个 Fibonacci 项——这正是辗转相除法理论上需要最多步数的"最坏情形"。拉梅（Lamé） 年证明辗转相除步数上界时，正是用 Fibonacci 数列构造了极端情形。

练习

练习一：用辗转相除法求 $\gcd(987, 610)$，并说明这两个数在 Fibonacci 数列中的位置（提示：$610 = F_{15}$，$987 = F_{16}$），验证你的计算结果与 Fibonacci GCD 定理是否吻合。

练习二：已知 $\gcd(a, 6) = 2$ 且 $\gcd(b, 6) = 3$，求 $\gcd(a + b, 6)$（提示：先分别确定 和 模 的余数范围）。

练习三：证明：若 $p$ 是素数且 $p \mid a^2$，则 $p \mid a$（利用裴蜀定理的推论，或直接用本篇例题三的结论）。

要点收束

最大公因数是整除理论的核心节点，它把"两个数的公共因数"这个概念提炼为一个精确的数学对象。三种计算方法各有侧重：短除法提供直觉入口，辗转相除法提供两千年实战检验的效率保证（核心等式 $\gcd(a,b)=\gcd(b,a \bmod b)$ 的本质是公因数集合的完全等价），素因数分解法提供结构性的理解（每个素因子取指数的较小值）。裴蜀定理则揭示了 GCD 的线性表示能力：$\gcd(a,b)$ 是所有整数线性组合 中最小的正值，而 与 有整数解之间的充要等价，是后续大量证明的起手式。把 GCD 与互质、约分、整除传递联系起来理解，比孤立地记住若干性质更有价值，因为这些联系揭示的是整除理论内在的统一结构。下一篇，我们把目光转向与 GCD 互为镜像的对象——最小公倍数，看看两者如何从不同方向共同刻画两个整数之间的数量关系。

$15 = 11 \times 1 + 4$，即 $4 = 15 - 11 \times 1$……(B)

$11 = 4 \times 2 + 3$，即 $3 = 11 - 4 \times 2$……(C)

$4 = 3 \times 1 + 1$，即 $1 = 4 - 3 \times 1$……(D)

$3 = 1 \times 3 + 0$，终止。故 $\gcd(56, 15) = 1$，两数互质。

验证：$610 = F_{15}$，$987 = F_{16}$，$\gcd(F_{15}, F_{16}) = F_{\gcd(15,16)} = F_1 = 1$（因为相邻整数必然互质，$\gcd(15,16) = 1$），与计算结果吻合。注意辗转相除走了 $14$ 步，体现了 Fibonacci 数是辗转相除"最慢情形"的结构性原因。

由 $\gcd(b, 6) = 3$，知 $3 \mid b$ 但 $2 \nmid b$。所以 $b \equiv 3 \pmod{6}$（奇数中 $3$ 的倍数模 $6$ 余 $3$）。

取 $a \equiv 2 \pmod{6}$ 时：$a + b \equiv 2 + 3 = 5 \pmod{6}$，$\gcd(5, 6) = 1$，故 $\gcd(a+b, 6) = 1$。

取 $a \equiv 4 \pmod{6}$ 时：$a + b \equiv 4 + 3 = 7 \equiv 1 \pmod{6}$，$\gcd(1, 6) = 1$，故 $\gcd(a+b, 6) = 1$。

两种情况下 $\gcd(a+b, 6) = 1$，即 $a+b$ 与 $6$ 互质。

更简洁的写法：由 $p$ 是素数，$\gcd(p, a)$ 要么是 $1$ 要么是 $p$。若 $\gcd(p,a) = p$，结论已成立。若 $\gcd(p,a)=1$，则由 $p \mid a \cdot a$ 和互质整除传递，得 $p \mid a$，同样成立。这个结论是"$\sqrt{p}$ 是无理数"的关键步骤，一般课本用它证明 $\sqrt{2}$ 不是有理数：若 $\sqrt{2} = m/n$ 最简，则 $2n^2 = m^2$，故 $2 \mid m^2$，由本定理得 $2 \mid m$，设 $m = 2k$，代入得 $2n^2 = 4k^2$，即 $n^2 = 2k^2$，故 $2 \mid n^2$，由本定理得 $2 \mid n$，与 $m/n$ 为最简分数矛盾。