歐幾里得定理

歐幾里得定理（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$足夠大時，以上的這個表示不成立。

因此，素數的數量必不能為有限。

## 參閱

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