整除、因数与倍数

有些大数，看一眼就能知道它除以 $3$ 会不会有余数；有些数，根本不用把因数列出来，就能断定它有偶数个因数。这些判断凭什么成立？难道整数把答案写在了脸上？

上一节的带余除法告诉我们，整数除以一个正整数，总能写成“整倍数加余数”。现在先盯住其中最干净的一种情形：余数是 $0$。从这个小小的条件出发，我们会慢慢解释上面两件事，还会遇到两种有趣的数：一种能用自己的因数拼回自己，另一种会用因数拼出一个“伙伴”。

能分得干干净净，究竟是什么意思

$12$ 个人要平均分成 $3$ 组，每组 $4$ 人，刚好分完。换成 $5$ 组，每组先安排 $2$ 人，还剩 $2$ 人；如果每组人数必须一样，而且一个人不能拆开，这次就分不干净。

数学上说，$3$ 能整除 $12$，因为 $12=3\times4$，乘在 $3$ 后面的那个数是整数。写成 $12=5\times2.4$ 虽然也是正确等式，却不能说明 $$ 整除 ：问题的要求恰恰是商不能有小数部分。

对整数 $a,d$，我们约定 $d\ne0$。如果存在整数 $q$，使得

就说 $d$ 整除 $a$，记作 $d\mid a$；也说 $d$ 是 $a$ 的因数，$a$ 是 $d$ 的倍数。不能整除时，记作 $$。所以 与“ 是 的倍数”说的是同一件事。

这里的竖线是一个判断符号，不是除号，也不是分数线。$3\mid12$ 是真命题，$12\mid3$ 是假命题；读的时候，左边那个数是拿来分的，右边那个数是被分的。回到上一节，若 $d>0$，把 $a$ 写成 $a=dq+r$、，那么 就等价于 。

负数和零也要说清楚

分组的故事帮助我们入门，定义的适用范围却比故事大。因为商允许是负整数，所以 $3\mid(-12)$、$(-3)\mid12$、$(-3)\mid(-12)$ 都成立。例如 $12=(-3)\times(-4)$。改变被除数或除数的正负号，不影响能不能整除。

零也不是例外：任何非零整数都能整除 $0$，因为 $0=d\times0$。但本课程不让 $0$ 作整除关系的除数，也不讨论 $0\mid0$。这与“非零数可以整除零”是两个不同的问题，别把它们混在一起。

后面说“列出一个正整数的因数”时，我们会明确列的是正因数。例如 $12$ 的正因数是 $1,2,3,4,6,12$；如果要列全部整数因数，还要把它们各自的负数加上。正因数的讨论没有正负号干扰，更方便看清结构。

同一个整除关系，从另一头看就成了倍数。$4$ 的整数倍是 $\ldots,-8,-4,0,4,8,\ldots$；如果只要正倍数，就是 $4,8,12,\ldots$。一个正整数的正因数只有有限多个，正倍数却有无限多个。找因数是在固定总量里找分法，找倍数是在不断把同一份数量累加。

把“整除”翻译成乘法，性质就有了来处

刚接触证明时，“已知 $d\mid a$”可能让人不知道下一步写什么。一个很有用的习惯是立即把它展开成 $a=du$，其中 $u$ 是整数。这样，抽象的竖线就变成了可以加减乘除的等式。

最基本的几条结论都能这样解释：$d\mid d$，因为 $d=d\times1$；$1\mid a$，因为 $a=1\times a$；，因为 。这里凡是用作除数的 ，都要求非零。

一层层整除，可以接起来

如果 $a\mid b$，又有 $b\mid c$，那么 $a\mid c$。比如 $3\mid6$、$6\mid24$，自然得到 。为了说明任意满足条件的整数都如此，写出

其中 $u,v$ 是整数。代入后 $c=a(uv)$，而 $uv$ 仍是整数，因此 $a\mid c$。这叫整除的传递性。证明没有依赖 $3,6,24$ 这几个特定数字，所以它比单独算一个例子走得更远。

