最小公倍数

两路公交车刚刚同时从站台出发，一路每隔 $4$ 分钟发一班，另一路每隔 $6$ 分钟发一班。下一次同时发车，需要等多久？

如果把两个间隔乘起来，得到 $24$ 分钟，这个答案倒也不假：到那时，两路车确实都会发车。可你如果真在站台等着，就会发现它们在第 $12$ 分钟已经一起出发过一次了。乘法给出了一个能用的答案，却没告诉我们最早的答案在哪里。

上一章，我们一直在向下找：一个数要能同时整除两个数，最大能有多大？这一章把方向转过来：一个数要能同时被两个数整除，最小能有多小？它叫最小公倍数，记作 $\operatorname{lcm}$ 。我们会看到，这两个方向之间有一条准确的联系，连计算最小公倍数都可以借用刚学过的欧几里得算法。

两个倍数列表，在哪里第一次碰头

先把刚才的发车时间列出来。以两路车同时出发的时刻为第 $0$ 分钟，只看此后的发车：

\begin{aligned} \text{甲路：}&\quad 4,8,12,16,20,24,28,\ldots\\ \text{乙路：}&\quad 6,12,18,24,30,36,\ldots \end{aligned}

第 $12$ 分钟第一次重合，第 $24$ 分钟又重合。如果接着列，会遇到 $36,48,60,\ldots$ 。这些数同时在两个列表里，是 $4$ 和 $6$ 的正公倍数；其中最小的是 $12$ ，所以 $\operatorname{lcm}(4,6)=12$ 。

两行倍数分别列出4与6的正倍数，第一次共同出现的数是12

刚才的发车情境里有个容易被忽略的条件：第 $0$ 分钟是一次共同起点。我们问的是“下一次”，所以要找大于 $0$ 的时间。 $0$ 的确能被 $4$ 和 $6$ 整除，但它代表刚刚发生的那次出发，不能算成等待时间的答案。

把公交情境中的条件抽出来，定义就有了。对正整数 $a,b$ ，若正整数 $M$ 满足 $a\mid M$ 且 $b\mid M$ ，那么 $M$ 是它们的正公倍数。所有正公倍数中最小的那个，就是最小公倍数：

\operatorname{lcm}(a,b) =\min\{M\in\mathbb Z_{>0}:a\mid M,\ b\mid M\}.

这样的数总能找到，因为 $ab=a\cdot b=b\cdot a$ ，它一定是一个正公倍数。既然正公倍数的集合不空，正整数的良序性质就保证其中有最小的一个。这个论证看似简单，却回答了定义背后的问题：我们不是给一个可能不存在的东西起名字。

本章主要讨论正整数。若以后需要把最小公倍数扩展到含 $0$ 的输入，我们约定 $\operatorname{lcm}(a,0)=0$ 。这是一项额外约定，不能把它解释成“ $0$ 和 $a$ 的最小正公倍数”，因为没有正数能写成 $0$ 的整数倍。本章关于正公倍数和正等待时间的论证，都在正整数范围内使用。

列倍数的方法很直观，也可以稍微省些力。求 $\operatorname{lcm}(8,12)$ ，只要依次检查较大数 $12$ 的正倍数： $12$ 不能被 $8$ 整除， $24$ 可以，答案就找到了。检查是从小到大进行的，所以第一个通过检查的数一定最小。不过，若两个数的共同倍数很远，列举就会拖得很长。要从“挨个找”变成“直接构造”，我们得回到素因数分解。

为什么公因数取小指数，公倍数取大指数

先看 $12$ 和 $18$ ：

12=2^2\cdot3,\qquad18=2\cdot3^2.

如果一个正整数能被 $12$ 整除，它的素因数分解中至少要有两个 $2$ 和一个 $3$ ；如果还能被 $18$ 整除，它又至少要有一个 $2$ 和两个 $3$ 。两边的要求叠在一起，就是至少有两个 $2$ 、两个 $3$ 。

这里的“叠在一起”可不是把指数相加。已经准备好的两个 $2$ ，既足以满足 $12$ 对 $2$ 的要求，也足以满足 $18$ 对 $2$ 的要求；不用再额外补一个。逐种素数检查，只保留较高的那项要求，于是得到

