整除

01从完整的一包开始

1、2、3、… 是正整数，表示完整的几个。把 0 以及 $-1$、$-2$、$-3$、… 也包括进来，就得到整数，常用字母 $\mathbb Z$ 表示这整个集合。负整数可以记录相反方向的移动或数量的减少；它不是负半个圆片。现在的分包图先只使用非负数量，也就是 0 或正整数。

先按下面的“下一步分包”。每按一次，就取出 4 个圆片装好；青色的一组是一包，灰色圆片还在等待。6 包用掉 $6 \times 4 = 24$ 个，从 26 个中减去 24 个，剩下 2 个。2 小于每包所需的 4，所以无法再装满一包。最后一步会把这 2 个标成金色：这时它们才是余数。按「逐包装入」开始演示，按「下一步分包」一次装一包，按「重置动画」回到开头；改变总数或每包大小也会从头开始。

如果换成 24 个圆片，每包仍是 4 个，就恰好装成 6 包：$24 = 4 \times 6$，没有剩下。我们把“能写成整整几份”记成 $4 \mid 24$，读作“4 整除 24”。竖线不是除号，它表达一句成立或不成立的话。$4 \mid 24$ 成立，而 $4 \mid 26$ 不成立。$26 \div 4 = 6.5$ 这个除法当然有数值，但 6.5 不是整数，不能表示完整的几包。

这里 $d$ 是每份的大小，$n$ 是总量，$q$ 是整数倍数。这一行是定义：它规定整除这个词的意思，不是一条需要证明的结论。“存在一个整数 $q$”只要求找到一个符合条件的整数，不要求每个整数都可以。比如 $3 \mid 12$ 的证据是 $q = 4$，因为 $12 = 3 \times 4$。要说明 5 不能整除 12，可以检查相邻倍数：$5 \times 2 = 10 < 12 < 15 = 5 \times 3$；2 与 3 之间没有整数，所以没有可用的 $q$。

这个等式定义比圆片图更广。$3 \mid 0$，因为 $0 = 3 \times 0$；$3 \mid -12$，因为 $-12 = 3 \times (-4)$；$-3 \mid 12$，因为 $12 = (-3) \times (-4)$。因此非零整数都整除 0，负号也不妨碍整除。$d$ 和 $-d$ 能整除完全相同的数：只要把倍数 $q$ 换成 $-q$。

02剩下多少，为什么只有一种答案

26 个圆片刚才分成 6 包，每包 4 个，另剩 2 个。因此 $26 = 4 \times 6 + 2$。我们把完整包数 6 叫商，把剩余的 2 叫余数。只写“除数乘商，加余数”等于原数还不够：26 也等于 $4 \times 5 + 6$，可是余下的 6 还能装一包。为表示已经分完，必须要求余数不小于 0，且严格小于除数。

对于正整数 $n$，可以不停减去 $d$，直到剩下的数小于 $d$。负整数又怎么办？例如 $-17$ 除以 5，不能把 $-2$ 当作标准余数。我们把 $-17$ 放在相邻倍数 $-20$ 和 $-15$ 之间，从左边的 $-20$ 向右走 3 到达 $-17$，所以 $-17 = 5 \times (-4) + 3$。商为 $-4$，余数为 3，仍满足 $0 \le 3 < 5$。可以把它看成数轴上长为 5 的一段内部的位置。

为什么任何整数 $n$ 都能这样写？在数轴上标出 $d$ 的所有倍数：…、$-2d$、$-d$、0、$d$、$2d$、…，相邻两个倍数之间相隔 $d$。$n$ 一定落在某个倍数 $dq$ 和下一个倍数 $d(q + 1)$ 之间，可以等于 $dq$，但还没有到 $d(q + 1)$。从 $dq$ 向右走到 $n$ 的距离记作 $r$，于是 $n = dq + r$，而且 $0 \le r < d$。刚才的 $-17$ 就是这样：它落在 $-20$ 和 $-15$ 之间，距离 $-20$ 为 3。

为什么不能同时有两组不同答案

先用数字看一遍：26 也能写成 $4 \times 5 + 6$，但剩下的 6 还能再装一包，所以这种写法不合规；余数必须小于每包大小，答案就只能有一种。下面用字母重复同一件事，看不懂可以跳过。假设同一个 $n$ 有两种合规写法 $n = dq + r = dq' + r'$，其中两个余数都在 0 到 $d - 1$ 之间。两边减去 $dq'$ 和 $r$，得到 $d(q - q') = r' - r$。右边严格在 $-d$ 与 $d$ 之间。左边是 $d$ 的整数倍：若 $q - q' \ge 1$，左边至少为 $d$；若 $q - q' \le -1$，左边至多为 $-d$。因此只有 $q - q' = 0$ 才可能落在这个范围内。于是 $q = q'$，再代回得到 $r = r'$。商和余数都唯一。

