本节对应原书 PDF 第 266–269 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。

设 a,b 是两个整数，且 b\neq 0.如果存在整数 c 使 a=bc，则称 a 被 b 整除，或 b 整除 a，记作 b|a.此时，又称 a 是 b 的倍数，b 是 a 的因子.把 b 不整除 a 记作 b\nmid a.

例如，6 被 \pm 1,\pm 2,\pm 3 和 \pm 6 整除，6 有 8 个因子 \pm 1,\pm 2,\pm 3 和 \pm 6.由于正负因子是成对出现的，通常只考虑正因子.显然，任何正整数都有两个正因子：1 和它自己，称作它的平凡因子.除平凡因子之外的因子称作真因子.例如，2 和 3 是 6 的真因子.

设 a,b 是两个整数，且 b\neq 0，则存在唯一的整数 q 和 r，使

a=qb+r\qquad 0\leqslant r<|b|

这个式子称作带余除法.记余数 r=a\bmod b.

例如，15=3\times 4+3，15\bmod 4=3；-8=-3\times 3+1，-8\bmod 3=1；10=5\times 2+0，10\bmod 2=0.

显然，b|a 当且仅当 a\bmod b=0.

解读：带余除法里 0\leqslant r<|b| 这个范围是唯一性的全部来源——如果把 r 放宽到任意整数，商和余数就不再唯一.例中 -8\bmod 3=1 而不是 -2，正是因为余数必须非负.

不难验证，整除有下述性质：

性质 11.1.1 如果 a|b 且 a|c，则对任意的整数 x,y，有 a|xb+yc.

性质 11.1.2 如果 a|b 且 b|c，则 a|c.

性质 11.1.3 设 m\neq 0，则 a|b 当且仅当 ma|mb.

性质 11.1.4 如果 a|b 且 b|a，则 a=\pm b.

性质 11.1.5 如果 a|b 且 b\neq 0，则 |a|\leqslant|b|.

定义 11.1 如果正整数 a 大于 1 且只能被 1 和它自己整除，则称 a 是素数；如果 a 大于 1 且不是素数，则称 a 是合数.素数也称作质数.

例如，7 和 11 是素数，6 和 14 是合数.

合数与素数有下述性质：

性质 11.1.6 a>1 是合数当且仅当 a=bc，其中 1<b<a，1<c<a.

性质 11.1.7 合数必有素数因子，即设 a 是一个合数，则存在素数 p，使得 p|a.

性质 11.1.8 如果 d>1，p 是素数且 d|p，则 d=p.

性质 11.1.9 设 p 是素数且 p|ab，则必有 p|a 或者 p|b.

更一般地，设 p 是一个素数且 p|a_1a_2\cdots a_k，则必存在 1\leqslant i\leqslant k，使得 p|a_i.

注意：当 d 不是素数时，d|ab 不一定能推出 d|a 或 d|b.如，6|4\times 15，但 6\nmid 4 且 6\nmid 15.

解读：性质 11.1.9 是素数区别于一般整数的核心能力——"素数整除乘积则整除某一因子".性质 11.1.7 与它配合，才保证了下面的素因子分解唯一.

根据性质 11.1.7，任何大于 1 的整数要么是素数，要么可以分解成素数的乘积.这样的分解是唯一的，这就是下述算术基本定理，它表明素数是构成整数的"基本元素".

定理 11.1（算术基本定理） 设 a>1，则

a=p_1^{r_1}p_2^{r_2}\cdots p_k^{r_k}

其中，p_1,p_2,\cdots,p_k 是不相同的素数，r_1,r_2,\cdots,r_k 是正整数，并且在不计顺序的情况下，该表示是唯一的.

定理中的表达式称作整数 a 的素因子分解.下面是几个整数的素因子分解：

30=2\times 3\times 5
117=3^2\times 13
21\ 560=2^3\times 5\times 7^2\times 11
71\ 213=17\times 59\times 71
1024=2^{10}

设 a 可以素因子分解成定理中的形式，我们常说 a 含有 r_1 个 p_1，r_2 个 p_2，\cdots.今后有时需要把表达式推广成更一般的形式：r_1,r_2,\cdots,r_k 是非负整数，即 r_1,r_2,\cdots,r_k 可以等于 0.当 r_i=0 时，a 实际上不含 p_i.1 也可以表示成这种更一般的形式：所有的 r_i=0.当然，这种推广的表达式不再有唯一性.