\operatorname{lcm}(12,18)=2^2\cdot3^2=36.

我们不妨把最大公因数也放在旁边比较：

数中的素因子	$12$ 的指数	$18$ 的指数	GCD 取的指数	LCM 取的指数
$2$	$2$	$1$	$1$	$2$
$3$	$1$	$2$	$1$	$2$

公因数要同时装得进两个数，指数不能超过任意一边，所以最多取较小的；公倍数要同时容得下两个数的要求，指数不能低于任意一边，所以至少取较大的。于是 $\gcd(12,18)=2\cdot3=6$ ，而 $\operatorname{lcm}(12,18)=2^2\cdot3^2=36$ 。

这个解释依赖前面已经证明的唯一分解。对正整数而言，一个数整除另一个数，等价于它所含的每种素数的指数都不超过另一个数中的指数：如果能够整除，商的素因数分解补上了缺少的部分；如果各项指数都够，逐项相减得到的非负指数就能组成整数商。

为了把规则写成一般形式，列出 $a,b$ 中出现过的全部不同素数 $p_1,\ldots,p_r$ ，写成

a=\prod_{i=1}^{r}p_i^{\alpha_i},\qquad b=\prod_{i=1}^{r}p_i^{\beta_i}.

某个素数只出现在一边，就把另一边对应的指数写成 $0$ 。例如 $30=2\cdot3\cdot5$ 和 $42=2\cdot3\cdot7$ ，要把 $5$ 、 $7$ 都列进来，不能只盯着共有的 $2$ 和 $3$ 。如果 $a=b=1$ ，这里没有素因子，按空乘积等于 $1$ 理解即可。

现在两条公式可以并排写下：

\gcd(a,b)=\prod_{i=1}^{r}p_i^{\min(\alpha_i,\beta_i)},\qquad \operatorname{lcm}(a,b)=\prod_{i=1}^{r}p_i^{\max(\alpha_i,\beta_i)}.

最小公倍数公式为什么确实给出了“最小”？记右边构造出的数为 $L$ 。它的每个指数都够用，所以 $a\mid L$ 、 $b\mid L$ 。而任何正公倍数 $M$ 的对应指数，都不能比这些最大值更小，因此 $L\mid M$ 。既然 $M$ 是 $L$ 的正整数倍，就有 $M\ge L$ 。既证明了它是公倍数，也证明了没有更小的正公倍数。

这个证明还顺手告诉我们一件比“最小”更强的事。

最小公倍数能整除每一个公倍数。若 $L=\operatorname{lcm}(a,b)$ ，那么全部正公倍数恰好是 $L,2L,3L,\ldots$ 。一个正整数 $M$ 同时被 $a,b$ 整除，当且仅当 $L\mid M$ 。

反过来的方向也别漏掉：既然 $a\mid L$ 、 $b\mid L$ ，它们自然也整除 $L$ 的每个整数倍。现在开头公交车在 $12,24,36,\ldots$ 分钟重合，就不只是我们列出的一串巧合了。

两个方向，恰好拼回原来的乘积

我们已经算出 $\gcd(12,18)=6$ ， $\operatorname{lcm}(12,18)=36$ 。把这两个结果相乘，会得到

6\cdot36=216=12\cdot18.

为什么向下找一次、向上找一次，乘起来反而回到了原来的乘积？刚才的指数表已经把原因放在我们眼前了。

对某一个素数 $p$ ，设它在 $a,b$ 中的指数分别是 $\alpha,\beta$ 。GCD 拿走较小的指数，LCM 拿走较大的指数；两者相乘，指数相加，于是

\min(\alpha,\beta)+\max(\alpha,\beta)=\alpha+\beta.

不论两项谁大谁小，较小项加较大项，总还是原来的两项之和。这正是 $ab$ 中 $p$ 的指数。每种素数都如此，唯一分解便给出

\boxed{\gcd(a,b)\operatorname{lcm}(a,b)=ab}\qquad(a,b>0).

12与18的素因数分解，分别取较小指数得到最大公因数6，取较大指数得到最小公倍数36，并验证6×36等于12×18。

不分解素因数，也能把公式证明出来

上一章的互质消去性质也能帮我们完成这件事。这个证明值得走一遍，因为它直接解释了为什么计算时只求 GCD 就够了。

