最大公因数与辗转相除法

手里有 $48$ 颗糖和 $36$ 块饼干，想分给尽可能多的小朋友。每个人分到的糖一样多，饼干也一样多，两样东西都不能剩。最多能分给多少人？

人数必须同时整除 $48$ 和 $36$。分给 $6$ 人，每人 $8$ 颗糖、$6$ 块饼干，当然可以；分给 $12$ 人，每人 $4$ 颗糖、$3$ 块饼干，也可以。还能再多吗？这个问题的答案，藏在两个数共有的因数里。

上一章，我们把整数拆成了素数，知道每个正整数的素因数配方是确定的。现在要把两个配方放在一起，看看它们究竟共享多少东西。不过，最让人意外的地方在后面：要找最大的共同因数，我们竟然可以完全不分解素因数，只做几次带余除法；找到答案后，还能用原来两个数的整数倍把它“凑”出来。

从共同的因数里挑出最大的

先把这个小例子算清楚。$48$ 的正因数是 $1,2,3,4,6,8,12,16,24,48$；$36$ 的正因数是 $1,2,3,4,6,9,12,18,$。共同出现的是：

其中最大的是 $12$，所以最多分给 $12$ 人。这里要分清“人数最多”和“每个人拿得最多”：如果追求每个人拿得最多，分给一个人就行了。最大公因数解决的是前一个问题。

对于不全为零的整数 $a,b$，同时整除它们的正整数叫作它们的正公因数，其中最大的一个叫作最大公因数，也叫最大公约数，记作 $\gcd(a,b)$。于是：

这个“最大”一定找得到吗？$1$ 总是一个公因数，所以候选不会为空；如果 $a\ne0$，那么它的正因数不会超过 $|a|$，因此共同的正因数只有有限多个。有限个候选里，总能挑出最大的。若 $a=0$，就用非零的 $b$ 做同样的判断。

交换两个数的顺序不会改变候选，改变正负号也不会改变它们的正因数。因此：

