整除与因数

上一篇我们搭建了整数家族的基本版图——从自然数的局限出发，引入了负整数，认识了封闭性、离散性与无穷性这三张整数的"身份证"，并在带余除法定理里看到了整数做除法时仍然保有的完美结构。

今天我们要在这个基础上走得更深一步，专门讨论余数恰好为零的那种情况：整除。整除看起来只是除法的一个特殊情形，实际上它是整个初等数论的核心纽带——公因数、最小公倍数、质数分解，乃至密码学的 RSA 算法，都把整除关系作为出发点。

整除的定义与基本记号

理解整除，最自然的出发点是分东西时"分得干干净净"的那种感觉。把 $12$ 颗糖平均分给 $4$ 个朋友，每人恰好 $3$ 颗，没有余数，这就是整除；而把同样的 $12$ 颗糖分给 $5$ 个朋友，每人只能分 $2$ 颗，还剩下 $2$ 颗无处安放，这就不是整除。"能不能分得干净"这个问题，在数学里被提炼成了一个干净的定义。

这个定义有几个细节值得停下来思考。首先，为什么要求 $a \neq 0$？因为"被 $0$ 整除"这件事在算术里没有意义——任何数除以 $0$ 都是无法定义的操作。但 $0$ 本身可以被任意非零整数整除：$0 = a \times 0$，商 永远存在，所以对任意 都有 。其次，定义里的 是整数，而不仅仅是正整数。比如 ，因为 ，这里 ；整除关系可以跨越正负，这与我们把余数限定为非负的带余除法定理是完全相容的——当余数为零时，带余除法的表达式 就直接变成了 ，恰好是整除的定义。

具体的例子有助于校准直觉。$3 \mid 12$ 成立，因为 $12 = 3 \times 4$；$5 \mid 35$ 成立，因为 $35 = 5 \times 7$；而 是因为 ，余数为 ，不为零，无法写成 的形式。记号 中，竖线是整除符号，不是分数线，两者在书写和含义上都不能混淆—— 是一个命题（真或假），而 是一个数值表达式。

整除的基本性质体系

整除关系不是孤立存在的几个例子的集合，它有一套内在一致的逻辑结构。理解这套结构，比记住一堆孤立的性质更有价值，因为它能让你在遇到新的整除问题时，凭借推理而不是凭记忆找到出路。

自整除与零的情形是最基础的起点：任意整数 $a$ 整除自身（$a \mid a$，因为 $a = a \times 1$），$1$ 整除任意整数（$1 \mid a$，因为 ），任意非零整数整除 （前面已经说明）。

更有力的是整除的传递性：若 $a \mid b$ 且 $b \mid c$，则 $a \mid c$。证明是直接的——由 $a \mid b$ 得 $b = a q_1$，由 得 ，代入得 ，而 是整数，所以 。传递性使得整除关系可以沿着一条链条传递下去：若 且 ，则 ，这在证明中可以节省大量重复论证。

比传递性更强大、在后续数论里反复被调用的，是整除的线性组合性质：若 $a \mid b$ 且 $a \mid c$，则对任意整数 $m, n$，有 $a \mid (mb + nc)$。证明思路完全类似：，，于是 ，而 是整数，结论成立。这条性质的含义极为宽泛：如果 能整除 和 ，那么 和 之间任何的"线性混搭"——不管怎么乘以整数再相加减——都还能被 整除。以 且 为例， 和 （）都成立，这是线性组合性质的直接体现。

此外还有一条约束因数大小的性质：若 $a \mid b$ 且 $b \neq 0$，则 $|a| \leq |b|$。直觉上"因数不会大于它的倍数"，这条性质把这个直觉变成了严格结论，并且告诉我们更重要的一件事：任意一个非零整数的因数只有有限多个，因为因数的绝对值不超过这个数本身的绝对值，而绝对值不超过某个上界的整数只有有限多个。与此相伴的是互整除性质：若 $a \mid b$ 且 ，则 ——两个整数互为因数，只能是相差一个符号。这条性质在需要证明"两个数相等"时非常有用，先分别证明 和 ，再结合正整数的假设就能得出 。

整除的判别规则

掌握了整除的定义与性质之后，一个非常实用的问题随之而来：面对一个具体的大数，如何在不做完整除法的前提下，快速判断它能否被某个小数整除？数学的美妙之处在于，这类快速判别方法往往有深刻的数论依据，理解了依据，规则就不再是需要死记的口诀，而是自然推导出的结论。