因此 $d \mid n$ 当且仅当标准余数为 0。若余数为 0，$n = dq$ 就符合整除定义；反过来，若 $n = dk$，那么 $(k, 0)$ 已是合规的商与余数，由唯一性可知标准余数必为 0。“当且仅当”表示两个方向都成立，我们刚才分别检查了它们。

03把整除改写成可以使用的等式

现在遇到 $d \mid a$，不要只把竖线看成一个需要背的符号。把它换成 $a = ds$，其中 $s$ 是整数，便能进行加减乘法。比如 $6 \mid 18$ 与 $6 \mid 30$ 分别告诉我们 $18 = 6 \times 3$、$30 = 6 \times 5$。相加得到 $18 + 30 = 6 \times (3 + 5) = 6 \times 8$，所以 6 整除它们的和；相减得到 $30 - 18 = 6 \times (5 - 3) = 6 \times 2$，所以也整除它们的差。

把这个理由写成一般情形。若 $a = ds$、$b = dt$，再选任意整数 $u$、$v$，那么 $ua + vb = u(ds) + v(dt) = d(us + vt)$。括号里的 $us + vt$ 仍是整数，因为整数的加法、乘法仍得到整数。因此 $d \mid (ua + vb)$。$ua + vb$ 叫作 $a$、$b$ 的整数线性组合：“组合”是加在一起，“整数”说明倍数只能取整数。负倍数也可以，所以减法已经包含在内。

还有一条沿着倍数链前进的规则。若 $a \mid b$ 且 $b \mid c$，写 $b = as$、$c = bt$，再把第一式代入第二式，得到 $c = (as)t = a(st)$。$st$ 是整数，所以 $a \mid c$。例如 $3 \mid 12$、$12 \mid 60$，就有 $60 = 12 \times 5 = 3 \times 4 \times 5 = 3 \times 20$。这个性质叫传递性，但真正可用的是刚才那条整数等式。

04公因数为什么不会丢

有时我们要同时分配两种数量，并让每份大小相同。比如 18 和 30 各自能按哪些正整数大小分得没有剩余？18 的正因数是 1、2、3、6、9、18；30 的是 1、2、3、5、6、10、15、30。这些因数可以配成 $18 = 1 \times 18 = 2 \times 9 = 3 \times 6$，以及 $30 = 1 \times 30 = 2 \times 15 = 3 \times 10 = 5 \times 6$。从 1 试到原数，余数为 0 的数才留下，这样就得到完整列表。更大的正因数不会出现，理由在下一节。比如 18：$1 \times 18$、$2 \times 9$、$3 \times 6$，成对的因数已经都出现了。两个列表都出现的 1、2、3、6 是公因数，其中最大的是 6。我们记作 $\gcd (18,30) = 6$。$\gcd$ 是最大公因数的英文缩写。

为什么这个“最大”存在？对于正整数 $a$、$b$，1 总能同时整除它们，所以列表不空。若正整数 $d$ 整除 $a$，$a = dq$ 中的 $q$ 必为正整数，至少是 1，于是 $d \le a$。同理 $d \le b$。因此正公因数只可能在 1 到较小的那个数之间，选择有限，必能找出最大值。若两数最大公因数是 1，我们就称它们互素；这不是说两数各自都必须是素数。

当数变大，逐个列出因数会很慢。我们希望用更小的一对数替换原来的一对，又不丢掉任何公因数。用 84 和 30 试一下：$84 = 2 \times 30 + 24$。减去两份 30 后留下 24。下面每按“下一行除法”，模型就在相同比例下把被除数切成整份除数与金色余数，再把下一对数换成“除数、余数”。图下保留每一步的等式，随时可以退回或重置。

证明替换保留的是整个公因数列表

先证明一个方向。若 $d$ 同时整除 84 和 30，它就整除整数线性组合 $84 - 2 \times 30 = 24$，因此 $d$ 是 30 与 24 的公因数。再证明反方向。若 $d$ 同时整除 30 与 24，它就整除 $2 \times 30 + 24 = 84$，因此 $d$ 也是 84 与 30 的公因数。我们不是只碰巧保留最大那个数，而是两个公因数列表完全相同，所以最大值相同。