显然，a 的因子只能含有 a 中的素因子.更准确地说，有下述推论.

推论 设 a=p_1^{r_1}p_2^{r_2}\cdots p_k^{r_k}，其中 p_1,p_2,\cdots,p_k 是不相同的素数，r_1,r_2,\cdots,r_k 是正整数，则正整数 d 为 a 的因子的充分必要条件是

d=p_1^{s_1}p_2^{s_2}\cdots p_k^{s_k}

其中 0\leqslant s_i\leqslant r_i，i=1,2,\cdots,k.

例 11.1 （1）21 560 有多少个正因子？

（2）10! 的二进制表示中从最低位数起有多少个连续的 0？

解 （1）前面已有 21\ 560=2^3\times 5\times 7^2\times 11.由推论，21 560 的正因子的个数为 4\times 2\times 3\times 2=48.

（2）10 以内的素数有 2,3,5,7.对不超过 10 的合数作素因子分解：

4=2^2,\quad 6=2\times 3,\quad 8=2^3,\quad 9=3^2,\quad 10=2\times 5

得

10!=2^8\times 3^4\times 5^2\times 7

故 10! 的二进制表示中从最低位数起有 8 个连续的 0.

解读：正因子个数 4\times 2\times 3\times 2 中每个乘数是"该素因子的指数 + 1"，即 2 可取 0,1,2,3 共 4 种；二进制末尾连续 0 的个数就是 2 的指数 8，因为每多一个因子 2 就相当于左移一位.

现在要问：有无穷多个素数吗？回答是肯定的.这是第 1 章中例 1.11 的推论.为完整起见，这里重新证明如下.

定理 11.2 有无穷多个素数.

证明 用反证法.假设只有有穷多个素数，设为 p_1,p_2,\cdots,p_n，令 m=p_1p_2\cdots p_n+1.显然，p_i\nmid m，1\leqslant i\leqslant n.因此，要么 m 本身是素数，要么存在大于 p_n 的素数整除 m，矛盾.

解读：这个证明的构造技巧是"把已知素数全乘起来再加 1"：加 1 之后余数恒为 1，所以 m 不被任何一个已知素数整除，只能引入新素数.

记 \pi(n) 为小于等于 n 的素数个数.例如，\pi(0)=\pi(1)=0，\pi(2)=1，\pi(3)=\pi(4)=2，\pi(5)=3.\pi(n) 描述了素数分布，表 11.1 表明 \frac{n}{\ln n} 是 \pi(n) 的很好近似.关于 \pi(n) 与 \frac{n}{\ln n} 的关系有下述定理，定理的证明超出了本书的范围.

表 11.1

n10^310^410^510^610^7
\pi(n)1681229959278 498664 579
\frac{n}{\ln n}1451086868672 382620 421
\frac{\pi(n)}{n/\ln n}1.1591.1321.1041.0851.071

定理 11.3 当 n\geqslant 67 时，

\ln n-\frac{3}{2}\leqslant\frac{n}{\pi(n)}\leqslant\ln n-\frac{1}{2}

由上述定理可得到下述结论.

推论（素数定理）

\lim_{n\to+\infty}\frac{\pi(n)}{n/\ln n}=1

检查一个正整数是否是素数称作素数测试.素数测试不仅有重大的理论价值，而且在密码学中有十分重要的应用.根据性质 11.1.6，任给一个正整数 a，只要对所有的 1<b<a，检查 b|a 是否成立，就能判断 a 是否是素数.下述定理可以明显地改进这个算法.

定理 11.4 如果 a 是一个合数，则 a 必有一个小于等于 \sqrt{a} 的真因子.

证明 由性质 11.1.6，a=bc，其中 1<b<a，1<c<a.显然，b 和 c 中必有一个小于等于 \sqrt{a}.否则，bc>(\sqrt{a})^2=a，矛盾.

推论 如果 a 是一个合数，则 a 必有一个小于等于 \sqrt{a} 的素因子.

证明 由定理，a 有小于等于 \sqrt{a} 的真因子 b.如果 b 是素数，则结论成立.如果 b 是合数，由性质 11.1.7 和性质 11.1.5 得知，b 有素因子 p<b\leqslant\sqrt{a}.根据性质 11.1.2，p 也是 a 的因子，结论也成立.

例 11.2 判断 157 和 161 是否是素数.