设 $d=\gcd(a,b)$ ，把最大公因数从两个数里提出来：

a=du,\qquad b=dv,\qquad\gcd(u,v)=1.

$u,v$ 为什么互质？如果还有共同因数 $e>1$ ，那么 $de$ 就会同时整除 $a,b$ ，并且比 $d$ 更大，这与 $d$ 的定义矛盾。

候选答案是 $duv$ 。它等于 $av$ ，也等于 $bu$ ，当然是公倍数。接下来取任意正公倍数 $M$ 。由 $a\mid M$ ，可以写成 $M=duk$ ；又因为 $b=dv\mid M$ ，约掉 $d$ 得到 $v\mid uk$ 。现在 $u,v$ 互质，上一章的互质消去性质允许我们推出 $v\mid k$ 。

所以 $k=vq$ ，其中 $q$ 是正整数，进而

M=duvq.

每个正公倍数都是 $duv$ 的倍数，因此它就是最小公倍数。最后代回 $a=du,b=dv$ ：

\operatorname{lcm}(a,b)=duv=\frac{ab}{d} =\frac{ab}{\gcd(a,b)}.

把两个数直接相乘时，共享的那一部分算得多了；除掉一次最大公因数，恰好留下同时满足两边要求所需的部分。这里“共享的部分”有明确数值，就是 $d$ ，并不是看起来重复的数字随手删掉。

真正计算时，先除再乘

求 $\operatorname{lcm}(84,132)$ ，我们不必先分解两个数。先用欧几里得算法求 GCD：

\begin{aligned} 132&=84+48,\\ 84&=48+36,\\ 48&=36+12,\\ 36&=3\cdot12. \end{aligned}

最后一个非零余数是 $12$ ，因此

\operatorname{lcm}(84,132) =\left(\frac{84}{12}\right)\cdot132 =7\cdot132=924.

验算一下， $924=84\cdot11=132\cdot7$ 。这说明整除关系没有算错；而它的最小性来自刚才证明的公式，不能只靠“两边都除得尽”就下结论。

我们把计算顺序特意写成 $(a/\gcd(a,b))\cdot b$ ，因为 $\gcd(a,b)$ 一定整除 $a$ ，第一步不会产生分数，中间数通常也更小。手算时省力，在使用固定范围整数的程序里，也能避免先算 $ab$ 带来的某些中间溢出。不过，先除后乘不能让超出存储范围的最终答案自动变得可存储。

有些输入，可以直接看出答案

若 $a\mid b$ ，那么 $b$ 本身就是公倍数，任何正公倍数又至少是 $b$ ，所以 $\operatorname{lcm}(a,b)=b$ 。例如 $\operatorname{lcm}(9,45)=45$ ，不用再列倍数。

若 $\gcd(a,b)=1$ ，公式则变成 $\operatorname{lcm}(a,b)=ab$ 。例如 $8$ 和 $9$ 都是合数，但互质，因此最小公倍数是 $72$ 。“互质”说的是两数的关系，不要求它们各自是素数。反过来，对正整数，若最小公倍数等于乘积，乘积关系也会迫使 GCD 等于 $1$ 。

还有几个能随手检查的边界： $\operatorname{lcm}(1,a)=a$ ， $\operatorname{lcm}(a,a)=a$ ，并且

\max(a,b)\le\operatorname{lcm}(a,b)\le ab.

左边来自正公倍数至少不小于任一原数，右边来自 $ab$ 本来就是一个正公倍数。算出的答案若比输入中的较大数还小，肯定出了问题。

多个数时，先把两项的要求合在一起

三路车分别每隔 $4,6,9$ 分钟发车，并且刚刚同时出发。我们要找的数必须同时被这三个数整除，定义和两数时完全一样：取所有正公倍数里最小的一个。

既然“同时被 $4,6$ 整除”等价于“被 $12$ 整除”，前两项的要求可以合并成一项。于是

\operatorname{lcm}(4,6,9) =\operatorname{lcm}(\operatorname{lcm}(4,6),9) =\operatorname{lcm}(12,9)=36.

