素数

素数（prime number），又称质数，是大于 1、只有 1 和自身两个正因数的整数，例如 2、3、5、7、11。大于 1 而不是素数的整数称为合数，例如 $12 = 3 \cdot 4$ 。0 和 1 既不是素数，也不是合数。

素数在乘法中扮演基本因子的角色。12 可以拆成 $3 \cdot 4$ ，再把 4 拆成 $2 \cdot 2$ ，得到 $12 = 2 \cdot 2 \cdot 3$ 。其中 2 和 3 已经不能继续拆成两个大于 1 的整数之积；分解便在素数处停下来。

为什么从 2 开始

1 只有一个正因数，不符合“恰有两个正因数”的定义。它在乘法中的作用也与素因子不同：给 $12 = 2 \cdot 2 \cdot 3$ 添上任何多个 1，都没有改变分解的信息。把 1 单独看作乘法的单位，就能直接讨论那些真正构成整数的因子。

2 是唯一的偶素数。任何大于 2 的偶数都含有因数 2，而这个因数既不是 1，也不是它自身。奇数则可能是素数，也可能是合数，例如 9、15、21 都有更小的因子。

素数定义在这里针对正整数。分解负整数时，可以先提出负号，再分解绝对值；0 则被每个正整数整除，不属于素数和合数的分类范围。

判断一个数是不是素数

判定 97 时，可以依次试除，但不必一直试到 96。若 $n = a b$ ，其中 $1 < a \leq b$ ，那么 $a^{2} \leq a b = n, a \leq \sqrt{n} .$ 所以合数总有一个不超过平方根的非平凡因数。若这个因数还不是素数，可以继续分解，最终得到一个同样不超过平方根的素因子。

97 的平方根在 9 与 10 之间，候选素因子只有 2、3、5、7。97 是奇数，不能被 2 整除；各位数字和为 16，不能被 3 整除；末位不是 0 或 5，不能被 5 整除；最后 $97 = 7 \cdot 13 + 6$ ，也不能被 7 整除。因此 97 是素数。数字和判据的理由可见同余。

再看 221。它的平方根小于 15，需要检查 2、3、5、7、11、13。前几个因子均不成功，但 $221 = 13 \cdot 17,$ 所以 221 是合数。平方根界包括等号，例如 49 的因数 7 就恰好等于其平方根。

这类试除法对较小的整数很直接：只要把规定范围的候选因子检查完，就能从“没有找到因子”推出素性。整数很大时，候选数量也会很大，因而还需要更高效的素性判定算法。

用筛法找出一整段素数

若要找出所有不超过 50 的素数，逐个对每个整数试除会重复很多工作。埃拉托色尼筛法改为一次删掉同一个素数的合数倍数。

先列出 2 到 50。保留 2，划去 4、6、8 等更大的偶数。下一个未被划去的数是 3，保留它，划去 9、12、15 等倍数；其中 6 已经在第一轮划去。接下来保留 5、7，分别处理它们的倍数。留下 $2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.$ 共有 15 个。

下图把保留的素数用金框标出，合数划去，角上的 p 表示首先筛掉它的素因子。例如 25 标 p=5，49 标 p=7；1 因不大于 1，从一开始就不参加筛选。图底的 π(50) 表示不超过 50 的素数个数。先看这两个平方位置，再看被 2、3 划去的整列数字，可以核对为什么只需四轮。

一到五十的数字表，十五个素数用金框保留，合数划线并标出首次筛除的素因子，二十五和四十九分别标五和七 — 筛到 7 后，所有不超过 50 的合数都有了对应的小素因子。

每个被划去的数都有一个比自身小的因子。反过来，任何不超过 50 的合数都有一个不超过 $\sqrt{50} < 8$ 的素因子，因此经过 2、3、5、7 四轮以后，所有合数都已被划去。

处理素数 p 时，从 $p^{2}$ 开始划就够了。比它小的倍数 $2 p, 3 p, \dots, (p - 1) p$ ，已经含有小于 p 的素因子，早先就被处理过。这个观察减少了重复标记，但保留了同一筛选结果。筛法名称与古希腊的 Eratosthenes 相联系，相关史料见 MacTutor 素数史。

整数分解为何总能完成

以 360 为例，可以先分成 $36 \cdot 10$ ： $360 = (2^{2} \cdot 3^{2}) (2 \cdot 5) = 2^{3} \cdot 3^{2} \cdot 5.$ 也可以先分成 $8 \cdot 45$ ，最终仍得到三个 2、两个 3、一个 5。算术基本定理说明，这不是该例的巧合：每个大于 1 的整数都有素数分解，而且除因子顺序外分解唯一。

先证明分解存在。使用强归纳法：假定小于 n 而大于 1 的整数都已有素数分解。如果 n 本身是素数，已经完成；否则写成 $n = a b$ ，其中 a、b 都大于 1 且小于 n。将它们各自的素数分解相乘，就得到 n 的分解。从最小的情形 n=2 开始，这个论证覆盖所有大于 1 的整数。

不同的拆分为何得到同一结果

唯一性依赖一个关键性质：若素数 p 整除乘积 ab，则 p 整除 a 或 b。 若 p 不整除 a，由于 p 的正因数只有 1 和 p，便有 $gcd (p, a) = 1$ 。裴蜀等式给出整数 u、v，使 $u p + v a = 1.$ 两边乘以 b，得到 $u p b + v a b = b$ 。左边第一项含因子 p，第二项由 $p ∣ a b$ 也被 p 整除，所以 p 整除 b。这叫欧几里得引理。对三个或更多因子的乘积，可以反复应用同一结论。

