欧几里得定理

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

欧几里得的证明

欧几里得在他的著作《几何原本》（第九卷的定理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)