整数倍相加减，共同的因数仍在

如果 $d\mid a$ 且 $d\mid b$，那么对任意整数 $u,v$，都有

这叫整除的线性组合性质。“线性组合”听着有点抽象，在这里就是把两个数分别乘以整数，再加起来；减法也包括在内，因为系数可以是负数。

证明只需写 $a=ds$、$b=dt$。于是

括号里是整数，所以整除成立。共同的因数在这种运算后一定保留，并非“多数时候”保留。例如 $7$ 整除 $35$ 和 $56$，就一定整除 $3\times35-2\times56=-7$；结果是负数、甚至是零，都不妨碍结论。

这条性质还能倒着帮我们恢复条件。已知 $d\mid a$、$d\mid(a+b)$，两式相减便得 $d\mid b$。因此，若 $A-B$ 是 的倍数，就有

为什么两个方向都成立？$A=B+(A-B)$，也有 $B=A-(A-B)$，用的都是刚才的加减性质。后面所有十进制判别，都会借助这种“拿掉一块已知的整倍数”的办法。

有些顺手的推断，其实不成立

从 $d\mid a$ 可以推出 $d\mid ab$，因为 $a=du$ 给出 $ab=d(ub)$。但如果只知道 $$，就不能随便说 整除其中一个数：，可 既不整除 ，也不整除 。

类似地，两个数都整除 $n$，它们的乘积未必整除 $n$。$4\mid12$、$6\mid12$，但 $24\nmid12$。两项条件可能包含了重复的信息，直接相乘会额外提出要求。后续我们会专门研究什么条件下可以这样合并，现在先用定义逐步确认。

最后看因数为什么不会无限多。若 $d\mid a$ 且 $a\ne0$，写成 $a=dq$ 后，$q$ 也非零，所以 $\mathrm{\mid }q$。于是

因此，一个正整数 $n$ 的正因数都在 $1$ 到 $n$ 之间。如果两个正整数还互相整除，那么一方面 $a\le b$，另一方面 $b\le a$，只能有 $a=b$。对非零整数则只能推出 ，因为 与 也互相整除。

为什么看几位数字，就能判断整个数

看到 $32415$，不用长除法就能判断它能被 $3$、$5$ 整除，却不能被 $9$ 整除。诀窍并不是数字之间碰巧存在某种暗号，而是十进制早就替我们把大数拆成了若干块。

看末尾：前面的部分已经能分完

任意非负整数都能写成 $N=10A+b$，其中 $b$ 是个位数字。因为 $10A$ 一定能被 $2$、$5$、$10$ 整除，所以判别 $$ 时只需检查剩下的 。

因此，被 $2$ 整除要看个位是不是 $0,2,4,6,8$；被 $5$ 整除要看个位是不是 $0$ 或 $5$；被 $10$ 整除则要求个位是 $0$。这些规则都有来回两个方向：个位符合，整个数符合；整个数符合，减去 后的个位也必须符合。

判别 $4$ 时，看个位就不够了：$12$ 和 $22$ 个位相同，却只有 $12$ 能被 $4$ 整除。但写成

情况就清楚了。$100A=4\times25A$ 已经是 $4$ 的倍数，所以只要看末两位组成的 $B$。例如 $3128=3100+28$，两部分都能被 $4$ 整除，原数当然也能。

同理，$1000$ 是 $8$ 的倍数，因此判断 $8$ 看末三位。例如 $5312$ 的末三位是 $312=8\times39$，所以 $8\mid5312$。位数不足时，前面补零即可： 的末两位可看成 ， 的末三位可看成 ，数值没有改变。

看数字和：每一位多出来的部分都能分完

$12345$ 的各位数字加起来是 $15$。它与原数相差多少？按位值展开，就得到

