数论——质数、整除与模运算

数论是研究整数的数学分支。如果你想理解质数、整除或模运算，那么你已经接触到数论的核心内容了。

质数是大于 $1$ 的整数，并且恰好只有两个正因数：$1$ 和它本身。整除讨论的是一个整数除以另一个整数时是否没有余数。模运算关注余数，因此也常被称为“钟表算术”。

数论研究什么

这三个概念是相互关联的：

• 质数是正整数的基本构件。
• 整除告诉你一个整数是否能恰好除尽另一个整数。
• 模运算把整除问题改写成余数问题。

例如，说“$a$ 能被 $n$ 整除”等价于说

$$a \equiv 0 \pmod n$$

所以，整除问题通常也可以改写成余数问题。

质数：整数的基本构件

质数从下面这些数开始：

$$2, 3, 5, 7, 11, 13, \dots$$

数字 $2$ 是唯一的偶质数。其他任何偶数都能被 $2$ 整除，因此不可能是质数。

如果一个大于 $1$ 的正整数不是质数，就叫做合数。例如，$21$ 是合数，因为

$$21 = 3 \cdot 7$$

质数之所以重要，是因为每个大于 $1$ 的整数都可以写成若干个质数的乘积，因子的顺序除外。这就是质因数分解背后的思想。

整除：一个数何时能恰好除尽另一个数

如果 $a$ 和 $b$ 是整数，且 $b \ne 0$，那么“$b$ 整除 $a$”表示存在一个整数 $k$，使得

$$a = bk$$

这记作

$$b \mid a$$

例如，$4 \mid 20$，因为 $20 = 4 \cdot 5$。但 $4 \nmid 22$，因为 $22$ 除以 $4$ 会有余数。

整除是因数、倍数、最大公因数和最小公倍数背后的基本语言。它也解释了我们熟悉的一些判别法：

• 如果一个数的个位是偶数，那么它能被 $2$ 整除。
• 如果一个数的个位是 $0$ 或 $5$，那么它能被 $5$ 整除。
• 如果一个数各位数字之和能被 $3$ 整除，那么这个数能被 $3$ 整除。

最后这条规则并不是技巧，它来自模运算。

模运算：研究余数的运算

如果两个整数除以 $n$ 后余数相同，就称它们在模 $n$ 意义下同余。我们记作

$$a \equiv b \pmod n$$

这表示 $n$ 整除 $a-b$。

例如，

$$17 \equiv 5 \pmod{12}$$

因为 $17$ 和 $5$ 除以 $12$ 的余数都是 $5$，同时也因为 $12$ 整除 $17 - 5 = 12$。

这很有用，因为你可以把一个数替换成与它同余但更简单的数。在 $12$ 小时制的钟表上，加上 $15$ 小时和加上 $3$ 小时效果相同，因为

$$15 \equiv 3 \pmod{12}$$

例题：为什么 $231$ 能被 $3$ 整除？

来看数字 $231$。

先把它写成按位展开的形式：

$$231 = 2 \cdot 100 + 3 \cdot 10 + 1$$

现在在模 $3$ 的意义下计算。因为

$$10 \equiv 1 \pmod 3$$

所以

$$100 = 10^2 \equiv 1^2 \equiv 1 \pmod 3$$

于是

$$231 \equiv 2 \cdot 1 + 3 \cdot 1 + 1 \equiv 2 + 3 + 1 = 6 \equiv 0 \pmod 3$$

因为 $231 \equiv 0 \pmod 3$，所以这个数能被 $3$ 整除。

这也解释了数位和判别法：在十进制中，$10$ 的每个幂在模 $3$ 意义下都同余于 $1$，因此整个数与它各位数字之和有相同的余数。

继续分解可得，

$$231 = 3 \cdot 77 = 3 \cdot 7 \cdot 11$$

所以 $231$ 是合数，不是质数。

数论中的常见错误

把 $1$ 当成质数

$1$ 不是质数。质数必须恰好有两个正因数，而 $1$ 只有一个。

忘记整除中的条件

记号 $b \mid a$ 只有在 $b \ne 0$ 时才有意义。因为不能除以零。

混淆相等与同余

$17 \equiv 5 \pmod{12}$ 并不表示 $17 = 5$。它表示两者相差一个 $12$ 的倍数。

过度依赖整除判别法

有些判别法之所以快捷，是因为十进制运算让它们特别方便。这并不意味着每个除数都有简单的数位判别规则。

数论会出现在哪里

在学校数学中，数论常出现在因式分解、余数问题、整除证明以及钟表类问题中。当你约分、寻找公因数，或解决带有循环规律的问题时，也会用到数论。

更深入一些看，质数和模运算在密码学与计算机科学中也非常重要。你不需要这些背景也能使用这些思想，但这能解释为什么数论会不断出现在实际应用中。

自己试一试

试着用同样的思路研究 $462$。先用各位数字之和判断它是否能被 $3$ 整除，再继续分解，判断它是质数还是合数。

如果你想检查自己的方法，可以在数学求解器中做一道类似的整除或余数问题，并把其中的模运算步骤与你自己的过程进行比较。