素数与合数

把 $30$ 拆成两个正整数相乘，你可能先写 $3\times10$，我可能先写 $5\times6$。两条路看着不同，可继续拆下去，$10$ 变成 $2\times5$，$6$ 变成 $2\times3$，最后都剩下 $2$、$3$、$5$。换成更大的数，换个人来拆，难道也总会这样？

上一节我们用整除判断一个数是不是另一个数的因数，还用因数配对避免漏数。这一节要往里面再看一层：有些因数还能拆，有些已经拆不动了。先找出这些“拆不动的数”，再弄清为什么不同的分解路线会走到同一个终点，我们就能不用逐个试除，直接读出一个数有多少正因数。

哪些数已经拆不动了

想把 $12$ 颗棋子排成整齐的长方形，可以排成一行十二颗，也可以排成两行六颗、三行四颗。换成 $7$ 颗，除了排成一条长线，就没有别的排法了。这里“没有别的排法”，对应的正是 $7$ 没有介于 $1$ 和自身之间的正因数。

素数（也叫质数）是大于 $1$、正因数恰好只有 $1$ 和自身的整数。大于 $1$ 的整数中，不是素数的叫合数。例如 $7$ 是素数，而 $12$ 有额外的正因数 $2$，因此是合数。

为什么合数一定能拆成两个更小的数？设 $n$ 有一个正因数 $a$，满足 $1<a<n$。由整除的定义，$n=ab$，其中 $b$ 是整数；因为 $n$、 都是正数，而且 ，所以也有 。反过来，只要找到这样的乘积，就找到了一个额外因数。于是“合数”和“能写成两个大于 的整数的乘积”，说的是同一回事。

$1$ 要单独留下。它只有一个正因数，不能满足“恰好两个”的要求；又不能拆成两个大于 $1$ 的整数相乘，因此既不是素数也不是合数。$0$ 和负整数也不在这两类的定义范围内。我们虽然把 $0$ 算作自然数，讨论素数时仍须保留“大于 $1$”这个条件。

最小的素数是 $2$，它也是唯一的偶素数：其余偶数若大于 $2$，就能写成 $2$ 与一个大于 $1$ 的整数的乘积。不过，反过来说“奇数都是素数”就错了，$9=3\times3$、$15=3\times5$ 都是现成的反例。奇偶性可以帮我们排除一大批候选数，不能独自完成判断。

检查到哪里，才能放心停手

判断 $97$ 是不是素数，难道要把 $2$ 到 $96$ 都除一遍？如果真要这样，每遇到一个稍大的数，手算就会变成体力活。上一节的因数配对恰好能帮忙。

假如 $n$ 是合数，把它写成 $n=ab$，并让 $1<a\leq b$。如果连较小的 $a$ 都大于 $\sqrt n$，那么较大的 也大于 ，乘积就会大于 。所以合数一定有一个正因数落在下面的范围里：

这给出了试除法的停止条件：对于整数 $n>1$，若所有满足 $2\leq d\leq\sqrt n$ 的整数都不能整除 $n$，那么 就是素数。实际比较时可以用 ，无需先把平方根算成小数。

为什么只试素数就够了

还可以省下一些除法，但我们先把依据补齐。任何整数 $n>1$ 都有一个素因数，也就是一个能整除 $n$ 的素数。证明并不需要提前知道唯一分解定理：在 $n$ 的所有大于 $1$ 的正因数中，取最小的一个 $p$，这个集合非空，因为 $n$ 自己就在里面。若 $p$ 是合数，它还有正因数 满足 ；由 、，可知 ，这就与 最小矛盾。因此 必是素数。

现在回头看那个不超过 $\sqrt n$ 的因数 $a$。$a$ 自己有素因数 $p$，于是 $p\mid a\mid n$，而且 。这说明： 所以只试这个范围内的素数就足够；如果 能整除 ，我们试 时已经发现它了，其他合数同理。

对 $97$ 而言，$9^2<97<10^2$，只需要试 $2,3,5,7$。它是奇数，数字和为 $$，个位不是 或 ，因此前三个都不能整除它；最后 ，也不能被 整除。候选素因数全部排除， 就是素数。

