欧几里得：素数为什么永远数不完

题目

证明：素数有无穷多个。

（素数：大于 1 且只能被 1 和自身整除的数，如 2、3、5、7、11……）

答案与解析

用欧几里得在《几何原本》里的绝妙反证法：

1. 假设素数只有有限个，记为 $p_1, p_2, \dots, p_n$。
2. 构造一个新数 $N = p_1 \times p_2 \times \cdots \times p_n + 1$。
3. $N$ 除以任何一个已知素数 $p_i$，余数都是 1，所以没有任何已知素数能整除 $N$。
4. 那么 $N$ 要么是一个新的素数，要么能分解成若干都不在列表里的新素数。
5. 总之，列表之外还有素数，与“素数只有这有限个”矛盾。

所以素数无穷多。∎

背后的数学

这大概是人类历史上最优雅的“无穷证明”之一。两千多年后，欧拉给出了另一种证明：若素数有限，则级数 $\sum \frac{1}{p}$ 收敛，可实际上它发散（约等于 $\ln\ln n$），从而素数必无穷。两种思路，一个靠构造、一个靠分析，殊途同归。