右边每一项都是 $9$ 的倍数！所以原数与数字和相差一个 $9$ 的倍数。数字和能被 $9$ 整除，原数就能；数字和不能，原数也不能。

这不是五位数的特例。个位的权重是 $1$，十位、百位、千位的权重依次是 $10,100,1000$；把每个权重换成 $1$，差出来的都是 $9,99,999,\ldots$。因为

任意非负整数与它的数字和之差都能被 $9$ 整除，也就能被 $3$ 整除。这同时解释了 $3$ 与 $9$ 的数字和判别。

现在回看 $32415$：数字和是 $15$，能被 $3$ 整除，不能被 $9$ 整除；个位是 $5$，所以又能被 $5$ 整除。三项判断共用同一次拆数，根本不用分别做三次除法。如果数字和仍然很大，还可以对数字和继续求数字和，因为每次变换都保留同样的整除判断。

被6整除，为什么可以同时看2和3

$6\mid N$ 显然能推出 $2\mid N$、$3\mid N$，因为 $6$ 本身就是 $2$ 和 $3$ 的倍数。反过来需要说明，不能只把两个条件直接相乘。

由 $3\mid N$ 写出 $N=3q$。如果 $q$ 是奇数，就能写成 $q=2t+1$，于是 $N=6$，也会是奇数，和 矛盾。因此 必须是偶数，写成 ，便得到 。这才证明了“同时能被 和 整除”等价于“能被 整除”。

例如 $324$ 是偶数，数字和 $9$ 又能被 $3$ 整除，所以 $6\mid324$。这里特意把理由讲完整，是为了避免把这条结论误套到 $4$ 和 $6$ 上。

被11整除：为什么数字要一加一减

$2728$ 的数字和是 $19$，看不出它与 $11$ 有什么关系。但从个位起一加一减，得到 $8-2+7-2=11$，这次有用了：$2728=11\times248$。

原因仍在位值里。$10$ 比 $-1$ 多 $11$，$100$ 比 $1$ 多 $99$，$1000$ 比 $-1$ 多 ，它们的差都能被 整除。一般地， 总是 的倍数。可以用上一节的归纳法验证： 时差为零；而

只要前一项差能被 $11$ 整除，下一项也能。

所以，把个位的权重保留为 $1$，十位换成 $-1$，百位换成 $1$，这样交替下去，原数与得到的交错和相差一个 $11$ 的倍数。于是，原数能被 $11$ 整除，当且仅当交错和能被 $11$ 整除。

交错和可以是 $0$，也可以是负数，它们照样参与判断。$121$ 给出 $1-2+1=0$，所以能被 $11$ 整除；$209$ 给出 $9-0+2=11$，同样能。若从左往右开始交替，结果至多改变正负号，不影响能否被 整除。对于负整数，先对绝对值使用这些十进制规则即可。

这些判别还能反过来帮助我们补出缺失的数字。假设四位数 $\overline{3a52}$ 能被 $11$ 整除，其中 $a$ 表示十进制的一位数字。交错和是 $2-5+a-3=a-6$。由于 只能在 到 之间， 就只能在 到 之间；这个范围里唯一的 的倍数是 ，所以 。补出的数为 ，用乘法复核：。

这类题最容易漏掉的是数字的范围。如果只写“$a-6$ 是 $11$ 的倍数”，还没有做完；是 $0\le a\le9$ 把无限多个倍数压缩到了一个候选。同样，交错和也不能一律设成零：前面的 $2728$ 就给出了交错和等于 $11$ 的例子。先确定范围，再列出范围里的倍数，推理才完整。

找因数，为什么走到平方根就可以停

现在换一个问题：找出 $36$ 的全部正因数。逐个试 $1$ 到 $36$ 当然可以，但一旦找到 $2$，就已经同时找到了 $18$，因为 $36=2\times18$。因数自带伙伴，每发现一个，就能顺手找到另一个。

把这些伙伴排在一起：

因此正因数从小到大是