现在设某个整数有两份素数分解。第一份的首个素因子 p 整除第二份的整个乘积，因此整除其中某个素因子 q。素数 q 的正因数只有 1 和 q，而 $p > 1$ ，所以 $p = q$ 。从两份乘积中各约去一次这个因子，再对剩下的乘积重复。若一份先约尽而另一份还有素因子，就会得到 1 等于若干大于 1 的整数之积，这是不可能的。因此两份因子及其出现次数全部匹配。

素因子指数怎样描述全部因数

回到 $360 = 2^{3} \cdot 3^{2} \cdot 5$ 。它的每个正因数，都从这份因子清单中选择一些因子，故形式为 $2^{α} 3^{β} 5^{γ}, 0 \leq α \leq 3, 0 \leq β \leq 2, 0 \leq γ \leq 1,$ 其中各指数为整数。指数 α 有 4 种选择，β 有 3 种，γ 有 2 种；唯一分解保证不同的选择不会得到同一个数。因此正因数共有 $4 \cdot 3 \cdot 2 = 24$ 个。

与 $84 = 2^{2} \cdot 3 \cdot 7$ 比较时，共同因数不能使用只出现在一边的素数，也不能使用超过任何一边供给量的指数。于是最大公因数为 $gcd (360, 84) = 2^{2} \cdot 3 = 12.$ 共同倍数则至少要包含两边要求的全部因子，各素数取较大指数，得到 $lcm (360, 84) = 2^{3} \cdot 3^{2} \cdot 5 \cdot 7 = 2520.$ 复核有 $12 \cdot 2520 = 360 \cdot 84$ ，与最大公因数和最小公倍数的乘积关系一致。

完全平方数也能由指数辨认。一个整数平方时，每个素因子的指数都加倍，因此全为偶数；反过来，若所有指数都是偶数，把指数减半便得到整数平方根。360 中 2 与 5 的指数为奇数，所以它不是完全平方数。

同样的整除性质还可证明素数的平方根是无理数。假设 $\sqrt{p} = a / b$ ，其中 a、b 为互素正整数，则 $a^{2} = p b^{2}$ 。由素数引理， $p ∣ a$ ，令 $a = p c$ ，代入并约去一个 p，得到 $p c^{2} = b^{2}$ 。再用引理得 $p ∣ b$ ，与 a、b 互素矛盾。

素数是否会在某处用完

假设已经列出有限多个素数 $p_{1}, \dots, p_{k}$ ，把它们相乘再加 1： $N = p_{1} p_{2} \dots p_{k} + 1.$ 清单中的每个素数除 N 都余 1，所以没有一个能整除 N。但 $N > 1$ ，一定有素因子；这个素因子必定不在清单中。因此任意有限清单都不能列完素数，素数有无限多个。

构造出的 N 本身未必是素数。例如取前六个素数， $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509.$ 虽然得到合数，它的素因子仍在原清单之外，这已经足够完成论证。欧几里得《几何原本》第九卷命题二十给出了超出任意有限素数清单的论证，原文见 Joyce 编注的 IX.20。

无限多也允许相邻素数之间出现很长的空档。给定正整数 m，取 $N = (m + 1)!$ ，这里的阶乘表示从 1 到 m+1 的整数连乘。于是 $N + 2, N + 3, \dots, N + m + 1$ 分别被 2、3、……、m+1 整除，而且每项都大于相应因数。这就构成连续 m 个合数。m 可以任意大，故合数连续出现的长度没有固定上界。

从素性检验到整体分布

试除和筛法提供确定的因子检验；有些更快的检验则利用同余性质。费马小定理说，若 p 为素数且 p 不整除 a，则 $a^{p - 1} \equiv 1 (\mod p) .$ 同余符号表示两边除以 p 有相同余数。若某个整数不满足相应等式，就可以排除它是素数；满足等式，却还可能是合数。

例如 $341 = 11 \cdot 31$ ，而 $2^{10} = 1024 = 3 \cdot 341 + 1$ 。连续相乘可得 $2^{340} = (2^{10})^{34} \equiv 1 (\mod 341)$ 。341 因而通过了底数 2 的这项检验。费马小定理给出素数应有的性质，这个例子说明该性质本身还不足以反推素性。

另一个研究方向是不再逐个判定，而是统计素数有多少。记 $π (x)$ 为不超过 x 的素数个数，例如上面的筛选得到 $π (50) = 15$ 。素数定理指出 $lim_{x \to \infty} \frac{π (x)}{x / \log x} = 1,$ 其中 $\log$ 为自然对数。它说明 $x / \log x$ 给出了大范围计数的相对近似，不是每个 x 处的精确等式。证明需要进一步的分析方法。

Hadamard 与 de la Vallée Poussin 在 1896 年分别证明了素数定理。MacTutor 素数史记录了从古代无限性和筛法，到近代整体分布研究的发展。素数虽然没有固定的等距排列，却具有唯一分解、可检验的整除规律，以及可精确表述的分布定理。

参考资料

Karl-Dieter Crisman，Number Theory: In Context and Interactive：素数、筛法、分解与分布。
同书，To Infinity and Beyond。
Euclid，Elements，IX.20，David Joyce 编注。
J. J. O’Connor、E. F. Robertson，Prime numbers。
相关条目：整数整除、同余、逻辑。