最大公因数

什么是最大公因数？

先说结论：最大公因数，就是两个数共同拥有的“最大公用尺子”。

比如 $48$ 和 $36$。

如果你想用同一种长度去量它们，而且都要刚好量完，那么 $12$ 就是能做到这件事的最大长度。

所以：

这就是最大公因数，英文叫 Greatest Common Divisor，常写作 GCD。它听起来像一个很基础的概念，但真的很常用。

分数约分要用它。判断两个数是不是互质要用它。后面学最小公倍数、同余、算法，甚至密码学，也绕不开它。

所以这部分我们不用追求一口气背完所有性质。我们先把它“看懂”，再谈计算。

从一个分配问题说起

假如你手里有 $48$ 颗糖和 $36$ 块饼干，现在要分给一些小朋友。

要求是：

• 每个人拿到的糖一样多
• 每个人拿到的饼干也一样多
• 糖和饼干都不能剩
• 想让每个人拿到的“份数”尽量大

这个问题其实就在问：

有没有一个数，既能整除 $48$，又能整除 $36$，而且这个数要尽量大？

我们列一下因数。

$48$ 的正因数有：

$36$ 的正因数有：

两个列表里共同出现的数是：

最大的就是 $12$。

所以 $48$ 和 $36$ 的最大公因数是 $12$。

验证一下：

刚刚好，没有剩余。

最大公因数的定义

现在让我们把刚才的直观理解写成正式定义。

比如：

读作“$48$ 和 $36$ 的最大公因数是 $12$”。

这里有几个小坑，提前说一下。

第一，顺序不重要。

因为两边找的是同一批公因数。

第二，负号不影响最大公因数。

比如：

第三，和 $0$ 搭配时要小心。

如果 $a\neq 0$，那么：

因为任何非零整数都能整除 $0$，所以 $a$ 和 $0$ 的最大公因数就是 $|a|$。

$\gcd(0,0)$ 的情况我们一般不讨论，在不同的地方可能有不同约定。

最大公因数有一个很重要的特点：它不只是“最大的公因数”，它还会被所有公因数整除。

换句话说，如果 $d$ 是 $a$ 和 $b$ 的任意公因数，那么：

比如 $48$ 和 $36$ 的公因数有 $1,2,3,4,6,12$。它们都能整除 $12$。

这就是 GCD 很好用的原因。

互质：最大公因数等于 1

如果两个数的最大公因数是 $1$，我们说它们互质。

也就是：

互质不代表两个数都是素数。这个点很容易让人产生误会。比如 $8$ 和 $9$。

$8$ 是合数，$9$ 也是合数。

但它们没有共同的正因数，除了 $1$。

所以：

它们互质。

相邻的两个正整数也一定互质。

比如 $14$ 和 $15$，$99$ 和 $100$。

为什么？

如果某个数 $d$ 同时整除 $n$ 和 $n+1$，那它也会整除它们的差：

能整除 $1$ 的正整数只有 $1$。

所以：

以后看到“互质”两个字，可以先在脑子里翻译成一句话：

这两个数没有共同的因数，除了 $1$。

怎么求最大公因数

常见方法有三种。先别急着全背下来。我们可以这样理解：

• 短除法：适合入门和手算
• 辗转相除法：最快、最稳、最常用
• 素因数分解法：适合理解结构

短除法：最直观的方法

短除法的思路是：不断找两个数共同能除的因数。

还是看 $48$ 和 $36$。

先都除以 $2$：

再都除以 $2$：

再都除以 $3$：

这时 $4$ 和 $3$ 已经互质了。

所以前面用过的公因数连乘：

答案就是 $12$。

短除法的优点是看得见。缺点也很明显：数字一大，就容易漏因数。所以真正稳定的办法，是下面这个。

辗转相除法：老办法，但是真的能打

辗转相除法，也叫欧几里得算法。

它的核心只有一句：

简单说，就是：

两个数的 GCD，不会因为把“大数”换成“余数”而改变。

为什么？

假设：

如果一个数能同时整除 $a$ 和 $b$，那它也能整除：

反过来，如果一个数能同时整除 $b$ 和 $r$，它也能整除：

所以 $(a,b)$ 和 $(b,r)$ 的公因数其实是同一批。

最大公因数当然也一样。

比如求：

先算：

所以：

继续：

所以：

再继续：

余数到 $0$ 了。

最后一个非零余数是 $21$。

所以：

这套方法很厉害，因为它不用分解质因数。

数字很大时，分解质因数可能很难，但辗转相除法依然很快。