一般式也用同样两步：公因数 $d$ 若整除 $a$、$b$，就整除 $r = a - qb$；若整除 $b$、$r$，就整除 $a = qb + r$。重复这个替换，84 与 30 变成 30 与 24，再变成 24 与 6，最后变成 6 与 0。模型里的三行计算分别是 $84 = 2 \times 30 + 24$、$30 = 1 \times 24 + 6$、$24 = 4 \times 6 + 0$。

为什么停在这里？每个非零整数都整除 0，所以 6 与 0 的正公因数正好就是 6 的正因数，最大为 6。又因为每一行都保留公因数，原来的 $\gcd (84,30)$ 也是 6。一般地，$\gcd (a,0) = a$ 对正整数 $a$ 成立。这个反复使用带余除法的方法叫辗转相除法。它一定停止，因为每次新余数都是比当前正除数更小的非负整数，不可能在有限的整数 0、1、…、$b - 1$ 中无限严格下降。零余数本身不是所求公因数；答案是它前面的最后一个非零数。

05把最后的余数追回原来的数

辗转相除不只给出答案 6。它还留下了每个余数怎样由上一对数算出的记录。我们想让最终的 6 只用最初的 84 与 30 表示，这样以后只知道某数整除 84、30，也能直接说明它整除 6。先从 $6 = 30 - 24$ 开始，其中 24 还不是原来的数；第一行告诉我们 $24 = 84 - 2 \times 30$，因此把这个整体代进去。

第二行括号前的负号作用到里面每一项，所以减去“84 减两份 30”，就等于减去 84 并加回两份 30。下面的条带保留了这些计算：84 减两份 30 得到余数，30 减这个余数得到新的长度，替换后出现的三份 30 也可以接起来核对。红色虚线段表示被减去的长度，金色表示留下的长度。点选步骤后画面会停住，供我们对照上面的每一行。

这里的 $A$、$B$ 是这一步保留的两个数；$u$、$v$、$s$、$t$ 是它们各自含有几份 $a$ 和 $b$。字母多的时候，可以先看下面的数字例子，再回来。为什么其他正整数也能这样回代？最初 $a = 1a + 0b$，$b = 0a + 1b$，已经是整数线性组合。若当前两数是 $A = ua + vb$ 与 $B = sa + tb$，下一余数 $R = A - qB$，就等于 $(u - qs)a + (v - qt)b$。新的两个系数仍是整数。因此初始数及后来每轮保留的数，都保持这种形式。最后一个非零数有时就是初始数之一：例如 $6 = 2 \times 3 + 0$ 时，答案 3 的表达式是 $0 \times 6 + 1 \times 3$，而不是一个新产生的非零余数。结合刚才的算法证明，我们得到：总存在整数 $u$、$v$，使 $au + bv = \gcd (a,b)$。这叫裴蜀等式。它的理由是回代保留下来的记录，不是一个凭空出现的公式。

什么时候能把乘积里的因子分开

回到之前不能随意使用的推理。现在假设 $\gcd (a,b) = 1$，而且 $a \mid bc$。裴蜀等式给出 $au + bv = 1$。两边乘以 $c$，是为了让已知的乘积 $bc$ 出现：$acu + bcv = c$。第一项 acu 是 $a$ 的整数倍；第二项 bcv 也是，因为 $bc = ak$ 对某个整数 $k$ 成立，所以 $bcv = a(kv)$。两项相加得到 $c = a(cu + kv)$，括号里是整数，于是 $a \mid c$。每一个步骤都用到了条件：若 $\gcd (a,b)$ 不等于 1，就不能在起点写出那条等于 1 的式子。

例如 4 与 9 互素，因为 $9 - 2 \times 4 = 1$，而共同因数必须整除 1，只可能为 1。如果知道 $4 \mid 9c$，就可以推出 $4 \mid c$；具体地 $c = 9c - 2 \times 4c$，两项都能被 4 整除。与它对照，$6 \mid 2 \times 3$ 不能推出 $6 \mid 3$，因为 $\gcd (6,2) = 2$，并没有满足互素条件。

06为什么素数是乘法的零件

把 60 写成 $6 \times 10$ 后，还可以把 6 拆成 $2 \times 3$，把 10 拆成 $2 \times 5$。于是 $60 = 2 \times 3 \times 2 \times 5 = 2^{2} \times 3 \times 5$。$2^{2}$ 只是两份 2 相乘的简写。最后这些大于 1 的数，除了 1 和它自己，没有其他正因数，不能再拆成两个都大于 1 的正整数。我们把这样的数叫素数。大于 1 而不是素数的整数叫合数；1 单独保留，既不是素数，也不是合数。

