整除与因数

上一节我们认识了整数，也学了带余除法。

这一节只看一种特别重要的情况：余数刚好是 $0$。

比如 $12$ 颗糖分给 $4$ 个人，每人 $3$ 颗，刚好分完。我们就说 $12$ 能被 $4$ 整除。

整除是数论里非常基础的关系。后面学习因数、倍数、公因数、最小公倍数、质数分解，都会反复用到它。

整除的定义与基本记号

整除的直觉很简单：能不能分得刚刚好。

$12$ 颗糖分给 $4$ 个人，刚好分完，所以 $4$ 整除 $12$。

$12$ 颗糖分给 $5$ 个人，会剩下 $2$ 颗，所以 $5$ 不能整除 $12$。

这个定义里有两个点要注意。

第一，除数不能是 $0$。所以定义里要求 $a \neq 0$。

第二，商 $q$ 必须是整数。它可以是正数，也可以是负数。

比如：

因为：

再比如：

因为：

但：

因为 $20$ 除以 $7$ 会余 $6$，不能写成 $20 = 7q$ 的样子。

还要注意，$a \mid b$ 不是分数。

它是一个判断句：要么成立，要么不成立。

整除的基本性质

整除有几条常用性质。

它们看起来不难，但后面做题会一直用到。

第一，任何非零整数都整除自己：

因为：

第二，$1$ 整除任何整数：

因为：

第三，任何非零整数都整除 $0$：

因为：

第四，整除可以传递。

如果：

那么：

比如 $3 \mid 6$，$6 \mid 24$，所以 $3 \mid 24$。

原因也很直接。

如果 $b = aq_1$，$c = bq_2$，那么：

所以 $a$ 也能整除 $c$。

还有一条特别常用的性质，叫线性组合性质。

如果 $a$ 能整除 $b$，也能整除 $c$，那么 $a$ 也能整除它们的整数倍相加减：

其中 $m,n$ 都是整数。

比如 $6 \mid 12$，$6 \mid 18$。

那么：

也有：

这条性质的核心意思是：如果两个数都含有同一个因数，那么它们做整数倍的加减后，这个因数通常还会保留下来。

最后还有一个直觉很强的结论。

如果 $a \mid b$，并且 $b \neq 0$，那么 $a$ 的绝对值不会比 $b$ 的绝对值更大：

所以，一个非零整数的因数只有有限多个。

整除的判别规则

有时我们不想真的做除法。

比如看到一个很大的数，想快速判断它能不能被 $2$、$3$、$5$、$9$ 整除。

这时就可以用判别规则。

被 $2$ 整除：看个位。

如果个位是 $0,2,4,6,8$，这个数就能被 $2$ 整除。

比如 $318$ 的个位是 $8$，所以 $2 \mid 318$。

被 $5$ 整除：也看个位。

如果个位是 $0$ 或 $5$，这个数就能被 $5$ 整除。

比如 $725$ 的个位是 $5$，所以 $5 \mid 725$。

被 $10$ 整除：个位必须是 $0$。

比如 $430$ 能被 $10$ 整除，$435$ 不能。

被 $4$ 整除：看末两位。

如果末两位组成的数能被 $4$ 整除，原来的数就能被 $4$ 整除。

比如 $3128$ 的末两位是 $28$，而 $28 = 4 \times 7$，所以 $4 \mid 3128$。

被 $3$ 整除：看各位数字之和。

比如 $12345$ 的数字和是：

$15$ 能被 $3$ 整除，所以 $12345$ 也能被 $3$ 整除。

被 $9$ 整除：也看各位数字之和。

如果数字和能被 $9$ 整除，原数就能被 $9$ 整除。

比如 $12345$ 的数字和是 $15$，不能被 $9$ 整除，所以 $12345$ 不能被 $9$ 整除。

被 $6$ 整除：要同时满足两个条件。

一个数能被 $6$ 整除，等价于它既能被 $2$ 整除，又能被 $3$ 整除。

比如 $324$ 的个位是 $4$，所以能被 $2$ 整除。

它的数字和是 $3+2+4=9$，所以也能被 $3$ 整除。

因此：

因数与倍数的结构

如果 $a \mid n$，那么 $a$ 是 $n$ 的因数，$n$ 是 $a$ 的倍数。

比如：

所以 $4$ 是 $36$ 的因数，$36$ 是 $4$ 的倍数。

要找一个数的所有因数，可以用“配对”的方法。

以 $36$ 为例：

所以 $36$ 的正因数是：

为什么只检查到 $6$ 就够了？

因为 $6 = \sqrt{36}$。如果一个因数比 $6$ 大，它的配对因数一定比 $6$ 小，前面已经找到了。

所以找因数时，不需要从 $1$ 一直试到 $n$，只要试到 $\sqrt{n}$ 附近就够了。

因数个数也可以用公式算。

如果：

那么 $n$ 的正因数个数是：

比如：

所以：

也就是说，$72$ 有 $12$ 个正因数。

为什么指数要加 $1$？

因为一个因数里，$2$ 的次数可以选 $0,1,2,3$，一共有 $4$ 种。

$3$ 的次数可以选 $0,1,2$，一共有 $3$ 种。

两边独立选择，所以共有 $4 \times 3 = 12$ 种。

完全数与亲和数

因数不只是用来做题，也能带出很多有趣的数。

先看完全数。

如果一个正整数等于它所有真因数的和，就叫完全数。

真因数就是“除了它自己以外的正因数”。

最小的完全数是 $6$。

因为 $6$ 的真因数是：

它们的和是：

所以 $6$ 是完全数。

$28$ 也是完全数。

它的真因数是：

而：

完全数很少见。数学家研究它们已经很久了。

再看亲和数。

亲和数是一对数。

如果 $a$ 的真因数之和等于 $b$，同时 $b$ 的真因数之和又等于 $a$，那么 $a$ 和 $b$ 就是一对亲和数。

最经典的一对是 $220$ 和 $284$。

$220$ 的真因数之和是 $284$。

$284$ 的真因数之和是 $220$。

这就像两个数互相“指向”对方。

完全数和亲和数都说明了一件事：因数看起来很普通，但里面藏着很多漂亮的问题。

例题精讲

例题一：综合整除性判别

题目：判断 $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$ 的意思是：$b$ 可以写成 $a$ 乘以某个整数。

整除关系让我们自然得到因数和倍数。

为了做题更方便，我们学习了几个常用判别规则，比如看个位、末两位、数字和。

找因数时，可以用配对法；数因数时，可以用质因数分解后的指数公式。

完全数和亲和数则告诉我们：因数的和也很有意思，里面藏着许多数论问题。

整除看起来只是“能不能除干净”，但它其实是后面学习公因数、最小公倍数、质数分解和同余的入口。

那么就说 $a$ 整除 $b$，记作

读作“$a$ 整除 $b$”，也可以说“$b$ 被 $a$ 整除”。

这时，$a$ 是 $b$ 的因数，$b$ 是 $a$ 的倍数。

如果不能整除，记作 $a \nmid b$。

所以 $120$ 应该有 $16$ 个正因数。

合起来，我们确定知道：

所以：

提取 $d$：

因为 $mp+nq$ 是整数，所以：

$\square$

如果继续求所有正因数之和，可以把每个质数的可能幂次分别加起来：

计算得：

所以 $360$ 有 $24$ 个正因数，所有正因数之和是 $1170$。

整理得：

反过来也一样。

如果 $\sigma(n)=2n$，那么：

也就是 $n$ 的真因数之和等于 $n$ 本身。

所以这两个说法等价。$\square$