素因数分解法：看结构很清楚

如果两个数已经分解成素因数，那求 GCD 会非常直观。

比如：

共同的素因数是 $3$ 和 $7$。

所以：

更一般地说，如果某个素数在两个数里都出现，就取它出现次数较少的那一边。

比如：

那么：

因为公因数不能比任意一边含有更多的 $2$ 或 $3$。

这个方法适合理解结构。

但如果原数很大，先分解质因数就可能很麻烦。

裴蜀定理：GCD 还能被“凑出来”

这一节看起来会稍微抽象一点，但其实很好理解。

先看一个例子：

神奇的是，$21$ 可以用 $252$ 和 $105$ 凑出来：

也就是说，最大公因数不只是一个结果。

它还能写成这两个数的整数倍相加。

这就是裴蜀定理。

这个定理最常用的特例是：

等价于存在整数 $x,y$，使得：

这句话在证明里非常好用。

看到“互质”，就可以想到“能凑出 $1$”。

怎么找到这个 $x,y$ 呢？

用辗转相除法倒着推。

还是看：

正向计算是：

所以：

又因为：

所以：

把 $42 = 252 - 105 \times 2$ 代进去：

整理：

也就是：

这就是一组裴蜀系数。

约分到底在约什么

很多同学会机械地约分。

比如：

我们知道可以约成：

其实这里做的事情就是：分子和分母同时除以最大公因数。

因为：

所以：

为什么这就到最简了？

因为把两个数都除以它们的 GCD 后，剩下的两个数一定互质。

也就是说：

其中：

所以，“约分到最简”的本质就是：

除掉分子分母最大的共同部分。

例题精讲

例题一：辗转相除法求 GCD

题目：用辗转相除法求 $\gcd(1155,693)$。

例题二：求裴蜀系数

题目：求整数 $x,y$，使得

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

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

这题很典型。

看到互质条件，优先想到裴蜀定理。

例题四：用素因数分解法求 GCD

题目：求

例题五：绳子问题

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

例题六：约分为什么会到最简

题目：已知 $\gcd(a,b)=d$，证明

一个有意思的彩蛋：Fibonacci 数列

Fibonacci 数列是：

它和 GCD 也有关系。

相邻两个 Fibonacci 数永远互质。

比如：

原因其实和辗转相除法很像。

因为每一项都等于前两项之和：

所以用辗转相除法时，余数会一路退回前面的 Fibonacci 数。

最后退到 $1$。

更一般地，还有一个漂亮公式：

这一点你现在不必完全掌握。

你只要知道：GCD 和 Fibonacci 数列之间有很深的联系。

有趣的是，Fibonacci 数列还是辗转相除法的“最慢情况”之一，因为每一步余数都只小一点点。

练习

练习一：用辗转相除法求 $\gcd(987,610)$，并说明这两个数在 Fibonacci 数列中的位置。

练习二：已知 $\gcd(a,6)=2$ 且 $\gcd(b,6)=3$，求 $\gcd(a+b,6)$。

练习三：证明：若 $p$ 是素数且 $p \mid a^2$，则 $p \mid a$。

要点收束

这章的主角是最大公因数。

你可以把它理解成：两个数共同拥有的最大“公用尺子”。

求 GCD 有三种常用视角：

• 短除法：适合初学，直观
• 辗转相除法：适合计算，快而稳
• 素因数分解法：适合理解结构

互质就是最大公因数等于 $1$。

裴蜀定理告诉我们，$\gcd(a,b)$ 可以写成 $ax+by$ 的形式。

约分的本质，就是把分子和分母同时除以它们的最大公因数。

GCD 不是单纯求一个数，它是在问两个整数到底共享了多少“共同部分”。

下一部分我们再看最小公倍数，它和最大公因数刚好从另一个方向描述两个数的关系。

所有公因数中最大的那个，叫做 $a$ 和 $b$ 的最大公因数，记作

所以：

第二个数里：

所以：

所以：

$610$ 和 $987$ 是相邻的 Fibonacci 数，所以它们互质，结果也吻合。

由 $\gcd(b,6)=3$ 可知，$b$ 能被 $3$ 整除，但不能被 $2$ 整除。

所以：

如果 $a \equiv 2 \pmod{6}$，那么：

所以 $\gcd(a+b,6)=1$。

如果 $a \equiv 4 \pmod{6}$，那么：

所以 $\gcd(a+b,6)=1$。

两种情况都一样：

如果 $\gcd(p,a)=1$，由于：

由互质条件下的整除传递可知：

所以不管是哪种情况，都有：

$\square$