这不是一个只对例子有效的技巧。若 $L=\operatorname{lcm}(a,b)$ ，一个正整数同时是 $a,b,c$ 的倍数，当且仅当它同时是 $L,c$ 的倍数。两边筛选出来的集合相同，最小值自然也相同：

\operatorname{lcm}(a,b,c) =\operatorname{lcm}(\operatorname{lcm}(a,b),c).

更多数也可以一个一个并进来。由于最后的要求始终是“同时被所有输入整除”，先合并哪两个不会改变答案。如果已经有素因数分解，就对每种素数取所有输入中的最大指数。例如

18=2\cdot3^2,\qquad24=2^3\cdot3,\qquad30=2\cdot3\cdot5,

所以

\operatorname{lcm}(18,24,30)=2^3\cdot3^2\cdot5=360.

不过，两数的乘积关系不能原样搬到三数。仍用 $4,6,9$ ，它们的 GCD 是 $1$ ，LCM 是 $36$ ，两者相乘是 $36$ ，而 $4\cdot6\cdot9=216$ ，显然不相等。

问题出在指数上。两个指数里，最小值与最大值刚好包括全部两项；三个指数里，最小值加最大值通常漏掉了中间那项。因此不能把 $\operatorname{lcm}(a,b,c)$ 写成 $abc/\gcd(a,b,c)$ 。

三个数的最大公因数是 $1$ ，不代表它们两两互质。 $4,6,9$ 没有大于 $1$ 的共同因数，但 $4,6$ 共享因数 $2$ ， $6,9$ 共享因数 $3$ 。若多个正整数两两互质，它们的最小公倍数才等于所有数的乘积：每种素数只会出现在一个输入中，取最大指数与相乘累加指数便给出相同结果。

通分时，我们究竟在找什么

看这个计算：

\frac{7}{12}-\frac{3}{8}+\frac{1}{6}.

每个分数都表示若干份同样大的小块，可现在三种小块的大小不同，不能直接把份数加减。通分，就是把它们改写成用同一种大小的小块来计数。

如果只通过给分子、分母同乘正整数来通分，新分母就必须是 $12,8,6$ 的公倍数。取它们的最小公倍数 $24$ ，所需的放大倍数分别是 $2,3,4$ ：

\frac{7}{12}=\frac{14}{24},\qquad \frac{3}{8}=\frac{9}{24},\qquad \frac{1}{6}=\frac{4}{24}.

于是

\frac{7}{12}-\frac{3}{8}+\frac{1}{6} =\frac{14-9+4}{24} =\frac{9}{24} =\frac{3}{8}.

用 $48$ 或 $96$ 作公分母也能算对，只是分子会随之变大。LCM 给出的是所选分母的最小正公倍数，并不保证计算结果已经最简；这里最后仍要用 GCD 把 $9/24$ 约成 $3/8$ 。最小公倍数负责统一分母，最大公因数负责约去共同因子，它们在同一道计算里各做了一件事。

还有一种更省事的情况：原分数本身可以先约分。例如

\frac{6}{8}+\frac{5}{12} =\frac{3}{4}+\frac{5}{12} =\frac{9}{12}+\frac{5}{12} =\frac{7}{6}.

原分母 $8,12$ 的 LCM 是 $24$ ，但先约分后，只需用 $12$ 作公分母。这不矛盾：我们改变了待通分的分母。因此做题时可以先检查约分，再求剩下分母的 LCM，最后检查结果是否还能约分。

周期会重合，但起点不能忘

现在回到公交站。甲、乙、丙三路车分别每 $15,20,30$ 分钟发车，早上 $6{:}00$ 同时发车，之后一直按固定间隔运行。下一次三路同时发车是什么时候？

以 $6{:}00$ 为起点，设经过 $t$ 分钟。三路同时发车要求 $15\mid t$ 、 $20\mid t$ 、 $30\mid t$ ，又因为问“下一次”，所以 $t>0$ 。分解得到

15=3\cdot5,\qquad20=2^2\cdot5,\qquad30=2\cdot3\cdot5,

所以最小正等待时间是

t=\operatorname{lcm}(15,20,30)=2^2\cdot3\cdot5=60.

答案是 $7{:}00$ 。到那时，三路分别走过 $4,3,2$ 个发车间隔，确实同时发车。此后的共同发车时刻是 $8{:}00,9{:}00,\ldots$ ，只要题设的运行规律持续成立。