例如 $\gcd(-48,36)=12$。若 $a\ne0$，任何 $a$ 的正因数都整除 $0$，所以 $\gcd ($。至于两个数都是 ，所有正整数都是公因数，按“最大正公因数”的说法没有答案；本课程另外约定 ，让后面的计算规则保持统一。这项约定不表示 是一个正公因数。

互质说的是两个数之间的关系

如果 $\gcd(a,b)=1$，就说 $a,b$ 互质。$8$ 和 $9$ 都是合数，却互质，因为一个只含素因数 $2$，另一个只含素因数 $3$。反过来，两个数即使都是素数，也要看是否相同： 和 就不互质。

相邻的两个正整数一定互质。理由很短：任何同时整除 $n$ 和 $n+1$ 的正整数，也整除它们的差 $1$，只能是 $1$。也就是：

记住这个证明里的动作：遇到两个数，不一定要盯着它们本身，它们的差可能更好处理。辗转相除法正是把这个动作做得更彻底。

已经知道素因数时，怎样找共同部分

素因数分解法：每种素数能拿几份

上一章的唯一分解，在这里马上有了用途。比如：

一个公因数最多能拿两个 $2$，因为 $36$ 只提供两个；最多能拿一个 $3$，因为 $48$ 只提供一个。因此最大的共同部分是：

一般地，把两个正整数涉及的素数统一写成 $p_1,\ldots,p_k$，缺少某种素数的一边补上指数 $0$。若：

那么：

这不只是一个方便记忆的口诀。公因数中的每个素数指数，都必须同时不超过 $a$ 和 $b$ 中对应的指数，所以不能超过两者的较小值；把这些较小值全部取到，得到的数又确实同时整除 $a,b$。任何别的正公因数都整除这个数，因此也不会比它更大。

例如：

$5$ 和 $7$ 各自在另一边缺席，指数较小值是 $0$，所以不会出现在答案中。

短除法：把共同部分分次取出来

短除法做的是同一件事，只是不用先把两个数分别分解到底。仍然从 $48,36$ 出发，每次选一个大于 $1$ 的公因数，把两边一起除掉：

最后 $4,3$ 互质，共同部分已经取尽，前面取出的因数相乘就是 $2\times2\times3=12$。

为什么可以连乘？由刚才的指数规则，对正整数 $k,u,v$，把两数同时乘以 $k$，每种素数的共同指数也相应增加，故：

短除法每做一次，就是把这个等式反向使用一次。选的公因数可以是素数，也可以是合数，关键是每一步都要同时整除两边，而且最后剩下的两个数必须互质。如果在 $12,9$ 就停下，只把前面两个 $2$ 相乘得到 $4$，它虽然是公因数，却还没有取到最大。

这两种方法适合因数容易看出的数。可如果数字变成十几位，连第一个素因数都不好找，难道求最大公因数也要跟着卡住？

辗转相除：数字变小，公因数一个也没变

先试着算 $\gcd(252,105)$。用带余除法得到：

想想看，一个数如果整除 $252$ 和 $105$，那么它也一定整除 $252-2\times105=42$。因此，原来那两个数的每个公因数，都还是 $105,42$ 的公因数。

但这只证明了“原来的没有丢”，还要检查有没有新混进来的。反过来，若一个数整除 $105$ 和 $42$，它也整除 $2\times105+42=252$。所以新的一对数也没有增加公因数。两边找的根本就是同一批候选，于是：

接着算：

因此：

三次除法就结束了。整个过程里，我们既没列因数，也没试除素数，只是不断把问题换成更小的一对数。

换一对数，$48=18\times2+12$、$18=12+6$、$12=6\times2+0$，同样得到 。下面的图把每一步保留下来的两个数连在了一起，可以顺着它再走一遍。

为什么可以反复这样做

把例子里的数字换成字母。对 $a\ge b>0$，写出：

如果 $d\mid a$ 且 $d\mid b$，由 $r=a-bq$ 得 $d\mid r$；如果 且 ，由 得 。这两个方向合在一起证明：

于是每次求出余数后，用原来的除数和余数组成下一对，继续做带余除法。这就是辗转相除法，也叫欧几里得算法。一般整数先取绝对值，必要时交换顺序；若其中一个已经是 $0$，直接返回另一个数即可。

证明算法可靠，还差一件事：它会不会永远算下去？不会。只要没有出现 $0$，新的余数就是比前一个除数更小的正整数。这样的数列严格递减，而最初除数以下只有有限个正整数，不能无限下降。因此某一步余数必为 $0$。此时一对数是 $(d,0)$，它的最大公因数是 $d$；每一步又都保留最大公因数，所以最初的答案也是 $d$。

它为什么通常很快

正余数严格递减，已经足够证明算法会停，但还不能解释它为什么快。再多看一步：设某次除法的除数是 $b$，余数是 $r$。如果 $r\le b/2$，这一步已经把较小的数至少减半；如果 $r>b/2$，下一次用 $b$ 除以 $r$ 时商只能是 ，新余数是 。

也就是说，至多两次除法，较小的数就至少减半。把一个大数反复减半，不需要多少轮就能到 $1$。这解释了为什么求 GCD 往往比分解素因数省事。这里比较的是除法次数；每次对大整数做除法本身仍然需要计算时间。

倒着走一遍，最大公因数就被凑出来了

刚才算出 $\gcd(252,105)=21$，现在多问一句：只允许拿 $252$ 和 $105$ 的整数倍相加，能不能得到 $21$？它比两个数都小，好像不太可能。允许负整数系数以后，事情就不同了。

从出现 $21$ 的那一步开始回代：

确实有 $-504+525=21$。这不是碰巧凑对了；我们只不过把每个余数换回它是怎样产生的。

裴蜀定理说：对不全为零的整数 $a,b$，存在整数 $x,y$，使得：

这里的 $ax+by$ 叫作 $a,b$ 的整数线性组合，$x,y$ 叫作一组裴蜀系数。系数可以为正、为负，也可以为 $0$。

为什么一定凑得到

一开始，$a=1a+0b$、$b=0a+1b$ 已经是整数线性组合。每个新余数都是“前面一个数减去另一个数的整数倍”。如果前面两个数都能写成 $a,b$ 的整数线性组合，做这样的减法后，结果当然仍然能写成同样的形式。沿着辗转相除的每一步往下推，所有余数都如此，最后那个非零余数——最大公因数——也如此。

这个论证也告诉了我们找系数的办法：把除法等式保留下来，然后从最后一个非零余数开始逐层回代。带着系数一起进行的辗转相除，通常叫作扩展欧几里得算法。若原数带负号，把绝对值的表示中对应系数改号即可；若其中一个是 $0$，例如 $a>0,b=0$，直接用 $a=1a+0b$。

上一章证明素数乘积引理时，我们见过“选出最小的正整数线性组合”的想法。现在可以看清这个最小值是什么了。设 $d=\gcd(a,b)$，因为 $d$ 同时整除 $a,b$，它就整除任何 $ax+by$。所以每个正的整数线性组合都是 $d$ 的正倍数，不可能小于 ；裴蜀定理又保证 自己确实凑得出来。因此：

一个是从“公因数”里挑最大，一个是从“正的组合结果”里挑最小，它们居然挑到了同一个整数。

回代时，始终盯住最初的两个数

再做一个步骤稍长的例子，求 $56,15$ 的裴蜀系数。先正向计算：

所以它们互质。回代时，每次消去一个中间余数：

这里最后两个 $15$ 含义不同：一个是系数，一个是原数。验算 $-4\times56+15\times15=-224+225=1$，就能确认一组系数是 $(-4,15)$。不要在还剩 或 时就停下来；我们要的最终形式只能包含最初的 和 。

互质为什么能让整除变得简单

裴蜀定理首先补上了一个容易被误认为显然的性质：每个公因数都整除最大公因数。一个数“比另一个数小”本来并不意味着它能整除另一个数，这里需要理由。若 $c\mid a$ 且 $c\mid b$，那么它整除 $ax+by$，取裴蜀表示便得到 $c\mid\gcd(a,b)$。

特别地，两个整数互质，等价于能用它们的整数线性组合凑出 $1$。一个方向由裴蜀定理给出；另一个方向也要说清楚：若 $ax+by=1$，那么任何正公因数都整除 $1$，所以最大公因数只能是 $1$。

从乘积里消去一个互质的因子

设 $a\ne0$，且 $\gcd(a,b)=1$。如果 $a\mid bc$，能否推出 $a\mid c$？可以。因为存在整数 使 ，两边乘以 ：

左边第一项显然被 $a$ 整除，第二项也被 $a$ 整除，因为已知 $a\mid bc$。于是它们的和 $c$ 被 $a$ 整除。这就是互质条件下的整除消去性质：

互质条件不能丢。$6\mid3\times2$，但 $6\nmid2$；因数 $3$ 在这里承担了 $6$ 所需的一部分，不能直接消去。上一章的素数乘积引理也是这件事的特例：若素数 $p$ 不整除 $b$，那么 ，于是 就迫使 。

另一个常用结果也随之而来：若非零整数 $a,b$ 互质，且都整除 $c$，那么 $ab\mid c$。写 $c=ak$，由 $b\mid ak$ 和 得 ，再写 ，便有 。没有互质条件时， 和 都整除 ，它们的乘积 却不整除 。共同因数会让“直接相乘”重复计算一部分，这正是下一章要继续处理的问题。

分数为什么除以 GCD 就约到了底

对整数 $a,b$，其中 $b\ne0$，设 $d=\gcd(a,b)>0$。把分子分母都除以 $d$，分数的值不变：

剩下两数一定互质。假如它们还有一个大于 $1$ 的正公因数 $k$，那么 $dk$ 就同时整除 $a,b$，而 $dk>d$，这与 $d$ 最大矛盾。所以：

例如 $\gcd(1155,693)$ 可由 $1155=693+462$、$693=462+231$、$462=2\times231$ 得到 ，因此 。这不是只找到了一次可用的约分，而是保证约完以后不再有大于 的共同因数。对于 的情况，同样得到 或 ；通常再把分母整理为正数即可。

哪些整数能由两个数凑出来

既然能凑出 GCD，那么别的整数呢？比如同样使用 $252$ 和 $105$，$252x+105y=42$ 有整数解吗？$252x+105y=20$ 呢？

前面已经知道所有整数线性组合都是 $21$ 的倍数，所以 $20$ 无论如何都不可能。$42$ 则可以：把 $-2\times252+5\times105=21$ 乘以 $2$，便得到一组解 。

一般地，给定不全为零的整数 $a,b$，令 $d=\gcd(a,b)$。二元一次整数方程：

有整数解的充要条件是 $d\mid c$。必要性来自 $d$ 整除左边的每一项；充分性来自裴蜀定理：若 $au+bv=d$ 且 $c=kd$，那么 $x=k$ 就是一组解。

找到一组以后，怎样找到全部

先设 $a,b$ 都非零，并已找到一组特解 $(x_0,y_0)$。把 $x$ 增加 $b/d$，同时把 减少 ，方程左边的变化是：

因此对任意整数 $t$，都有一组解：

这会不会漏解？设 $(x,y)$ 是任意一组解，减去特解满足的方程，再除以 $d$：

刚才已经证明 $a/d,b/d$ 互质。右边被 $b/d$ 整除，左边也就如此，用互质消去性质得 $b/d\mid x-x_0$。所以必有整数 $$ 使 ，代回后得到 。任意解都落在上面的式子里，因此它就是全部整数解。

如果有一个系数为 $0$，直接处理更简单。例如 $a\ne0,b=0$ 时，有解就意味着 $a\mid c$，此时 $x=c/a$， 可以是任意整数。若 ，方程变成 ： 时所有整数对都是解， 时无解。这一情况单独判断，不使用除以 的公式。

整数解不一定是实际问题允许的解

每袋装 $6$ 个或 $9$ 个饼干，要装好 $30$ 个，两种袋子各用多少袋？设袋数为 $x,y$，得到 $6x+9y=30$。因为 $\gcd (6,9)$ 整除 ，有整数解。容易找到 ，所以全部整数解为：

袋数还必须非负。由 $2+3t\ge0$ 得整数 $t\ge0$，由 $2-2t\ge0$ 得 $t\le1$，因此只剩 ，对应 和 。如果题目要求两种袋子都使用，就只能选 。

相邻的斐波那契数，为什么一直互质

数列 $1,1,2,3,5,8,13,21,34,55,\ldots$ 有个简单规则：从第三项开始，每一项等于前两项之和。它叫作斐波那契数列，英文是 Fibonacci 数列。约定 $F_1=F_2=1$，则 。

沿着数列往后看，数字越来越大，可相邻两项的 GCD 始终是 $1$。为什么？因为减掉前一项，就退回再前一项：

对 $n\ge2$ 反复使用这个等式，最终退到 $\gcd(F_2,F_1)=\gcd(1,1)=1$； 时本来就是这一对。于是所有相邻两项都互质。

例如对 $55,34$ 做辗转相除，非零余数依次是 $21,13,8,5,3,2,1$，最后 $2=2\times1+0$。它几乎逐项倒着走回去了。这也解释了为什么这种数会让辗转相除走较多步骤：连续许多步的商都是 ，每次只减去一份除数。算法依然会停，也仍满足前面“至多两步至少减半”的估计，只是不会像遇到一个很大的商那样，一步就把数字大幅缩小。

试着把几条线索接起来

下面的题目分别检查计算、回代、条件判断和证明。先自己做，再展开解答；算出一个公因数以后，也要说明它为什么是最大的。

练习一：剪绳子与最大段长

两条绳子分别长 $84$ 厘米、$56$ 厘米，要剪成整数厘米长的相等小段，两条都不能剩。每段最长多少厘米，一共得到多少段？

练习二：求 GCD，并回代验证

用辗转相除求 $\gcd(414,156)$，再把它写成 $414x+156y$，给出一组整数 $x,y$。

练习三：不用同余符号判断一个 GCD

已知 $\gcd(a,6)=2$、$\gcd(b,6)=3$，求 $\gcd(a+b,6)$。

练习四：从一组解到全部解

分别判断 $18x+30y=7$ 与 $18x+30y=42$ 是否有整数解；若有，求全部整数解，并找出其中的非负整数解。

练习五：从互质推广到乘积

设 $a,b,c$ 为正整数，且 $\gcd(a,c)=\gcd(b,c)=1$。证明 $\gcd(ab,c)=1$。

练习六：沿数列倒退

约定 $F_1=F_2=1$。指出 $610,987$ 分别是第几项，并用辗转相除说明它们互质。

从共同因数走向共同倍数

回到开头的分糖问题，$12$ 同时描述了两件事：它是 $48,36$ 能共同容纳的最大分组人数，也是这两个数通过整数线性组合能得到的最小正数。素因数分解让我们看见共同部分，辗转相除把它算出来，回代则给出了它由原数构成的具体方式。

下一章把问题换一个方向：如果两种包装分别装 $48$ 件和 $36$ 件，要让同一批物品使用任何一种包装都恰好装完，至少需要多少件？这次要找的数必须被 $48$ 和 $36$ 同时整除，我们要寻找的是最小公倍数。刚才对“共同部分”的理解，会帮助我们避免把两数相乘时的重复部分也算进去。

因此 GCD 是 $6$。逐层回代：

所以可取 $x=-3,y=8$。验算为 $-1242+1248=6$。另一方面，$414/6=69$、$156/6=26$，而回代等式除以 $6$ 给出 $-3\times69+8\times26=1$，也验证了约去 $6$ 后两数互质。

代回得 $18(-1+5t)+30(2-3t)=42$，所有参数项恰好抵消。要非负，就必须同时有整数 $t\ge1$ 和 $t\le0$，不可能。所以第二个方程有无穷多整数解，却没有非负整数解。

这就把 $1$ 写成了 $ab,c$ 的整数线性组合，所以它们互质。这里并不要求 $a,b$ 彼此互质；它们可以共享素因数，只要这些素因数没有出现在 $c$ 里。

最后一个非零余数是 $1$，所以 $\gcd(987,610)=1$。结果也与相邻斐波那契数互质的证明一致。