欧几里得定理

欧几里得定理（Euclid's theorem）是数论中的基本定理，定理指出素数的个数是无限的。该定理有许多著名的证明。

## 欧几里得的证明

欧几里得在他的著作《几何原本》（第九卷的定理20）提出了证明，大意如下：

对任何有限素数的集合${p_1, p_2, ..., p_n}$。在这里将会证明最少存在一个集合中没有的额外素数。令$P = p_1 p_2 ... p_n$及$q = P+1$。那么$q$是素数或者不是，二者必居其一：

- 如果$q$是素数，那么至少有一个素数不在有限素数集${p_1, p_2, ..., p_n}$中。
- 如果$q$不是素数，那么存在一个素数因子$p$整除$q$，如果$p$在我们的有限素数集中，$p$必然整除$P$(既然$P$是素数有限集中所有素数的积)；但是，已知$p$整除$P+1$($P+1 = q$)，如果$p$同时整除$P$和$q$，$p$必然整除$P$和$q$之差

$a$

$b$

$c$

$a \mid b$

$a \mid c$

$a \mid (b - c)$

—— $(P + 1) - P = 1$。但是没有素数能整除$1$，即有$p$整除$q$就不存在$p$整除$P$。因此$p$不在有限集${p_1, p_2, ..., p_n}$中。

这证明了：对于任何一个有限素数集，总存在一个素数不在其中。所以素数一定是无限的。

很多时候有人会错误地指出欧几里得是用了反证法，他们假设证明起初考虑的是所有自然数的集合，或是集合内含有$n$个最小的素数，而不是任何任意的素数集合。欧几里得证明用的不是反证法，而是证明了一个有限集合中没有任何拥有特殊性质的元素。当中并没有反论的部分，但集合中的任何元素都不可以整除1。

文献中存在数个版本的欧几里得证明，包括以下的：

正整数$n$的阶乘$n!$可被$2$至$n$的所有整数整除，这是由于它是这些数全部的乘积。因此$n!+1$并不能被$2$至$n$（包括$n$）的任何自然数所整除（所得的余数皆为$1$）。因此$n!+1$有两个可能性：是素数，或者能被大于$n$所整除。在任一个案中，对所有正整数$n$而言都存在最少一个比$n$大的素数。所以结论就是共有无限个素数。

## 欧拉的证明

另一个由瑞士数学家莱昂哈德·欧拉提出的证明，则使用了算术基本定理：每一个自然数都有一组独一无二的素因子排列。设$P$为所有素数的集合，欧拉写下了：

$$\prod_{p\in P} \frac{1}{1-1/p}=\prod_{p\in P} \sum_{k\geq 0} \frac{1}{p^k}=\sum_n\frac{1}{n}.$$

第一条等式是由乘积中每一项的等比数列公式所得。而第二个等式则是用于黎曼ζ函数的欧拉乘积。为了证实此点，可把乘积分配进和里面：

$$\begin{align} \prod_{p\in P} \sum_{k\geq 0} \frac{1}{p^k} & = \sum_{k\geq 0} \frac{1}{2^k} \times \sum_{k\geq 0} \frac{1}{3^k}\times\sum_{k\geq 0} \frac{1}{5^k}\times\sum_{k\geq 0} \frac{1}{7^k}\times\cdots \\[8pt] & =\sum_{k,\ell,m,n,\cdots \geq 0} \frac{1}{2^k 3^\ell 5^m 7^n \cdots}=\sum_n\frac{1}{n} \end{align}$$

在这个结果中，每一个素数积都出现了正好一次，因此由算术基本定理可得这个和等于所有自然数的和。

右边的和是发散的调和级数。因此左边的和也是发散的。由于乘积内每一个项都是有限的，所以其项数必须为无限；因此得出共有无限个素数。

## 埃尔德什的证明

埃尔德什·帕尔的第三种证明也是靠算术基本定理的。首先注意每一个自然数$n$都能被写成独一无二的

$$rs^2$$

其中$r$非平方数，或任何平方数的倍数（设$s$为能整除$n$的最大平方数，并使$r=\frac{n}{s^2}$）。此时假设素数的数量为有限，且其数量为$k$。由于每个素数只有一个非平方数的因子，所以根据算术基本定理，得出共有非平方数$2^n$个。（见组合#在集合中取出k项元素及$\sum_{r=0}^n \binom nr = 2^{n}$）

现在把一个正整数$N$固定，并考虑1与$N$之间的自然数。这些数每一个都能被写成$rs^2$，其中$r$为非平方数，$s^2$为平方数，例如：

$$\{(1\times 1), (2\times 1), (3\times 1), (1\times 4), (5\times 1), (6\times 1), (7\times 1), (2\times 4), (1\times 9), (10\times 1), \cdots \}$$

集合中共有$N$个不同的数。每一个都是由非方数和比$N$小的平方数组成。这样的平方数共有$\lfloor \sqrt{N}\rfloor$（见高斯符号的取底符号）。然后把这些小于$N$的平方数乘积与其余所有的非平方数相乘。这样得出的数一共有$2^k \lfloor \sqrt{N} \rfloor$个，各不相同，因此它们包括了所有我们集合里的数，甚至更多。因此，$2^k \lfloor \sqrt{N} \rfloor \geq N$。

由于此不等式对足够大的$N$并不成立，因此必须存在无限个素数。

## 弗斯滕伯格的证明

