查看“︁欧几里得定理”︁的源代码

{{noteTA|G1=Math}}
'''欧几里得定理'''是[[数论]]中的基本定理，定理指出[[素数]]的个數是[[无限集|无限]]的。该定理有许多著名的证明。

== 欧几里得的证明 ==

[[欧几里得]]在他的著作《[[几何原本]]》（第九卷的定理20）<ref>James Williamson (translator and commentator), ''The Elements of Euclid, With Dissertations'', Clarendon Press, Oxford, 1782, page 63.</ref>提出了证明，大意如下<ref>欧几里德主张的準确表述为：“素数比任何可以提出的量都要多”。在这个证明中，假定了最少存在三个素数，欧几里得则由此推论出必存在第四个素数。</ref>：

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

* 如果<math>q</math>是素数，那么至少有一个素数不在有限素数集<math>{p_1, p_2, ..., p_n}</math>中。

* 如果<math>q</math>不是素数，那么存在一个素数因子<math>p</math>整除<math>q</math>，如果<math>p</math>在我们的有限素数集中，<math>p</math>必然整除<math>P</math>(既然<math>P</math>是素数有限集中所有素数的积)；但是，已知<math>p</math>整除<math>P+1</math>(<math>P+1 = q</math>)，如果<math>p</math>同时整除<math>P</math>和<math>q</math>，<math>p</math>必然整除<math>P</math>和<math>q</math>之差<ref>一般來说，对任何整数<math>a</math>、<math>b</math>、<math>c</math>而言，若<math>a \mid b</math>和<math>a \mid c</math>成立的话，则<math> a \mid (b - c)</math>必成立。見[[整除規则|整除性]]。</ref> —— <math>(P + 1) - P = 1</math>。但是没有素数能整除<math>1</math>，即有<math>p</math>整除<math>q</math>就不存在<math>p</math>整除<math>P</math>。因此<math>p</math>不在有限集<math>{p_1, p_2, ..., p_n}</math>中。

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

很多时候有人会错误地指出欧几里得是用了反证法，他们假设证明起初考虑的是所有自然数的集合，或是集合內含有<math>n</math>个最小的素数，而不是任何任意的素数集合<ref>Michael Hardy and Catherine Woodgold, "Prime Simplicity", ''Mathematical Intelligencer'', volume 31, number 4, fall 2009, pages 44–52.</ref>。欧几里得证明用的不是反证法，而是证明了一個有限集合中沒有任何拥有特殊性质的元素。当中并沒有反论的部分，但集合中的任何元素都不可以整除1。

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

正整数<math>n</math>的階乘<math>n!</math>可被<math>2</math>至<math>n</math>的所有整数整除，这是由於它是这些数全部的乘积。因此<math>n!+1</math>并不能被<math>2</math>至<math>n</math>（包括<math>n</math>）的任何自然数所整除（所得的余数皆为<math>1</math>）。因此<math>n!+1</math>有兩个可能性：是素数，或者能被大于<math>n</math>所整除。在任一个案中，对所有正整数<math>n</math>而言都存在最少
一个比<math>n</math>大的素数。所以结论就是共有无限个素数<ref>{{Cite book|url=|title=Further Pure Mathematics|last=Bostock|first=Linda|last2=Chandler|first2=Suzanne|last3=Rourke|first3=C.|date=2014-11-01|publisher=Nelson Thornes|year=|isbn=9780859501033|location=|pages=168|language=en}}</ref>。

== 欧拉的证明 ==

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

: <math>\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}.</math>

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

: <math>
\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}
</math>

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

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

== 埃尔德什的证明 ==

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

: <math>rs^2</math>

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

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