如果起点错开了，直接算周期的 LCM 就可能答错。仍用 $4$ 分钟与 $6$ 分钟两路车：甲从第 $0$ 分钟开始，乙从第 $2$ 分钟开始。它们的发车时刻是

\begin{aligned} \text{甲路：}&\quad0,4,8,12,16,20,\ldots\\ \text{乙路：}&\quad2,8,14,20,26,\ldots \end{aligned}

第一次共同发车在第 $8$ 分钟，根本不是第 $12$ 分钟。 $12$ 仍然有用：从已经找到的共同发车时刻 $8$ 往后，再过 $12$ 分钟会在 $20$ 重合。也就是说，LCM 能控制共同事件之间的间隔，却未必直接给出相对于任意起点的第一次共同事件。

甚至可能一次也碰不上。若乙改为从第 $1$ 分钟开始，以后在 $1,7,13,19,\ldots$ 发车，这些时刻全是奇数；甲的发车时刻全是 $4$ 的倍数，当然是偶数，两路就不会同时发车。

所以看到周期题，我们先辨清三个条件：周期是否用相同单位表示，是否从一次共同事件开始计时，要求的是下一次的正等待时间还是某个时段里的全部共同事件。若起点错开，必须把这个偏移也保留下来。到下一章，余数会成为记录这种偏移的自然语言。

反过来使用乘积关系，还要验回原条件

已知两个正整数的最大公因数是 $6$ ，最小公倍数是 $180$ ，其中一个数是 $36$ 。另一个数是多少？

设另一个数为 $b$ ，乘积关系给出

36b=6\cdot180=1080,

所以 $b=30$ 。但我们还要把这个候选答案放回两个条件中： $\gcd(36,30)=6$ ，并且

\operatorname{lcm}(36,30)=\frac{36}{6}\cdot30=180.

两项都符合，答案才真正确定。

为什么还要验？因为乘积相同并不能保证 GCD 和 LCM 各自正确。例如，有人声称两个数的 GCD 是 $6$ 、LCM 是 $72$ ，其中一个数是 $12$ 。套乘积关系会得到另一个数 $36$ ，但 $\gcd(12,36)=12$ ， $\operatorname{lcm}(12,36)=36$ ，和题设都不符。因此这组条件无解。乘积关系给的是必要条件，反推题里算出一个正整数，还不能自动证明它满足全部条件。

从 $a=du,b=dv$ 的证明还能看出，若 GCD 是 $d$ ，LCM 是 $L$ ，则 $L=duv$ ，所以一定有 $d\mid L$ 。并且 $uv=L/d$ ， $u,v$ 要互质。这个表示能帮助我们有次序地找出所有可能的数对，而不会把任意一对因数都误当成答案。

留几道题，检查自己有没有真正抓住条件

两种方法应当走到同一个答案

求 $\operatorname{lcm}(72,105)$ ，分别用素因数分解和欧几里得算法核对，并说明它为什么最小。

素因数分解是 $72=2^3\cdot3^2$ 、 $105=3\cdot5\cdot7$ 。取每种素数的最大指数，得到

\operatorname{lcm}(72,105)=2^3\cdot3^2\cdot5\cdot7=2520.

任何公倍数都必须含有这些素因子及足够的指数，因此都被 $2520$ 整除；而 $2520$ 本身满足两边要求，所以它最小。

另一条路线是 $105=72+33$ ， $72=2\cdot33+6$ ， $33=5\cdot6+3$ ， $6=2\cdot3$ ，故 GCD 为 $3$ 。先除后乘得到

\operatorname{lcm}(72,105)=\frac{72}{3}\cdot105=24\cdot105=2520.

最后验算 $2520/72=35$ 、 $2520/105=24$ ，两种方法和整除检查一致。

条件不一定只给出一个答案

两个正整数满足 $a+b=60$ 且 $\gcd(a,b)=12$ 。求它们的最小公倍数所有可能的值。

写成 $a=12u,b=12v$ ，则 $u,v$ 是互质正整数，且 $u+v=5$ 。不计顺序，只有 $(u,v)=(1,4)$ 或 $(2,3)$ ，两对也确实都互质。