被 $2$ 和 $5$ 整除的判别是最简单的情形，它们的规则都只涉及末位数字。理由是：任意整数都可以写成 $N = 10k + d$，其中 $d$ 是个位数字，$k$ 是去掉个位后剩余部分。由于 $10 = 2 \times 5$，有 且 ，所以 ，。在 到 的个位数字中，被 整除的是 ，被 整除的是 ——这就是我们熟悉的"末位为偶数则被 整除，末位为 或 则被 整除"。末位同时为 时满足 ，这等价于同时被 和 整除（两者 ）。

被 $4$ 整除的判别与被 $2$ 的类似，但需要看末两位。这是因为 $100 = 4 \times 25$，所以 $4 \mid 100k$，于是 $N = 100k + \overline{d_1 d_0}$ 时，。以 为例，末两位 ，所以 ；而 的末两位 除以 余 ，所以 。

被 $3$ 和 $9$ 整除的判别规则就更有数论味道了，它涉及的不是某几位数字，而是所有位数字之和。这背后的关键是 $10 \equiv 1 \pmod{3}$，即 $10$ 除以 $3$ 余 $1$，从而 对所有 成立。把 按位展开：

每个 $10^k$ 在模 $3$ 意义下都等于 $1$，所以 $N \equiv a_n + a_{n-1} + \cdots + a_0 \pmod{3}$，即 与其各位数字之和在模 意义下相等。由此, 当且仅当各位数字之和被 整除。完全相同的推理对 成立，因为 ，所以 各位数字之和。这两条规则是同一个道理的两个应用，能被 整除必然能被 整除（因为 的整除条件更严格），但反过来不成立， 的数字和是 ，被 整除但不被 整除就是一个例子。

被 $6$ 整除的判别则把前面的工具组合起来：$6 = 2 \times 3$ 且 $\gcd(2, 3) = 1$，所以 $6 \mid N \iff 2 \mid N$ 且 ，即末位为偶数且各位数字之和被 整除。这种"把合数分解为互质因数乘积再逐一判别"的策略，是整除判别的一般框架——只要被判别数能分解为两两互质的因数之积，就可以换算为各个因数的独立判别。

因数与倍数的结构

整除关系定义了两种相互依存的角色：因数与倍数。若 $a \mid n$，则 $a$ 是 $n$ 的因数，$n$ 是 $a$ 的倍数。研究一个数的因数全貌，也就是研究有多少个数能"干干净净地量尽"它，是整除理论的核心问题之一。

寻找所有因数的系统方法，是配对。对 $n = 36$，从 $1$ 开始逐一检验：$1 \times 36 = 36$，$2 \times 18 = 36$，$3\times 12$，，。每找到一个因数 ，其配对因数 就同时被找到了，因此只需检验到 为止——对 来说只需检验到 ，超过 的因数（）都会在配对中自动出现。 的全部正因数是 ，共 个。

统计因数个数有一个优雅的公式，它依赖于质因数分解。若

则 $n$ 的正因数个数为 $\tau(n) = (a_1 + 1)(a_2 + 1) \cdots (a_k + 1)$。推导思路简洁： 的任意一个正因数形如 ，其中每个指数 可以独立地在 到 之间取值，共 种选法，因此由乘法计数原理，总的因数个数是 。以 为例，，即 有 个正因数，逐一列出是 ，确实 个。这个公式的背后是组合学里"每个位置独立选择"的乘法原理，数论与计数的深层联系从这里就已经开始显现。

完全数与亲和数

在系统地研究了因数的计数之后，让我们在这个框架里看两个格外引人入胜的数论对象。它们都是由因数的总和来定义的，背后却牵涉着至今未解的深层谜题。

完全数（Perfect Number）的定义别致而自洽：若一个正整数恰好等于它所有真因数（即除自身以外的正因数）之和，便称其为完全数。最小的例子是 $6$：它的真因数是 $1, 2, 3$，而 $1 + 2 + 3 = 6$，完全吻合。下一个是 $28$：真因数 $1,2,4,7,$ 之和恰好是 。接下来依次是 和 ——这些数字越来越稀疏，数学家为了寻找它们付出了巨大努力。

古希腊数学家欧几里得发现了一条生成偶完全数的公式，而两千年后欧拉（Euler）证明了这实际上涵盖了全部偶完全数。欧几里得定理说：若 $2^p - 1$ 是质数（这类质数今天被称为梅森质数），则 $n = 2^{p-1}(2^p - 1)$ 是偶完全数。当 时 是质数，；当 时 是质数，；当 时 是质数，。欧拉进一步证明，所有偶完全数都具有这种形式，因此寻找完全数等价于寻找梅森质数。截至目前，人类发现的梅森质数不足 个，且分布极为稀疏。至于是否存在，至今无人知晓——这是数学史上最古老的悬而未决的问题之一，既没有人能证明它不存在，也没有人能构造出一个，绝大多数数论学家相信奇完全数不存在，但这只是信念，不是定理。

