素数比任何给定的素数个数都多。

— 欧几里得，《几何原本》命题 IX.20

素数 是大于 1、只能被 1 和它自身整除的整数：2、3、5、7、11、13……其余的数，比如 $12=2\cdot2\cdot3$，都是素数的乘积。素数是算术的原子。

越往后，素数越稀少。1 到 100 之间有 25 个素数；1 000 001 到 1 000 100 之间只有 6 个。它们会不会在某处就没了？欧几里得用一个四行的论证证明了不会，英国数学家哈代认为它是整个数学中最美的论证之一。

证明

假设有人给你一份有限的素数清单 $p_1,p_2,\ldots,p_n$。欧几里得证明，至少有一个素数 不在 清单上。把它们全部相乘再加 1：

$$N=p_1\cdot p_2\cdots p_n+1.$$

现在用清单上的任意一个素数去除 $N$。乘积 $p_1p_2\cdots p_n$ 能被它整除，所以 $N$ 除以它的余数是 1。清单上没有一个素数能整除 $N$。

但 $N$ 大于 1，所以它至少有一个素因子 $q$。为什么？取 $N$ 的大于 1 的最小因子。如果它不是素数，它就有一个更小的因子，而这个因子也整除 $N$，与"最小"矛盾。所以最小因子是素数。

这个素数 $q$ 整除 $N$，而清单上没有素数整除 $N$。所以 $q$ 不在清单上。任何有限的清单都不能包含所有素数：

$$\boxed{\text{素数有无穷多个。}}$$

欧几里得没有说"无穷"，这个词希腊人是回避的。他说的是：给定 任何 个数的素数，总还有更多。这是同一件事，只是说得很谨慎。

构造出的数不一定是素数

一个常见的错误是以为 $N$ 总是素数。请看：

清单 $N$ $N$ 是素数吗？
2 3 是
2, 3 7 是
2, 3, 5 31 是
2, 3, 5, 7 211 是
2, 3, 5, 7, 11 2 311 是
2, 3, 5, 7, 11, 13 30 031 不是：$30\,031=59\cdot509$

在第六行，$N$ 是合数。但它的因子 59 和 509 都是不在清单上的素数。证明从来没有说 $N$ 是素数；它只说有 某个 新素数整除 $N$。至今仍不知道表中这种构造能否产生无穷多个素数。

一个类似的证明：关于平方

同样风格的论证——先假设，再推出矛盾——可以证明 $\sqrt2$ 不是分数，这是《几何原本》第十卷讨论的另一个结果。如果 $\sqrt2=\frac pq$ 且分数已约分，那么 $p^2=2q^2$；$p^2$ 是偶数，所以 $p$ 是偶数，$p=2k$；于是 $4k^2=2q^2$，$q^2=2k^2$，$q$ 也是偶数。可是分数已经约分了。矛盾。

练习：从清单 3、5 出发，构造得到什么数？它揭示了哪个新素数？

$N=3\cdot5+1=16=2^4$。这个数是合数，它唯一的素因子 $2$ 不在清单上。不论清单是否从 2 开始，证明都成立。

练习：证明存在连续 5 个都不是素数的数。

取 $6!=720$。数 $720+2$、$720+3$、$720+4$、$720+5$ 和 $720+6$ 分别能被 2、3、4、5 和 6 整除，没有一个是素数。用 $(n+1)!$ 同样可以得到 $n$ 个连续的合数。素数永远不会穷尽，但它们之间的间隔可以要多大有多大。

来源： 《几何原本》命题 IX.20，D. E. Joyce 编 · G. H. 哈代，《一个数学家的辩白》· GIMPS，互联网梅森素数大搜索。

欧几里得的全部主题 · ← 欧几里得算法：最大公约数 · 第五公设与其他几何 →

图片来源.