再看 $143$，因为 $11^2<143<12^2$，这次必须试到 $11$。排除 $2,3,5$ 以后，，而 。找到一个真因数就够了，无须继续试， 是合数。

要找一整段素数，就把合数成批划掉

如果任务变成列出 $50$ 以内的所有素数，再对每个数分别试除，就会反复做同样的检查。埃拉托色尼筛法把问题倒过来：先写出 $2$ 到 $50$，用小素数的倍数批量标记合数，最后看谁还留下。

从 $2$ 开始，保留 $2$ 本身，划掉 $4,6,8,\ldots,50$。下一个没有划掉的是 $3$，保留它，划掉它的合数倍数。接下来 $4$ 已经划掉，跳过；$5$ 没有划掉，保留并处理它的倍数，再轮到 $$。

每一轮遇到的“下一个未划掉的数”为什么一定是素数？如果它是合数，就有一个更小的素因数；更小的素因数早已处理过，它本应已经被划掉了。这个矛盾保证我们不会把合数拿来当新的筛子。

还可以从 $p^2$ 开始划 $p$ 的倍数。因为排在 $p^2$ 前面的合数倍数都形如 $kp$，其中 $2\leq k<p$； 至少有一个素因数 ，所以 在处理更小的 时已经划过。举例说，轮到 时，、 被 筛掉， 被 筛掉，新的检查从 开始就行。

在 $50$ 以内，各轮真正新划掉的数是：

处理完 $7$ 就可以停止，因为下一个素数 $11$ 的平方已经超过 $50$。任何不超过 $50$ 的合数都必有一个不超过 $\sqrt{50}$ 的素因数，因而必定已经被筛掉。剩下的是：

一般地，筛到范围上限 $N$ 时，只需处理满足 $p^2\leq N$ 的素数，最后所有未划掉的数都是素数。若从 $1$ 开始写表，记得先把 $1$ 排除；它不是被某个素数筛掉的合数，也不能因为留下就算成素数。

拆到最后，为什么总是同一批素数

现在我们已经能认出素数了。回到开头的 $30$：不同的拆法最后都给出 $2\times3\times5$，会不会只是小数的巧合？要回答这个问题，需要分开证明两件事：第一，分解确实能走到终点；第二，不同路线的终点相同。

先保证分解一定存在

假设有大于 $1$ 的整数不能写成素数的乘积，从中取最小的一个，记作 $n$。这一步用的是前面学过的良序原理。

$n$ 不可能是素数，否则单独一个 $n$ 就已经是素数乘积。因此 $n$ 是合数，可以写成 $n=ab$，其中 $1<a<n$、$1<b<n$。由于 是最小的失败者，比它小的 、 都能分解成素数的乘积；把这两份乘积放在一起，就得到了 的素数分解，又矛盾了。

所以每个大于 $1$ 的整数都能分解成素数的乘积。直观上，不断拆开合数，每次分出的数都严格变小，不能永远拆下去；上面的最小反例证明把这个直觉说严密了。不过，“每条路都会结束”还不等于“每条路都在同一处结束”。唯一性要靠下面这个小结论。

素数整除乘积，必须抓住其中一个因子

$6$ 能整除 $2\times3$，却既不能整除 $2$，也不能整除 $3$。换成素数，这种“分散在两边才凑够”的现象就不会发生：若 $p$ 是素数、$a,b$ 是整数，且 $p\mid ab$，那么必有 或 。

先别用“把 $a,b$ 分解后看看”来证明它，因为我们正在证明分解为什么唯一，不能把想证明的结论偷偷用在中间。我们只借用带余除法和整数线性组合，从头把理由建起来。

如果 $p\mid a$，已经完成了。以下假设 $p\nmid a$。考虑所有形如 $xp+ya$ 的正整数，其中 $x,y$ 可以是任意整数，也可以为负。这个集合至少含有 $p=1\cdot p+0\cdot$，因此能取到最小的正数，记为：

我们先证明 $d$ 能整除 $p$。用 $d$ 去除 $p$，写成 $p=qd+r$，其中 $0\leq r<d$。把 的表达式代回余数：

