欧几里得定理

**歐幾里得定理**是數論中的基本定理，定理指出質數的個數是無限的。該定理有許多著名的證明。

## 歐幾里得的證明

歐幾里得在他的著作《幾何原本》（第九卷的定理 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$ 之差 —— $(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{aligned}\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{aligned}}$

在這個結果中，每一個質數積都出現了正好一次，因此由算術基本定理可得這個和等於所有自然數的和。

右邊的和是發散的調和級數。因此左邊的和也是發散的。由於乘積內每一個項都是有限的，所以其項數必須為無限；因此得出共有無限個質數。

## 艾狄胥的證明

艾狄胥・帕爾的第三種證明也是靠算術基本定理的。首先注意每一個自然數 $n$ 都能被寫成獨一無二的

　
: $rs^{2}$

其中 $r$ 非平方數，或任何平方數的倍數（設 $s$ 為能整除 $n$ 的最大平方數，並使 $r={\frac {n}{s^{2}}}$ ）。此時假設質數的數量為有限，且其數量為 $k$ 。由於每個質數只有一個非平方數的因子，所以根據算術基本定理，得出共有非平方數 $2^{n}$ 個。（見組合 #在集合中取出 k 項元素及 $\sum _{r=0}^{n}{\binom {n}{r}}=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{aligned}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{aligned}}$

把全式除以 $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}}\leq 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$ 足夠大時，以上的這個表示不成立。

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

## 參閱

* 狄利克雷定理
* 質數定理

## 注釋和參考資料

## 外部連結

* 埃里克・韋斯坦因. Euclid's Theorem. MathWorld.
* Euclid's Elements, Book IX, Prop. 20 （頁面存檔備份，存於網際網路檔案館） (Euclid's proof, on David Joyce's website at Clark University)