与完全数"向内看"自己因数之和的方式不同，亲和数（Amicable Numbers）是一对"相互依存"的正整数：$a$ 的所有真因数之和等于 $b$，而 $b$ 的所有真因数之和恰好又等于 $a$。历史上最著名的一对亲和数是 $220$ 与 $284$，古希腊人很早就发现了它们。$220 = 2^2 \times 5 \times 11$，其真因数之和是 ；而 ，其真因数之和是 。两数之间形成了一个完美的闭环——你中有我，我中有你。中世纪阿拉伯数学家甚至认为在护身符上刻下这对数字能让两人感情长久，数学与浪漫达到了一种难以置信的交汇。此后费马在 年发现了第二对亲和数 和 ，欧拉则用系统方法一口气找到了六十余对。今天已知的亲和数对超过十二亿，但对于"亲和数对是有限多还是无限多"这个问题，同样还没有答案。

例题精讲

例题一：综合整除性判别

题目：判断 $N = 32415$ 能否分别被 $3$、$5$、$9$ 整除，并说明理由。

例题二：因数个数的计算

题目：求 $n = 120$ 的所有正因数，并验证因数个数公式。

例题三：由整除条件推导整除结论

题目：若 $6 \mid n$ 且 $15 \mid n$，判断 $10$、$30$、$45$、$90$ 各是否一定整除 $n$。

例题四：整除性质的证明

题目：利用整除的定义证明：若 $a \mid b$，则对任意正整数 $k$，有 $a \mid b^k$。

例题五：综合条件筛选

题目：在所有各位数字之和为 $15$、且被 $4$ 整除的三位数中，找出最小的那一个。

练习

练习一：证明：若 $d \mid a$ 且 $d \mid b$，则对任意整数 $m, n$，有 $d \mid (ma + nb)$。这是整除线性组合性质的一般形式，请自行给出完整证明。

练习二：找出 $n = 360$ 的所有正因数的个数，并挑战：$360$ 的所有正因数之和是多少？

练习三：一个正整数 $n$ 满足：它的所有正因数之和（包括自身）恰好等于 $2n$，证明这等价于 $n$ 是完全数的定义。

要点收束

整除关系是整数世界里最基础的纽带，也是数论几乎所有深层结果的起点。从定义 $a \mid b \iff b = aq$ 出发，我们建立了整除的性质体系：传递性保证整除关系可以沿链传播，线性组合性质保证对两个整除对象的任意"线性混搭"都能整除，大小约束保证因数的个数有限。这些性质构成了证明整除命题的基本工具箱，其中"把整除关系翻译为倍数表示，做代数变形后提取公因子"是贯穿始终的标准操作。

整除判别规则把抽象性质落到了实际计算中：末位、末两位、数字之和分别对应 $2/5$、$4$、$3/9$ 的判别，背后的统一道理是 $10^k$ 在各模数下的余数结构。因数个数公式 $\tau(n) = \prod (a_i + 1)$ 把质因数分解与组合计数融为一体，是整除理论向计数论延伸的第一步。完全数与亲和数则提醒我们，因数和这个简单的概念背后藏着至今无解的深层谜题。整除世界，远比它的定义看起来丰富，而这里建立的每一块砖，都将在公因数、质数分解与同余理论里再次发挥作用。

由于 $mp + nq$ 是整数，所以 $d \mid (ma + nb)$。$\square$

这个证明结构几乎是整除证明的"模板"：把整除关系翻译成倍数表示，做代数变形后提取公因子，最后验证剩余部分是整数。遇到任何形如"若干整除条件推出某线性组合也满足整除"的命题，这套流程都适用。

所有正因数之和用因数和公式（sigma 函数）计算：

其中每个括号里是对应质数幂次的等比数列求和：$1 + 2 + 4 + 8 = 2^4 - 1/(2-1) = 15$，$1 + 3 + 9 = 13$，$1 + 5 = 6$。这个公式与因数个数公式源于同样的独立选择思路，只是把"计数"换成了"求和"。

反之，若 $\sigma(n) = 2n$，则真因数之和 $= \sigma(n) - n = n$，满足完全数的定义。

两个条件完全等价。$\square$

这个等价式把完全数的定义与因数和函数 $\sigma$ 联系了起来，使得用因数个数公式类似的方法来系统研究完全数成为可能——欧拉正是用 $\sigma$ 函数的乘积性质证明了所有偶完全数必须是欧几里得形式。