所以 $r$ 仍是 $p$ 和 $a$ 的整数线性组合。假如 $r>0$，它就是这个集合里比 $d$ 更小的正数，与 $d$ 最小矛盾。于是 $r=0$，即 。

对 $a$ 做同样的带余除法，写成 $a=q'd+r'$，其中 $0\leq r'<d$，则：

同样由最小性得到 $r'=0$，所以 $d\mid a$。这里即使 $a$ 是负整数，带余除法仍然有效，因为除数 $d$ 为正。

$d$ 是素数 $p$ 的正因数，只能是 $1$ 或 $p$。但若 $d=p$，由 $d\mid a$ 就会得到 $p\mid$，与假设矛盾。所以 ，也就是存在整数 使：

终于可以回到原来的乘积了。两边乘以 $b$：

$p$ 能整除左边第一项，而条件 $p\mid ab$ 保证它也能整除第二项；由整除对加法的性质，$p$ 能整除整个左边，因此 $p\mid b$。这就证明了素数整除乘积的结论。

这段证明有一个值得记住的动作：从许多整数线性组合里取最小的正数，再用余数把它“逼”成公因数。下一节讲最大公因数时，我们会把这个动作发展成适用于任意两个整数的方法。

逐个配对，得到唯一性

如果同一个 $n>1$ 有两份素数分解：

那么左边的 $p_1$ 能整除右边整个乘积。刚证明的结论虽然写的是两个因子，但可以反复使用：先把右边分成 $q_1$ 与其余部分，若 $p_1$ 不整除 $q_1$，就继续检查其余部分。因此 一定能整除某一个 。

$q_j$ 本身是素数，正因数只有 $1$ 和自身；而 $p_1>1$，所以 $p_1=q_j$。把这两个相同的素数从等式两边约去，再对剩下的乘积重复同样的推理。

这个过程不可能只让一边先约完，而另一边还剩素数。约完的一边是空乘积，值为 $1$；另一边若还有至少一个素数，乘积至少为 $2$，两边不会相等。因此两边一定同时约完，每个素数都恰好配上，出现次数也相同。

存在性和唯一性合起来，就是算术基本定理：每个大于 $1$ 的整数，都能写成素数的乘积；忽略排列顺序，这个分解唯一。

把相同的素数合并成幂，通常写成：

其中 $p_1<p_2<\cdots<p_k$ 都是素数，各个 $\alpha_i$ 都是正整数。这样连顺序也固定了。 则对应没有任何素因子的空乘积；如果把 也当成素数，就能随意加进一个、两个乃至许多个 ，分解中因子的出现次数便不再唯一。

实际分解时怎么做

以 $360$ 为例，先反复除以 $2$，得到 $360\to180\to90\to45$，共取出三个 $2$；再反复除以 $3$，得到 $45\to15\to5$，共取出两个 。最后的 本身是素数，于是：

乘回去检查，$8\times9\times5=360$。若先拆成 $36\times10$，结果是 $(2^2\times3^2)(2\times5)$，合并后仍然一样，这正是唯一性在起作用。

试除时还可以随剩余部分缩小检查范围。例如分解 $202$，取出 $2$ 后剩 $101$；只要检查到 $\sqrt{101}$，排除 $2,3,5,7$ 就能认定剩下的 为素数，不必继续按照原来的 检查。每次停手时，依据的都是“剩余合数必有不超过自身平方根的素因数”。

一份分解，怎样读出全部正因数

上一节数正因数时，我们把它们两两配对。现在有了唯一分解，还能把“逐个找因数”改成“选择指数”。继续看 $360=2^3\times3^2\times5$。

$360$ 的一个正因数 $d$，能够含有多少个 $2$？零个、一个、两个、三个都可以，四个不行。对 $3$ 可以取零个、一个、两个，对 $5$ 可以取零个或一个。因此每个正因数都能写成：

为什么没有漏掉别的形状？若 $d\mid360$，存在正整数 $e$ 使 $de=360$。把 $d,e$ 都分解成素数后，由唯一性，它们不可能带入新的素数，每种素数的指数相加也必须等于 $360$ 中的指数。反过来，只要按上述范围选指数，剩下的指数能组成整数 $2^{3-a}{3}^2$，与 相乘就是 ，所以选出的数确实是因数。