这一定义解释了为何不把 1 当成素数：如果允许它作为分解零件，就可以在乘积里任意多添几个 1，而没有改变原数，零件的份数就无法唯一确定。素数分解只记录真正改变乘积的大于 1 的零件。接下来需要证明两件事：每个大于 1 的整数都能拆完，并且最终零件不会因拆法不同而不同。

先证明能拆完：不会留下一种例外

假设有某些大于 1 的整数不能写成素数的乘积，选择其中最小的 $N$，所用的仍是非空正整数集合有最小值的性质。$N$ 不可能是素数，因为一个素数本身就是只有一个因子的素数乘积。所以 $N$ 是合数，可以写成 $N = ab$，其中 $a$、$b$ 都大于 1。因为 $b \ge 2$，$a = N/b < N$；同理 $b < N$。$a$、$b$ 比最小的例外 $N$ 还小，所以都不是例外，各自都有素数分解。把两份分解相乘就得到 $N$ 的素数分解，与假设冲突。因此例外不存在。

再证明零件唯一：一个素因子必须在两边都出现

先补上需要的工具。若素数 $p$ 整除 $ab$，那么要么 $p$ 整除 $a$，要么 $p$ 不整除 $a$。第一种已经得到结论；第二种里，$p$ 的正因数只有 1、$p$，而 $p$ 不能作为 $a$ 的因数，所以 $\gcd (p,a) = 1$。用上一节已经证明的互素消因子规则，得到 $p \mid b$。因此素数整除两个数的乘积，必定整除其中至少一个。若乘积有更多项，就把它分成“第一项”乘“其余各项”，不断对剩余部分使用同一规则，最终会找到被 $p$ 整除的一项。项数有限，所以不会无止境地寻找。

现在假设同一个正整数有两份素数分解。取左边第一个素数 $p$；它整除左边的乘积，因此也整除相等的右边乘积。由刚才的工具，$p$ 整除右边某个素数 $q$。$q$ 的正因数只有 1 与 $q$，而 $p > 1$，所以 $p = q$。把右边这个 $q$ 移到最前面，左右都除以非零的 $p$，就消去一对相同因子。对剩下的两份乘积重复，直到一边没有因子。另一边也必须没有，因为空乘积等于 1，而一个或多个大于 1 的素数相乘至少为 2，不可能等于 1。因此两份分解的素数及每个素数出现的次数完全相同，只允许次序不同。

我们刚才证明的“能分解，而且除顺序外唯一”，合在一起叫算术基本定理。这个名字是对结果的命名；真正保证它的，是上面的存在性与唯一性两个证明。接下来数素因子的份数，才有了不会因拆法变化的依据。

07共同的份数与足够的份数

用已经分解好的 $60 = 2^{2} \times 3 \times 5$，与 $72 = 2^{3} \times 3^{2}$ 比较。72 的分解可逐步核对：$72 = 2 \times 36 = 2 \times 2 \times 18 = 2 \times 2 \times 2 \times 9 = 2^{3} \times 3^{2}$。下面每一行只放同一种素数，每个方块代表一份参与相乘的因子。先看两列都能提供多少份：2 都有两份，3 都有一份，5 则不是两列都有。青色方块把这些共同份数配对。

为什么可以用份数判断整除？若 $d \mid a$，写 $a = dk$，$k$ 是正整数。把 $d$、$k$ 都分解，乘起来得到 $a$；唯一性说明，每个素数在 $d$ 中的份数，加上在 $k$ 中的份数，恰好等于在 $a$ 中的份数。因此 $d$ 不能拥有超过 $a$ 的任何一种素数。反过来，若 $d$ 的每一种素因数份数都不超过 $a$，就从 $a$ 的分解中拿走 $d$ 所需的份数，剩下的因子相乘得到整数 $k$，于是 $a = dk$。两个方向都成立。

要同时整除两数，每种素数只能取两边份数中较少的那个。因此共同部分是 $2^{2} \times 3 = 4 \times 3 = 12$。它确实整除两数：$60 = 12 \times 5$，$72 = 12 \times 6$。其他公因数的各项份数都不超过它，所以其他正公因数都整除 12，因而不大于 12。这就证明 $\gcd (60,72) = 12$，不只是观察方块得出的猜测。