为什么试到 $6$ 就足够？如果 $de=36$，不可能 $d>6$ 且 $e>6$，否则乘积会大于 $36$。至少有一个因数不超过 $6$，只要小的这一边检查完整，大的那一边就不会漏掉。

对于任意正整数 $n$，同一个道理给出：若 $de=n$，至少有一个不超过 $\sqrt n$。实际找因数时，从 $d=1$ 开始，只要 就继续检查；遇到 ，记下 与 。当两者相同时，只记一次。

比如 $120$ 介于 $10^2$ 与 $11^2$ 之间，只需要检查 $1$ 到 $10$。能整除的有 $1,2,3,4,5,6$，得到八对：

所以 $120$ 有 $16$ 个正因数；排序后为

这里不只是少做了一些除法，也解释了为什么我们确信列表完整。

如果想把这件事看得更具体，可以把 $120$ 颗棋子排成整齐的长方形。每一种整数边长的排法，对应一对正因数；排成 $8$ 行、每行 $15$ 颗，和排成 $15$ 行、每行 $8$ 颗，只差把长方形转过来。检查较短的一边，就会连带得到较长的一边。只有排成正方形时，旋转前后两条边的数字完全一样，这正是配对计数里需要单独处理的一种情况。

奇数个因数，泄露了什么信息

$120$ 的正因数两两配对，一共有偶数个。$36$ 却有 $9$ 个，多出来的那一个是谁？就是和自己配对的 $6$。

只有 $d=n/d$ 时，配对才会把一个数和它自己配在一起；整理后就是 $n=d^2$。因此，若 $n$ 不是完全平方数，所有正因数都能组成不重叠的两人组，个数一定是偶数；若 $n$ 是完全平方数，只有 $\sqrt n$ 单独留下，其余照样成对，个数一定是奇数。

我们由此证明了一个双向结论：正整数有奇数个正因数，当且仅当它是完全平方数。 $1$ 也包括在内，它只有一个正因数 $1$，并且 $1=1^2$。现在若有人告诉你某个正整数恰有 $17$ 个正因数，即使不知道它是多少，也能断定它是平方数。

把因数加起来，会发生什么

知道怎样找全因数之后，我们可以玩一个新游戏：拿走一个正整数本身，把剩下的正因数加起来，看看总和落在哪里。

对 $8$，得到 $1+2+4=7$，比原数小；对 $12$，得到 $1+2+3+4+6=16$，比原数大。有没有刚好回到原数的情况？ 就是：

一个正整数除了自身以外的正因数，叫作它的真因数。如果全部真因数之和恰好等于这个正整数，就称它为完全数。这里的“全部”不能省：从 $12$ 的真因数里挑出 $1,2,3,6$ 确实能凑出 $12$，但漏掉 $4$ 就不符合定义。

$28$ 也是完全数。由配对 $1\times28$、$2\times14$、$4\times7$，列出真因数 $1,2,4,7,14$，验证

$1$ 没有真因数，我们把空的求和记为 $0$，所以 $1$ 不是完全数。对于 $2,3,4,5$，真因数和依次是 $1,1,3,1$，因此 $6$ 确实是最小的完全数，而不只是我们最先发现的一个例子。

两个数还能互相“拼出”对方

从 $220$ 出发，列出它的真因数：

它们相加并不回到 $220$，而是得到

再看 $284$。它的正因数配对只有 $(1,284)$、$(2,142)$、$(4,71)$，所以真因数是 $1,2,4,71,142$，而

居然回来了。像这样，两个不同的正整数，各自的全部真因数之和恰好等于对方，就叫一对亲和数。只验证一个方向还不够：必须既从 $220$ 得到 $284$，又从 $284$ 得到 $220$。

这两份因数列表也能用刚才的配对法核查完整性：$14^2<220<15^2$，检查到 $14$ 即可；$16^2<284<17^2$，检查到 即可。数值上的巧合很吸引人，但判断它确实成立，仍靠逐一核实定义里的每个条件。

