歐幾里得定理

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

歐幾里得的證明

歐幾里得在他的著作《幾何原本》（第九卷的定理20）^[1]提出了證明，大意如下^[2]：

對任何有限質數的集合${\displaystyle {p_{1},p_{2},...,p_{n}}}$。在這裏將會證明最少存在一個集合中沒有的額外質數。令${\displaystyle P=p_{1}p_{2}...p_{n}}$及${\displaystyle q=P+1}$。那麼${\displaystyle q}$是質數或者不是，二者必居其一：

• 如果${\displaystyle q}$是質數，那麼至少有一個質數不在有限質數集${\displaystyle {p_{1},p_{2},...,p_{n}}}$中。

• 如果${\displaystyle q}$不是質數，那麼存在一個質數因子${\displaystyle p}$整除${\displaystyle q}$，如果${\displaystyle p}$在我們的有限質數集中，${\displaystyle p}$必然整除${\displaystyle P}$(既然${\displaystyle P}$是質數有限集中所有質數的積)；但是，已知${\displaystyle p}$整除${\displaystyle P+1}$(${\displaystyle P+1=q}$)，如果${\displaystyle p}$同時整除${\displaystyle P}$和${\displaystyle q}$，${\displaystyle p}$必然整除${\displaystyle P}$和${\displaystyle q}$之差^[3] —— ${\displaystyle (P+1)-P=1}$。但是沒有質數能整除${\displaystyle 1}$，即有${\displaystyle p}$整除${\displaystyle q}$就不存在${\displaystyle p}$整除${\displaystyle P}$。因此${\displaystyle p}$不在有限集${\displaystyle {p_{1},p_{2},...,p_{n}}}$中。

這證明了：對於任何一個有限質數集，總存在一個質數不在其中。所以質數一定是無限的。

很多時候有人會錯誤地指出歐幾里得是用了反證法，他們假設證明起初考慮的是所有自然數的集合，或是集合內含有${\displaystyle n}$個最小的質數，而不是任何任意的質數集合^[4]。歐幾里得證明用的不是反證法，而是證明了一個有限集合中沒有任何擁有特殊性質的元素。當中並沒有反論的部分，但集合中的任何元素都不可以整除1。

文獻中存在數個版本的歐幾里得證明，包括以下的：

正整數${\displaystyle n}$的階乘${\displaystyle n!}$可被${\displaystyle 2}$至${\displaystyle n}$的所有整數整除，這是由於它是這些數全部的乘積。因此${\displaystyle n!+1}$並不能被${\displaystyle 2}$至${\displaystyle n}$（包括${\displaystyle n}$）的任何自然數所整除（所得的餘數皆為${\displaystyle 1}$）。因此${\displaystyle n!+1}$有兩個可能性：是質數，或者能被大於${\displaystyle n}$所整除。在任一個案中，對所有正整數${\displaystyle n}$而言都存在最少 一個比${\displaystyle n}$大的質數。所以結論就是共有無限個質數^[5]。

歐拉的證明

另一個由瑞士數學家萊昂哈德·歐拉提出的證明，則使用了算術基本定理：每一個自然數都有一組獨一無二的質因子排列。設${\displaystyle P}$為所有質數的集合，歐拉寫下了：

${\displaystyle \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}}.}$

第一條等式是由乘積中每一項的等比數列公式所得。而第二個等式則是用於黎曼ζ函數的歐拉乘積。為了證實此點，可把乘積分配進和裏面：

${\displaystyle {\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}}}$

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

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

艾狄胥的證明

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

${\displaystyle rs^{2}}$

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

現在把一個正整數${\displaystyle N}$固定，並考慮1與${\displaystyle N}$之間的自然數。 這些數每一個都能被寫成${\displaystyle rs^{2}}$，其中${\displaystyle r}$為非平方數，${\displaystyle s^{2}}$為平方數，例如：

${\displaystyle \{(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 \}}$

集合中共有${\displaystyle N}$個不同的數。每一個都是由非方數和比${\displaystyle N}$小的平方數組成。這樣的平方數共有${\displaystyle \lfloor {\sqrt {N}}\rfloor }$（見高斯符號的取底符號）。然後把這些小於${\displaystyle N}$的平方數乘積與其餘所有的非平方數相乘。這樣得出的數一共有${\displaystyle 2^{k}\lfloor {\sqrt {N}}\rfloor }$個，各不相同，因此它們包括了所有我們集合裏的數，甚至更多。因此，${\displaystyle 2^{k}\lfloor {\sqrt {N}}\rfloor \geq N}$。

由於此不等式對足夠大的${\displaystyle N}$並不成立，因此必須存在無限個質數。

弗斯滕伯格的證明

哈里·弗斯滕伯格（英語：Hillel Furstenberg）於1950年代提出了一個使用點集拓撲學的證明。（見弗斯滕伯格對質數無限性的證明（英語：Furstenberg's proof of the infinitude of primes））

一些近期的證明

皮納西科

胡安·帕布洛·皮納西科（Juan Pablo Pinasco）寫下了以下的證明^[6]。

設${\displaystyle p_{1},\cdots ,p_{N}}$為最小的${\displaystyle N}$個質數。然後根據容斥原理可得，少於或等如${\displaystyle x}$又同時能被那些質數中其中一個整除的正整數的個數為

${\displaystyle {\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}}}$