解 \sqrt{157} 和 \sqrt{161} 都小于 13，根据定理 11.4 的推论，只需检查它们是否有小于 13 的素因子.小于 13 的素数有：2,3,5,7,11.检查结果如下：

2\nmid 157,3\nmid 157,5\nmid 157,7\nmid 157,11\nmid 157，结论：157 是素数.

2\nmid 161,3\nmid 161,5\nmid 161,7|161(161=7\times 23)，结论：161 是合数.

10 以内的素数是 2,3,5,7，用它们除 100 以内大于 10 的数，删去所有能被它们整除的数，剩下的（含 2,3,5,7 在内）就是 100 以内的所有素数.如表 11.2 所示，其中画有 \backslash，/，-，\times 的数分别表示能被 2,3,5,7 整除的数.最后剩下 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89 和 97.这 25 个数就是 100 以内的全部素数.

再用这 25 个素数除 100^2=10\ 000 以内大于 100 的数，删去所有能被它们整除的数，可以得到 10 000 以内的所有素数.重复这个做法可以得到任意给定的正整数以内的所有素数.这个方法称作埃拉托斯特尼(Eratosthene)筛法.

表 11.2

\begin{array}{cccccccccc} ① & 2 & 3 & ④ & 5 & ⑥ & 7 & ⑧ & ⑨ & ⑩ \\ 11 & \bcancel{12} & 13 & \bcancel{14} & \bcancel{15} & \bcancel{16} & 17 & \bcancel{18} & 19 & \bcancel{20} \\ \bcancel{21} & \bcancel{22} & 23 & \bcancel{24} & \bcancel{25} & \bcancel{26} & \bcancel{27} & \bcancel{28} & 29 & \bcancel{30} \\ 31 & \bcancel{32} & \bcancel{33} & \bcancel{34} & \bcancel{35} & \bcancel{36} & 37 & \bcancel{38} & \bcancel{39} & \bcancel{40} \\ 41 & \bcancel{42} & 43 & \bcancel{44} & \bcancel{45} & \bcancel{46} & 47 & \bcancel{48} & \bcancel{49} & \bcancel{50} \\ \bcancel{51} & \bcancel{52} & 53 & \bcancel{54} & \bcancel{55} & \bcancel{56} & \bcancel{57} & \bcancel{58} & 59 & \bcancel{60} \\ 61 & \bcancel{62} & \bcancel{63} & \bcancel{64} & \bcancel{65} & \bcancel{66} & 67 & \bcancel{68} & \bcancel{69} & \bcancel{70} \\ 71 & \bcancel{72} & 73 & \bcancel{74} & \bcancel{75} & \bcancel{76} & \bcancel{77} & \bcancel{78} & 79 & \bcancel{80} \\ \bcancel{81} & \bcancel{82} & 83 & \bcancel{84} & \bcancel{85} & \bcancel{86} & \bcancel{87} & \bcancel{88} & 89 & \bcancel{90} \\ \bcancel{91} & \bcancel{92} & \bcancel{93} & \bcancel{94} & \bcancel{95} & \bcancel{96} & 97 & \bcancel{98} & \bcancel{99} & \bcancel{100} \end{array}

待核：表 11.2 原书用斜线、竖线、横线、叉号四种划法分别标记能被 2,3,5,7 整除的数，扫描件中划法可辨但无法用公式逐字还原；此处统一用 \bcancel{} 表示"已划去"，圈码表示被划去的数（原书圈码含义同"划去"）.

人们一直在寻找更大的素数.近代已知的最大素数差不多总是形如 2^n-1 的数.当 n 是合数时，2^n-1 一定是合数.设 n=ab，其中 a>1，b>1，有

2^{ab}-1=(2^a-1)(2^{a(b-1)}+2^{a(b-2)}+\cdots+2^a+1)

当 n 为素数时，2^2-1=3，2^3-1=7，2^5-1=31，2^7-1=127 都是素数，而 2^{11}-1=2047=23\times 89 是合数.设 p 为素数，称形如 2^p-1 的数为梅森(Marin Mersenne)数.到 2013 年年初共找到 48 个梅森素数，最大的梅森素数是 2^{57\ 885\ 161}-1，这个数超过 1700 万位.

解读：n 是素数只是 2^n-1 为素数的必要条件而非充分条件，2^{11}-1=2047 就是反例.梅森素数的下标 p 必须是素数，但素数下标并不保证结果是素数.