正因数个数：把每个位置的选择数相乘

指数 $a$ 有 $4$ 种选择，$b$ 有 $3$ 种，$c$ 有 $2$ 种。各个选择互不限制，而且不同的指数组合不会产生同一个数，否则就违反唯一分解。因此 $360$ 有 $4\times3\times2=24$ 个正因数。

一般地，用 $\tau(n)$ 表示正整数 $n$ 的正因数个数。若 $n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}$，相应公式就是：

每个指数都要加 $1$，因为还包括“不选这个素数”的零次方。素数 $p$ 的分解只有 $p^1$，公式给出 $\tau(p)=2$；素数幂 $p^a$ 的因数为 ，正好有 个。 的唯一正因数是自身，所以 。

这个公式也重新解释了上一节的平方数现象。$\tau(n)$ 为奇数，当且仅当每个 $\alpha_i+1$ 都为奇数，即每个 $\alpha_i$ 都为偶数。而所有指数都是偶数，恰好意味着能将它们各取一半，写出 $n$ 的整数平方根。例如 ，它有 个正因数。于是正因数个数为奇数，当且仅当这个正整数是完全平方数， 也符合。

正因数和：让分配律替我们列举

正因数个数知道了，能不能连它们的和也直接算出来？观察下面的乘积：

展开时，每一项都是从三个括号里各取一项再相乘，恰好对应刚才的指数选择。每个正因数出现一次，也只出现一次，所以展开结果就是 $360$ 的全部正因数之和。

用 $\sigma(n)$ 表示这个和，包括 $1$ 和 $n$ 本身，便有：

若题目要的是“小于 $360$ 的正因数之和”，最后再减掉 $360$，得到 $810$。这两个问题只差一句话，答案却不同。

对于一般的素因数分解，同样得到：

这里 $\prod$ 表示把各项连乘。后一个写法来自等比求和：若 $S=1+p+\cdots+p^a$，则 $pS-S=p^{a+1}-1$，所以 。因为 ，分母不为零。单独看 时，直接由定义得到 。

我们没有先背两个孤立的公式。数因数是在数指数的选法，求因数和是把这些选法产生的数加起来，它们来自同一份清单。

素数会不会被找完

素数表越写越长，但“我还没找到最后一个”当然不等于“根本没有最后一个”。要证明素数有无穷多个，得有一个能对付任何有限名单的办法。

假设有人给出一份名单 $p_1,p_2,\ldots,p_k$，声称上面已经列出了全部素数。把名单里的数乘起来，再加 $1$：

这个 $N$ 除以名单里的任意一个 $p_i$ 都余 $1$，所以名单上的素数谁也不能整除它。但 $N>1$，我们已经证明它至少有一个素因数 $q$。$q$ 既然能整除 ，就不在名单里。于是这份号称完整的名单漏掉了一个素数，与假设矛盾。

这就是欧几里得证明中最巧的地方：你交来任何一份有限名单，他都能造出一个必须有“名单外素因数”的整数，因此素数不可能只有有限多个。

无穷多个，也可以隔得很远

知道素数永远找不完之后，还会出现一个似乎冲突的现象：连续很长一段数，完全可以一个素数都没有。

想构造连续五个合数，就取 $6!=1\times2\times3\times4\times5\times6=720$。那么 $722,723,724,725,726$ 分别能被 整除，而且每个数都大于相应除数，因此全是合数。

这个办法可以随意延长。给定正整数 $L$，令 $M=(L+1)!$，考察连续的 $L$ 个整数：

对每个 $2\leq j\leq L+1$，$j\mid M$，所以 $j\mid M+j$；又有 $$，故每一项都是合数。这证明任意长的连续合数段都存在。它与素数无穷并不矛盾：一段路可以很久没有素数，仍不代表再往前就永远没有。

再从整体看，用 $\pi(x)$ 表示不超过 $x$ 的素数个数。例如 $\pi(10)=4$，对应 $2,3,5,7$；这里的 $\pi(x)$ 是一个计数函数，与圆周率不是同一件事。