把全式除以${\displaystyle x}$，並且讓${\displaystyle x\rightarrow \infty }$，得

${\displaystyle \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)}$

上式可被改寫為

${\displaystyle 1-\prod _{i=1}^{N}\left(1-{\frac {1}{p_{i}}}\right).\qquad (3)}$

若除了${\displaystyle p_{1},\cdots ,p_{N}}$以外不存在其他質數的話，則式(1)與 ${\displaystyle \lfloor x\rfloor }$相等，而式(2)則等於${\displaystyle 1}$，但很明顯地式(3)並不等於${\displaystyle 1}$。因此除了${\displaystyle p_{1},\cdots ,p_{N}}$以外必須要存在其他質數。

黃

俊浩·彼得·黃（Junho Peter Whang）於2010年發表了使用反證法的證明^[7]。設${\displaystyle k}$為任何正整數，${\displaystyle p}$為質數。根據勒壤得定理，則可得：

${\displaystyle k!=\prod _{p{\text{ prime}}}p^{f(p,k)}\,}$

其中

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

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

但若只存在有限個質數，則

${\displaystyle \lim _{k\to \infty }{\frac {\left(\prod _{p}p\right)^{k}}{k!}}=0,}$

（上式分子呈單指數增長，但斯特靈公式指出分母的增長速度比分子快），這樣就違反了每一個${\displaystyle k}$的分子要比分母大的這一點。

塞達克

菲利浦·塞達克（Filip Saidak）給出了以下的證明，當中沒有用到歸謬法 (而大部分歐幾里得定理的證明都用了，包括歐幾里得自己的證明)，而同時不需要用到歐幾里得引理，也就是若質數${\displaystyle p}$整除${\displaystyle ab}$則也必能整除${\displaystyle a}$或${\displaystyle b}$。證明如下：

由於每個自然數（${\displaystyle \geq 2}$）最少擁有一個質因子，所以兩個相鄰數字${\displaystyle n}$和${\displaystyle n+1}$必定沒有共同因子，而乘積${\displaystyle n(n+1)}$則比數字${\displaystyle 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}, · · ·
提供了一組質數集合無限增長的數列。

使用π的無理性的證明

以歐拉乘積來表示π的萊布尼茨公式可得^[8]

${\displaystyle {\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）與其他人發表了利用不能壓縮性（英語：Incompressiblity method）的證明^[9]：

設只存在${\displaystyle k}$質數（${\displaystyle p_{1},\cdots ,p_{N}}$）。由算術基本定理可得，任何正整數${\displaystyle n}$都能被寫成：

${\displaystyle n={p_{1}}^{e_{1}}{p_{2}}^{e_{2}}...{p_{k}}^{e_{k}},}$

其中非負自然數${\displaystyle e_{i}}$與質數的有限集合就足夠重構任何數字。由於所有${\displaystyle i}$都遵守${\displaystyle p_{i}\geqslant 2}$，因此可得所有\${\displaystyle e_{i}\leqslant \lg n}$（其中${\displaystyle \lg }$代表底數為2的對數）。

由此可得${\displaystyle n}$的編碼大小（使用大O符號）：

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

（其中prime list size為質數集合的大小）這編碼比直接用二進制代表${\displaystyle n}$要有效得多，二進制的話需要${\displaystyle N=O(\lg n)}$位元。無損數據壓縮的一個已被確立的結果指出，一般不可能把${\displaystyle N}$位元的資訊壓縮到少於${\displaystyle N}$位元。由於${\displaystyle \lg \lg n=o(\lg n)}$，所以當${\displaystyle N}$足夠大時，以上的這個表示不成立。

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

參閱

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

註釋和參考資料

1. James Williamson (translator and commentator), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, page 63.
2. 歐幾里德主張的準確表述為：「質數比任何可以提出的量都要多」。在這個證明中，假定了最少存在三個質數，歐幾里得則由此推論出必存在第四個質數。
3. 一般來說，對任何整數${\displaystyle a}$、${\displaystyle b}$、${\displaystyle c}$而言，若${\displaystyle a\mid b}$和${\displaystyle a\mid c}$成立的話，則${\displaystyle a\mid (b-c)}$必成立。見整除性。
4. Michael Hardy and Catherine Woodgold, "Prime Simplicity", Mathematical Intelligencer, volume 31, number 4, fall 2009, pages 44–52.
5. Bostock, Linda; Chandler, Suzanne; Rourke, C. Further Pure Mathematics. Nelson Thornes. 2014-11-01: 168. ISBN 9780859501033 （英語）.
6. Juan Pablo Pinasco, "New Proofs of Euclid's and Euler's theorems", American Mathematical Monthly, volume 116, number 2, February, 2009, pages 172–173.
7. Junho Peter Whang, "Another Proof of the Infinitude of the Prime Numbers", American Mathematical Monthly, volume 117, number 2, February 2010, page 181.
8. Debnath, Lokenath, The Legacy of Leonhard Euler: A Tricentennial Tribute, World Scientific: 214, 2010 [2017-07-13], ISBN 9781848165267, （原始內容存檔於2016-07-30）.
9. Shen, Alexander, Kolmogorov complexity and algorithmic randomness (PDF), AMS: 245, 2016 [2017-07-13], （原始內容存檔 (PDF)於2017-08-21）

外部連結

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