欧几里得定理及推论

一句话算法

把已知的所有素数乘起来再加一，这个新数一定会逼出一个“名单外”的素数。

问题模型

欧几里得定理说明：

等价地说，对于任意正整数 $n$，总能找到一个比 $n$ 更大的素数。

这个定理不是算法模板，但它是很多数论结论的基础：素数不会在某个位置停止，任何有限的素数列表都不可能包含全部素数。

核心直觉

假设你手里有一张素数名单：

$$p_1,p_2,\ldots,p_m$$

把它们全部乘起来，再加 $1$：

$$S=p_1p_2\cdots p_m+1$$

这个数有一个关键性质：它除以名单里的任意一个素数，余数都是 $1$。

也就是说，名单里的素数都不能整除 $S$。但任何大于 $1$ 的整数，要么自己是素数，要么能分解出素因子。因此 $S$ 必须带来一个新的素数。

算法步骤

这是一种证明思路，可以按下面的步骤记忆：

1. 假设只有有限个素数，记为 $p_1,p_2,\ldots,p_m$。

2. 构造新数：

   $$S=p_1p_2\cdots p_m+1$$

3. 对任意 $p_i$，都有：

   $$S \equiv 1 \pmod {p_i}$$

4. 所以没有任何 $p_i$ 能整除 $S$。

5. 但 $S>1$，它一定有素因子。

6. 这个素因子不在原来的素数列表中，和“列表已经包含所有素数”矛盾。

算法证明

定理：素数有无穷多个

使用反证法。

1. 假设：素数只有有限个：

   $$p_1,p_2,\ldots,p_m$$

2. 构造：

   $$S=p_1p_2\cdots p_m+1$$

3. 观察余数：对任意 $i$，

   $$S=p_1p_2\cdots p_m+1$$

   其中 $p_i$ 整除乘积 $p_1p_2\cdots p_m$，所以：

   $$S\equiv 1\pmod {p_i}$$

   因此：

   $$p_i\nmid S$$

4. 讨论 $S$：

   • 若 $S$ 是素数，则 $S$ 是一个新的素数，不在原列表里。
   • 若 $S$ 是合数，则 $S$ 至少有一个素因子 $q$。由于所有 $p_i$ 都不能整除 $S$，所以 $q$ 也不在原列表里。

5. 矛盾：无论哪种情况，都出现了原列表之外的素数。

所以“素数只有有限个”的假设错误，素数有无穷多个。

推论一：任意正整数之后都有更大的素数

对任意正整数 $n$，取所有不超过 $n$ 的素数组成列表：

$$p_1,p_2,\ldots,p_m$$

构造：

$$S=p_1p_2\cdots p_m+1$$

和上面一样，$S$ 不能被任何不超过 $n$ 的素数整除。

若 $S$ 是素数，则 $S>n$，得到一个大于 $n$ 的素数。

若 $S$ 是合数，设它的某个素因子为 $q$。因为 $q$ 不能是任何不超过 $n$ 的素数，所以：

$$q>n$$

因此，对于任意正整数 $n$，都存在素数 $q>n$。

推论二：任何有限素数集合都可以被扩展

设有限素数集合为：

$$A=\{p_1,p_2,\ldots,p_m\}$$

构造：

$$S=p_1p_2\cdots p_m+1$$

若 $q$ 是 $S$ 的任意素因子，则对所有 $p_i\in A$，都有：

$$p_i\nmid S$$

所以：

$$q\notin A$$

这说明任何有限素数集合都不是“完整的”，一定还能找到集合外的素数。

复杂度分析

这是一条数学定理，不是用于直接提交的算法，因此没有输入规模意义上的时间复杂度。

如果把“构造 $S$ 并检查因子”当作计算过程，数值会急剧变大，不适合作为寻找大素数的实用算法。它的价值在于证明“有限列表不可能穷尽所有素数”。

代码实现

本文不提供代码模板。若需要判断素数或筛出素数表，请参考本书的素数判定与素数筛章节。

测试用例

假设当前名单只有：

2 3 5

构造：

$$S=2\times 3\times 5+1=31$$

31 是素数，且不在原名单里。

再看一个 $S$ 不是素数的例子：

2 3 5 7 11 13

构造：

$$S=2\times 3\times 5\times 7\times 11\times 13+1=30031$$

而：

$$30031=59\times 509$$

这里 $30031$ 不是素数，但它的素因子 59 和 509 都不在原名单中。这正是欧几里得证明真正需要的结论。

应用分类详解

欧几里得定理的本质是“用反证法打破有限性假设”。它在竞赛中不常作为直接模板出现，但常作为数论证明、构造和反例分析的基础。

一、证明素数无限性

典型模式： 题目要求证明素数不会停止，或证明任意范围之后仍存在素数。

识别信号： 出现“无限多个素数”“大于任意给定整数的素数”。

核心建模： 假设素数有限，然后构造所有已知素数乘积加一。

应用场景	经典题目	核心思路
素数无限性证明	数论基础证明题	有限名单乘积加一
任意数之后有素数	推论证明题	取不超过 $n$ 的素数列表构造

二、构造不被一组素数整除的数

典型模式： 需要构造一个数，使它避开某个有限素数集合的整除。

识别信号： 出现“不能被这些素数整除”“构造新的质因子”。

核心建模： 对有限集合 $A$ 中所有素数做乘积，再加一或减一，让余数固定为 $1$ 或 $-1$。

三、反证法训练

典型模式： 要证明“不可能只有有限个对象”，或证明“任何有限列表都能被扩展”。

识别信号： 结论里有“不存在最大”“无限多个”“总能找到新的”。

核心建模： 先假设存在完整有限列表，再构造一个不在列表中的对象。

经典例题

1. 证明素数有无穷多个

直接使用欧几里得定理的标准证明。重点是说明 $S$ 不一定为素数，但它一定有名单外的素因子。

2. 证明任意正整数 $n$ 之后存在素数

取所有不超过 $n$ 的素数相乘再加一，分析这个数的素因子即可。

3. 构造一个不被给定素数集合整除的整数

给定有限素数集合 $\{p_1,p_2,\ldots,p_m\}$，构造 $S=p_1p_2\cdots p_m+1$。此时每个 $p_i$ 除 $S$ 的余数都是 $1$。

参考

• 本书素数判定与素数筛章节：math/numberTheory/prime/index.md
• 本书反证法章节：math/反证法.md