第一种给出 $(a,b)=(12,48)$ ，由于 $12\mid48$ ，LCM 为 $48$ 。第二种给出 $(24,36)$ ，LCM 为 $(24/12)\cdot36=72$ 。两组数的和都是 $60$ ，GCD 都是 $12$ ，所以全部可能值是 $48$ 和 $72$ 。条件没有确定唯一答案，不能随意选其中一个。

把多个分母的要求合并

计算下面的式子，写出公分母的选择依据，并把结果约到最简：

\frac{5}{6}+\frac{7}{15}-\frac{11}{10}.

三个分数已经最简。分母的分解是 $6=2\cdot3$ 、 $15=3\cdot5$ 、 $10=2\cdot5$ ，所以 LCM 为 $2\cdot3\cdot5=30$ 。

\frac{5}{6}+\frac{7}{15}-\frac{11}{10} =\frac{25}{30}+\frac{14}{30}-\frac{33}{30} =\frac{6}{30}=\frac15.

通分时三个分母分别乘 $5,2,3$ ，分子必须同步乘相同的数。最后用最大公因数 $6$ 约分，得到最简结果。

三个数的最大公因数是1，不等于两两互质

有同学说：“ $6,10,15$ 的最大公因数是 $1$ ，所以它们的最小公倍数是 $6\cdot10\cdot15=900$ 。”指出错误，求出正确答案，并求三个从同一起点开始、周期分别为 $6,10,15$ 秒的闪灯，在起点之后的 $100$ 秒内同时闪烁的全部时刻。

三个数整体的 GCD 为 $1$ ，但两两的 GCD 分别是 $2,3,5$ ，并不两两互质。 $900$ 是公倍数，却不是最小的。由 $6=2\cdot3$ 、 $10=2\cdot5$ 、 $15=3\cdot5$ 得到

\operatorname{lcm}(6,10,15)=2\cdot3\cdot5=30.

因此正的共同闪烁时刻都是 $30$ 的正倍数。落在 $0<t\le100$ 内的只有 $30,60,90$ 秒；下一次是 $120$ 秒，已超过题设区间。起点 $0$ 虽然也是共同闪烁时刻，但题目已经把它排除了。

增加一项整除要求，会怎样改变答案

设 $a,b,c$ 都是正整数。证明

\operatorname{lcm}(a,b)\mid\operatorname{lcm}(a,bc),

并说明这为何能推出 $\operatorname{lcm}(a,b)\le\operatorname{lcm}(a,bc)$ 。

记 $M=\operatorname{lcm}(a,bc)$ 。根据定义， $a\mid M$ ， $bc\mid M$ 。由于 $b\mid bc$ ，整除的传递性又给出 $b\mid M$ 。因此 $M$ 是 $a,b$ 的正公倍数。

本章已经证明最小公倍数整除每个公倍数，所以 $\operatorname{lcm}(a,b)\mid M$ 。于是 $M=k\operatorname{lcm}(a,b)$ ，其中 $k$ 是正整数，故 $k\ge1$ ，所需不等式成立。

这里的依据是 $b\mid bc$ 。不能把结论误读成“输入数值变大，LCM 就必定变大”：例如把 $\operatorname{lcm}(6,5)=30$ 中的 $5$ 换成更大的 $6$ ，结果反而是 $6$ 。数的大小关系与整除关系是两回事。

从整除走向余数

到这里，我们可以把开头的公交问题说得很准确：从一次共同发车开始计时，同时发车的正等待时间恰好是两个周期的正公倍数，最小公倍数给出下一次共同发车，其他共同发车则在它的整数倍处发生。

但“每隔 $6$ 分钟，从第 $2$ 分钟开始”多出了一点信息。它对应的是 $2,8,14,20,\ldots$ ，这些数除以 $6$ 都余 $2$ ；甲路的 $0,4,8,12,\ldots$ 除以 $4$ 都余 $0$ 。两路能否碰头，变成了能否找到一个数，让它除以不同的数时留下指定的余数。

我们已经熟悉余数为 $0$ 的情形，那就是整除。下一章要把视野扩展到其余的余数：当两个数分组后剩下同样多的零头，它们之间会有哪些可以计算、可以证明的关系？