把方法串起来试一试

练习一：把符号翻译成等式。 判断 $(-4)\mid20$、$7\mid0$、$8\mid12$ 是否成立，并说明理由。再证明：若 $d\mid a$，则对任意正整数 $k$，有 。

练习二：用加减缩小可能性。 正整数 $d$ 同时整除 $2n+1$ 与 $5n+4$，其中 $n$ 是整数。证明 $d$ 只能是 $1$ 或 $$，并分别给出能使这两个值成立的 。

练习三：两个条件能不能合并？ 已知 $6\mid n$ 且 $15\mid n$，判断 $10$、$30$、$45$、$90$ 是否一定整除 $n$。

练习四：让数字条件帮你筛选。 在各位数字之和为 $15$、且能被 $4$ 整除的三位数中，找出最小的数。再判断它能否被 $6$ 和 $11$ 整除。

练习五：找全与求和一起做。 用配对法求 $360$ 的正因数个数及所有正因数之和，不使用素因数分解公式。它是完全数吗？

练习六：给完全数换一种说法。 记 $S(n)$ 为正整数 $n$ 的全部正因数之和，包括 $n$ 自己。证明 $n$ 为完全数，等价于 $S(n)=2n$；再解释为什么亲和数 $a,b$ 满足 。

继续往里拆，会剩下什么

这一节一直在问“哪些数能分进去”。整除的定义让我们把这个问题翻译成整数乘积；十进制判别帮我们少做一些除法；因数配对则保证找得快，还找得全。

但配对法仍需要逐个尝试。如果整数很大，有没有一种结构能直接告诉我们它有哪些因数，甚至不列因数就算出个数？先看 $30$：它可以拆成 $2\times15$，也可以拆成 $3\times10$，还可以拆成 $5\times6$。继续拆下去，这几条路会不会走向不同的终点？

下一节，我们就研究那些除了 $1$ 和自身之外，再没有其他正因数的整数——素数（也叫质数）。从它们开始，整数的因数结构会变得更清楚。

证明时，由 $d\mid a$ 写成 $a=dq$，其中 $q$ 为整数。若 $k=1$，结论就是已知条件；若 $k\ge2$，则

括号里是整数，所以 $d\mid a^k$。题目限定正整数 $k$ 是有必要的；当 $a\ne0$ 且 $k=0$ 时，$a^0=1$，原来的条件通常不能保证 $d\mid1$。

所以 $30\mid n$，再由 $10\mid30$ 得出 $10\mid n$。至于 $45$ 和 $90$，取 $n=30$ 就得到反例：它满足原来的两个条件，却不能被 $45$ 或 $90$ 整除。因此这两项都不一定成立。整个过程只用了整数乘积、奇偶性和传递性。

对应末两位 $59,68,77,86,95$，只有 $68$ 能被 $4$ 整除。所以百位为 $1$ 时唯一的候选是 $168$，它也必定小于所有百位更大的候选，答案为 $168$。

验证 $1+6+8=15$，$168=4\times42$。它是偶数，数字和能被 $3$ 整除，故能被 $6$ 整除，且 $168=6\times28$。交错和 $8-6+1=3$ 不能被 $11$ 整除，所以 $11\nmid168$。

没有自身配对的项，所以共有 $12\times2=24$ 个正因数。每对先相加，再合计：

真因数之和要去掉自身 $360$，得到 $1170-360=810$，不等于 $360$，所以它不是完全数。也可用平方数结论作一致性检查：$360$ 不是平方数，算出的正因数个数确实是偶数。

若 $a,b$ 是亲和数，$a$ 的真因数和为 $b$，所以 $S(a)=a+b$；同理，$S(b)=b+a$。例如 $S(220)=284+220=504$，$S(284)=220+284=504$。不过只知道两个不同的数的正因数总和相等，还不足以说明它们亲和：还必须检查这个共同的和确实等于两数之和。