: <math>\{(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 \}</math>

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

由于此不等式对足够大的<math>N</math>並不成立，因此必须存在無限个素数。

== 弗斯滕伯格的证明 ==

[[希勒尔·弗斯滕伯格]]于1950年代還是個大學生時，提出了一个使用[[点集拓扑学]]的证明。（見{{le|弗斯滕伯格对素数无限性的证明|Furstenberg's proof of the infinitude of primes|}}）

== 一些近期的证明 ==

=== 皮纳西科 ===

胡安·帕布洛·皮纳西科（Juan Pablo Pinasco）写下了以下的证明<ref>Juan Pablo Pinasco, "New Proofs of Euclid's and Euler's theorems", ''American Mathematical Monthly'', volume 116, number 2, February, 2009, pages 172–173.</ref>。

设<math>p_1, \cdots, p_N</math>为最小的<math>N</math>个素数。然后根据[[容斥原理]]可得，少於或等如<math>x</math>又同時能被那些素数中其中一个整除的正整数的个数为

: <math>
\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}
</math>

把全式除以<math>x</math>，并且让<math>x \rightarrow \infty</math>，得

: <math> \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) </math>

上式可被改写为

: <math> 1 - \prod_{i=1}^N \left( 1 - \frac{1}{p_i} \right). \qquad (3) </math>

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

=== 黃 ===

俊浩·彼得·黃（Junho Peter Whang）于2010年发表了使用反证法的证明<ref>Junho Peter Whang, "Another Proof of the Infinitude of the Prime Numbers", ''American Mathematical Monthly'', volume 117, number 2, February 2010, page&nbsp;181.</ref>。设<math>k</math>为任何正整数，<math>p</math>为素数。根据[[勒让德定理]]，则可得：

: <math> k! = \prod_{p\text{ prime}} p^{f(p,k)} \, </math>

其中

: <math> f(p,k) = \left\lfloor \frac{k}{p} \right\rfloor + \left\lfloor \frac{k}{p^2} \right\rfloor + \cdots. </math>

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

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

: <math> \lim_{k\to\infty} \frac{\left(\prod_p p\right)^k}{k!} = 0, </math>

（上式分子呈单指數增長，但[[斯特灵公式]]指出分母的增长速度比分子快），这样就违反了每一个<math>k</math>的分子要比分母大的这一点。

=== 塞达克 ===

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

由于每个自然數（<math>\geq 2</math>）最少拥有一个素因子，所以兩个相邻数字<math>n</math>和<math>n+1</math>必定沒有共同因子，而乘积<math>n(n+1)</math>則比数字<math>n</math>本身拥有更多因子。因此[[普洛尼克數]]的鏈：<br>1×2 = 2 {2}, &nbsp; &nbsp;2×3 = 6 {2, 3}, &nbsp; &nbsp;6×7 = 42 {2,3, 7}, &nbsp; &nbsp;42×43 = 1806 {2,3,7, 43}, &nbsp; &nbsp;1806×1807 = 3263443 {2,3,7,43, 13,139}, · · ·<br>提供了一组素数集合無限增长的数列。

== 使用{{pi}}的無理性的证明 ==

以欧拉乘积来表示[[π的莱布尼茨公式]]可得<ref>{{citation|title=The Legacy of Leonhard Euler: A Tricentennial Tribute|first=Lokenath|last=Debnath|publisher=World Scientific|year=2010|isbn=9781848165267|page=214|url=https://books.google.com/books?id=K2liU-SHl6EC&pg=PA214|accessdate=2017-07-13|archive-date=2016-07-30|archive-url=https://web.archive.org/web/20160730155650/https://books.google.com/books?id=K2liU-SHl6EC&pg=PA214|dead-url=no}}.</ref>

:<math> \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 \; </math>

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

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

== 使用信息论的证明 ==

亞历山大·沈（音譯，Alexander Shen）与其他人发表了利用{{le|不能压缩性方法|Incompressiblity method|不能壓縮性}}的证明<ref>{{citation|title=Kolmogorov complexity and algorithmic randomness|first=Alexander|last=Shen|publisher=AMS|year=2016|url=http://www.lirmm.fr/~ashen/kolmbook-eng.pdf|page=245|accessdate=2017-07-13|archive-date=2017-08-21|archive-url=https://web.archive.org/web/20170821194859/http://www.lirmm.fr/~ashen/kolmbook-eng.pdf|dead-url=no}}</ref>：

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

:<math>n = {p_1}^{e_1} {p_2}^{e_2} ... {p_k}^{e_k},</math>

其中非負自然数<math>e_i</math>與素数的有限集合就足够重构任何數字。由於所有<math>i</math>都遵守<math>p_i \geqslant 2</math>，因此可得所有\<math>e_i \leqslant \lg n</math>（其中<math>\lg</math>代表底数為2的[[对数]]）。 

由此可得<math>n</math>的编码大小（使用[[大O符号]]）：

:<math>O(\text{prime list size} + k \lg \lg n) = O(\lg \lg n)</math> [[位元]]。

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

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

==参阅==
* [[狄利克雷定理]]
* [[素数定理]]

== 注释和参考资料 ==
{{reflist|2}}

==外部链接==
* {{MathWorld|urlname=EuclidsTheorems|title=Euclid's Theorem}}
* [http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html Euclid's Elements, Book IX, Prop. 20] {{Wayback|url=http://aleph0.clarku.edu/~djoyce/java/elements/bookIX/propIX20.html |date=20110123034101 }} (Euclid's proof, on David Joyce's website at Clark University)

[[Category:数学定理|O]]
[[Category:素数]]
[[Category:包含证明的条目]]