希勒尔·弗斯滕伯格于1950年代还是个大学生时，提出了一个使用点集拓扑学的证明。（见弗斯滕伯格对素数无限性的证明）

## 一些近期的证明

### 皮纳西科

胡安·帕布洛·皮纳西科（Juan Pablo Pinasco）写下了以下的证明。

设$p_1, \cdots, p_N$为最小的$N$个素数。然后根据容斥原理可得，少于或等如$x$又同时能被那些素数中其中一个整除的正整数的个数为

$$\begin{align} 1 + \sum_{i} \left[ \frac{x}{p_i} \right] - \sum_{i < j} \left\lfloor \frac{x}{p_i p_j} \right\rfloor & + \sum_{i < j < k} \left\lfloor \frac{x}{p_i p_j p_k} \right\rfloor - \cdots \\ & \cdots \pm (-1)^{N+1} \left\lfloor \frac{x}{p_1 \cdots p_N} \right\rfloor. \qquad (1) \end{align}$$

把全式除以$x$，并且让$x \rightarrow \infty$，得

$$\sum_{i} \frac{1}{p_i} - \sum_{i < j} \frac{1}{p_i p_j} + \sum_{i < j < k} \frac{1}{p_i p_j p_k} - \cdots \pm (-1)^{N+1} \frac{1}{p_1 \cdots p_N}. \qquad (2)$$

上式可被改写为

$$1 - \prod_{i=1}^N \left( 1 - \frac{1}{p_i} \right). \qquad (3)$$

若除了$p_1, \cdots, p_N$以外不存在其他素数的话，则式(1)与 $\lfloor x \rfloor$相等，而式(2)则等于$1$，但很明显地式(3)并不等于$1$。因此除了$p_1, \cdots, p_N$以外必须要存在其他素数。

### 黄

俊浩·彼得·黄（Junho Peter Whang）于2010年发表了使用反证法的证明。设$k$为任何正整数，$p$为素数。根据勒让德定理，则可得：

$$k! = \prod_{p\text{ prime}} p^{f(p,k)} \,$$

其中

$$f(p,k) = \left\lfloor \frac{k}{p} \right\rfloor + \left\lfloor \frac{k}{p^2} \right\rfloor + \cdots.$$

$$f(p,k) < \frac{k}{p} + \frac{k}{p^2} + \cdots = \frac{k}{p-1} \le k.$$

但若只存在有限个素数，则

$$\lim_{k\to\infty} \frac{\left(\prod_p p\right)^k}{k!} = 0,$$

（上式分子呈单指数增长，但斯特灵公式指出分母的增长速度比分子快），这样就违反了每一个$k$的分子要比分母大的这一点。

### 塞达克

菲利浦·塞达克（Filip Saidak）给出了以下的证明，当中没有用到归谬法 (而大部分欧几里得定理的证明都用了，包括欧几里得自己的证明)，而同时不需要用到欧几里得引理，也就是若素数$p$整除$ab$则也必能整除$a$或$b$。证明如下：

由于每个自然数（$\geq 2$）最少拥有一个素因子，所以两个相邻数字$n$和$n+1$必定没有共同因子，而乘积$n(n+1)$则比数字$n$本身拥有更多因子。因此普洛尼克数的链：1×2 = 2 {2}, 2×3 = 6 {2, 3}, 6×7 = 42 {2,3, 7}, 42×43 = 1806 {2,3,7, 43}, 1806×1807 = 3263443 {2,3,7,43, 13,139}, · · ·提供了一组素数集合无限增长的数列。

## 使用Π的无理性的证明

以欧拉乘积来表示π的莱布尼茨公式可得

$$\frac{\pi}{4} = \frac{3}{4} \times \frac{5}{4} \times \frac{7}{8} \times \frac{11}{12} \times \frac{13}{12} \times \frac{17}{16} \times \frac{19}{20} \times \frac{23}{24} \times \frac{29}{28} \times \frac{31}{32} \times \cdots \;$$

乘积的分子为奇数的素数，而每一个分母则是最接近分子的4的倍数。

若存在的素数是有限的话，上式所展示的就是Π是一个有理数，而分母是所有与素数多1或少1的4的倍数的乘积，而这点违反了Π实际上是无理数的这一点。

## 使用信息论的证明

亚历山大·沈（音译，Alexander Shen）与其他人发表了利用不能压缩性方法的证明：

设只存在$k$素数（$p_1, \cdots, p_N$）。由算术基本定理可得，任何正整数$n$都能被写成：

$$n = {p_1}^{e_1} {p_2}^{e_2} ... {p_k}^{e_k},$$

其中非负自然数$e_i$与素数的有限集合就足够重构任何数字。由于所有$i$都遵守$p_i \geqslant 2$，因此可得所有\$e_i \leqslant \lg n$（其中$\lg$代表底数为2的对数）。

由此可得$n$的编码大小（使用大O符号）：

$O(\text{prime list size} + k \lg \lg n) = O(\lg \lg n)$ 位元。

（其中prime list size为素数集合的大小）这编码比直接用二进制代表$n$要有效得多，二进制的话需要$N = O(\lg n)$位元。无损数据压缩的一个已被确立的结果指出，一般不可能把$N$位元的信息压缩到少于$N$位元。由于$\lg \lg n = o(\lg n)$，所以当$N$足够大时，以上的这个表示不成立。

因此，素数的数量必不能为有限。

## 参阅

- 狄利克雷定理
- 素数定理