欧几里得反证法：如何证明素数有无穷多个

素数（只能被1和自身整除的数）有多少个？欧几里得在两千多年前就用一个简洁的反证法给出了答案：无穷多。下面按步骤拆解这个证明，让你自己也能一步步推出结论。

1. 准备好反证法的基本框架

反证法的核心思路是：先假设结论的反面成立，然后推导出矛盾，从而证明原结论正确。这里我们要证明“素数有无穷多个”，所以先假设相反情况——素数只有有限个。

2. 列出所有素数（假设的）

假设 素数只有 n 个，把它们全部写出来：p1, p2, p3, ..., pn。例如，若你认为最大素数是 13，那么这组数就是 2, 3, 5, 7, 11, 13。注意：这里的列表是“全部”，一个不漏。

3. 构造一个新数

计算 一个新数 N，公式如下：

$$N = p_1 \times p_2 \times p_3 \times \cdots \times p_n + 1$$

即，把列表里所有素数乘起来，再加1。以上面例子为例：2 × 3 × 5 × 7 × 11 × 13 = 30030，再加1得到 30031。

4. 考察这个新数的性质

检查 这个 N 除以列表中的任何一个素数 p_i 的余数。由于 N 等于 （p_i × 其他素数的积） + 1，所以：

• N ÷ p_i 的余数一定是 1。
• 也就是说，N 不能被任何一个已知素数整除。

5. 推导矛盾

现在，N 要么本身是一个素数，要么可以分解成若干个素数的乘积。但无论是哪种情况：

• 如果 N 是素数，那么它就是一个不在原列表中的新素数（因为原列表里的素数都不能整除它）。
• 如果 N 是合数，那么它必定有素因子，而这个素因子也不能是原列表中的任何一个（同样因为余数不为0），因此又出现了一个新素数。

无论哪种情况，都找到了原列表之外的素数。这与最初的假设“素数只有这 n 个”直接矛盾。

6. 得出结论

推翻 假设，即“素数只有有限个”是错的。因此，素数有无穷多个。 证明完成。