这些数字提示，范围变大时，素数的总数增加，所占比例却可以降低。更精确的素数定理说：

$\ln x$ 是自然对数；如果你还没学过极限，可以先把后半句理解为：$x$ 越大，这两个量的比值越接近 $1$。它描述的是大范围里的累计数量，不是说每隔 $\ln x$ 个整数就准时出现一个素数，也不保证逐段的素数间距越来越大。比如 $89$ 到 $97$ 相差 $8$，后面的 $$ 到 又只相差 。

这个定理的证明超出本课程范围，我们在这里用它认识整体趋势。前面的试除、筛法、唯一分解和素数无穷的证明都已经独立完成，不需要依赖它。

自己试一试

试除时别漏掉最后一个候选

判断 $221$ 和 $169$ 是否为素数；如果是合数，写出素因数分解，并说明检查范围。

用筛法看清一段素数表

用筛法列出 $30$ 以内的素数，说明处理 $5$ 时为什么只会新划掉 $25$。再计算这份表中相邻素数的差；这些差都不超过 $6$，能否据此断言所有相邻素数的差都不超过 $6$？

不列清单，数出因数并求和

求 $180$ 的素因数分解、正因数个数及正因数和，再求它的小于自身的正因数之和。

把“素数”这个条件用到位

设 $p$ 是素数、$n$ 是整数。证明：若 $p\mid n^2$，则 $p\mid n$，进而 $p^2\mid n^2$。如果把第一句话里的“素数 ”换成任意大于 的整数 ，结论还成立吗？

只给因数个数，反推这个数的形状

一个正整数恰好有三个正因数，证明它一定是某个素数的平方；反过来，素数的平方一定有三个正因数吗？

检查“乘积加一”的证明有没有偷换

有人写道：“对任意有限个素数 $p_1,\ldots,p_k$，数 $N=p_1\cdots p_k+1$ 不能被它们整除，所以 一定是素数，故素数无穷。”指出错误，并修好这段证明。

从一个数的分解，走向两个数的共同部分

现在，$360=2^3\times3^2\times5$ 已经不只是一道分解题的答案。它告诉我们哪些数能整除 $360$，这些正因数有多少个、加起来是多少；若再拿一个整数来比较，还能看出两者共享了哪些素因数。

不过，真要找两个大数的最大公因数，先把它们完整分解未必划算。下一节会从糖和饼干最多能平均分给多少人出发，看看为什么只要不断取余数，就能得到答案。我们在唯一性证明里见过的整数线性组合，也会在那里再次出现，并与这个取余过程连在一起。

对 $169$，$\sqrt{169}=13$，必须包含候选素数 $13$。排除 $2,3,5$ 后，$169=7\times24+1=11\times15+4$，再算得 $169=13^2$。两个数都是合数，也都说明“前面几个没除尽”不能代替检查完整范围。

留下 $2,3,5,7,11,13,17,19,23,29$，共十个。相邻差依次为 $1,2,2,4,2,4,2,4,6$。这只能说明当前有限范围的情况；例如 $89$ 与 $97$ 是相邻素数，差为 $8$。中间的偶数是合数，$91=7\times13$、$93=3\times31$、$95=5\times19$，确实没有漏掉别的素数。正文构造的任意长合数段还说明，相邻素数间距没有一个对所有素数都适用的固定上界。

正因数和为：

小于自身的正因数之和是 $546-180=366$。作为独立核对，$180$ 的正因数两两配成 $(1,180),(2,90),(3,60),(4,45),(5,36),(6,30),(9,20),(10,18),(12,15)$，共九对、十八个；各对之和相加为 $181+92+63+49+41+36+29+28+27=546$，与公式一致。

替换成合数就未必成立。取 $d=4,n=2$，有 $4\mid2^2$，却没有 $4\mid2$；也没有 $4^2\mid2^2$。不能把素数的乘积性质直接推广给任意整数。

反过来，若 $p$ 为素数，$p^2$ 的正因数只有 $1,p,p^2$，恰好三个。例如 $25$ 的正因数为 $1,5,25$，而 $16=2^4$ 有五个正因数，并非所有平方数都满足题目条件。