再把问题反过来：找一个正整数，同时是 60 与 72 的倍数，并尽量小。这叫最小公倍数，记作 $\operatorname{lcm}$。为包含两数，每种素数至少要取两边较多的份数。取 $2^{3} \times 3^{2} \times 5 = 8 \times 9 \times 5 = 360$，便有 $360 = 60 \times 6 = 72 \times 5$。任何其他正公倍数都至少有这些份数，所以它是 360 的正整数倍，不可能比 360 小。因此 $\operatorname{lcm} (60,72) = 360$。这里特意要求正公倍数，否则 0 也同时是两数的倍数，会改变问题。

一般地，若某种素数在 $a$、$b$ 中分别出现 $\alpha$、$\beta$ 次，最大公因数取较少份数，最小公倍数取较多份数。二者相乘时，份数总和为 $\alpha + \beta$：若 $\alpha \le \beta$，就是 $\alpha + \beta$；若 $\beta < \alpha$，就是 $\beta + \alpha$。这恰好也是 $ab$ 中的份数。对每种素数都成立，再由分解唯一性，得到 $\gcd (a,b) \times \operatorname{lcm} (a,b) = ab$。例子里是 $12 \times 360 = 4320 = 60 \times 72$。

08用这些工具做完整的证明

例一：相邻整数没有大于 1 的公因数

取正整数 $n$。若正整数 $d$ 同时整除 $n$ 与 $n + 1$，由整数线性组合性质，它就整除 $(n + 1) - n = 1$。正整数 $d$ 若整除 1，$1 = dk$ 中的 $d$、$k$ 都至少是 1，只有 $d = k = 1$ 才可能乘成 1。因此任何正公因数都是 1，而 1 确实同时整除两数，所以 $\gcd (n,n + 1) = 1$。我们没有从几个相邻数猜测，而是让 $n$ 保持任意，整个论证只用到了“相差 1”。

例二：三个连续整数的乘积一定被 6 整除

取任意整数 $n$，包括负整数，记 $P = n(n + 1)(n + 2)$。先找因子 2。带余除法说明 $n$ 除以 2 的余数只能是 0 或 1。若 $n = 2k$，则 $n$ 含有因子 2；若 $n = 2k + 1$，则 $n + 1 = 2(k + 1)$，仍找到因子 2。因此 $P$ 必能写成 $2u$，$u$ 为整数。这里包含了全部余数情形，没有第三种需要补查的情况。

再找因子 3。$n$ 除以 3 的余数只有 0、1、2：若 $n = 3k$，$n$ 是 3 的倍数；若 $n = 3k + 1$，$n + 2 = 3(k + 1)$；若 $n = 3k + 2$，$n + 1 = 3(k + 1)$。因此 $3 \mid P$。最后不能只说“有 2 也有 3，所以有 6”而不说明原因。我们已经有 $P = 2u$ 与 $3 \mid 2u$。因为 $\gcd (3,2) = 1$，由互素消因子规则得到 $3 \mid u$，即 $u = 3v$。代回 $P = 2 \times 3v = 6v$，所以 $6 \mid P$。

例三：任何有限列表都装不下全部素数

假设有人声称已经列出全部素数，列表为 $p_{1}$、$p_{2}$、…、$p_{k}$。这是一个有限列表，至少含有素数 2。把它们相乘再加 1，得到 $N = p_{1}p_{2}\cdots p_{k} + 1$。$N > 1$，按前面已经证明的素数分解存在性，$N$ 至少有一个素因子 $q$。若 $q$ 在原列表里，它就整除乘积 $p_{1}p_{2}\cdots p_{k}$；同时 $q \mid N$，于是 $q$ 整除二者之差 1。可是素数 $q > 1$，不可能整除 1。因此 $q$ 不在原列表，声称“已经列完”便产生矛盾。素数不可能只有有限多个。

注意，我们只证明 $N$ 有一个不在列表里的素因子，没有证明 $N$ 本身总是素数。例如列表取 2、3、5、7、11、13，逐次相乘得到 6、30、210、2310、30030，所以乘积加 1 是 30031，而 $30031 = 59 \times 509$，因为 $59 \times (500 + 9) = 29500 + 531 = 30031$。它是合数也不影响论证：至少一个新的素因子已经足够。这是在竞赛证明中需要分清的“实际证明了什么”。

09带着理由练习

试着写下每道题的答案和理由，用展开的解答核对。除了答案，还要检查：倒过来推是否成立，有没有遗漏整数或余数的情形，每次除法的除数是否允许。

回到最初的分包问题，我们现在不只会算余数。整除的整数倍定义让我们能够组合等式；组合等式解释了公因数为什么在辗转相除中保留；回代又给出互素时能消去乘积因子的理由。这条逻辑链会继续用于同余与不定方程。后面的页面仍会在使用时重新说明需要的步骤，不要求我们只凭记忆接上。