欧几里得定理是数论中的基本定理,定理指出素数的个數是无限的。该定理有许多著名的证明。
欧几里得在他的著作《几何原本》(第九卷的定理20)[1]提出了证明,大意如下[2]:
对任何有限素数的集合
。在这裡将会证明最少存在一个集合中沒有的额外素数。令
及
。那么
是素数或者不是,二者必居其一:
- 如果
是素数,那么至少有一个素数不在有限素数集
中。
- 如果
不是素数,那么存在一个素数因子
整除
,如果
在我们的有限素数集中,
必然整除
(既然
是素数有限集中所有素数的积);但是,已知
整除
(
),如果
同时整除
和
,
必然整除
和
之差[3] ——
。但是没有素数能整除
,即有
整除
就不存在
整除
。因此
不在有限集
中。
这证明了:对于任何一个有限素数集,总存在一个素数不在其中。所以素数一定是无限的。
很多时候有人会错误地指出欧几里得是用了反证法,他们假设证明起初考虑的是所有自然数的集合,或是集合內含有
个最小的素数,而不是任何任意的素数集合[4]。欧几里得证明用的不是反证法,而是证明了一個有限集合中沒有任何拥有特殊性质的元素。当中并沒有反论的部分,但集合中的任何元素都不可以整除1。
文献中存在数个版本的欧几里得证明,包括以下的:
正整数
的階乘
可被
至
的所有整数整除,这是由於它是这些数全部的乘积。因此
并不能被
至
(包括
)的任何自然数所整除(所得的余数皆为
)。因此
有兩个可能性:是素数,或者能被大于
所整除。在任一个案中,对所有正整数
而言都存在最少
一个比
大的素数。所以结论就是共有无限个素数[5]。
另一个由瑞士数学家莱昂哈德·欧拉提出的证明,则使用了算术基本定理:每一个自然数都有一组独一无二的素因子排列。设
为所有素数的集合,欧拉写下了:
![{\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}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4e893442cbf77959d6625bf98cb6ae1082102f0e)
第一条等式是由乘积中每一项的等比数列公式所得。而第二个等式则是用于黎曼ζ函数的欧拉乘积。为了证实此点,可把乘积分配进和裡面:
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d7a03346c59f44f9910104cbd6c74bf685073927)
在这个结果中,每一个素数积都出现了正好一次,因此由算术基本定理可得这个和等于所有自然数的和。
右边的和是发散的調和级数。因此左边的和也是发散的。由于乘积內每一个项都是有限的,所以其项数必须为无限;因此得出共有无限个素数。
埃尔德什·帕尔的第三种证明也是靠算术基本定理的。首先注意每一个自然数
都能被写成独一无二的
![{\displaystyle rs^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d250be48d7e4a9bafca879a104921ff38f62b388)
其中
非平方数,或任何平方数的倍数(设
为能整除
的最大平方数,并使
)。此時假设素数的数量为有限,且其数量为
。由於每个素数只有一个非平方数的因子,所以根据算术基本定理,得出共有非平方数
个。(見組合#在集合中取出k項元素及
)
現在把一个正整数
固定,并考虑1與
之间的自然数。 这些数每一个都能被写成
,其中
为非平方数,
为平方数,例如:
![{\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 \}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2a7774e84f59ef7b379d3313013bc91b5d53b318)
集合中共有
个不同的数。每一个都是由非方數和比
小的平方数组成。这样的平方数共有
(見高斯符号的取底符号)。然后把这些小於
的平方數乘积与其余所有的非平方数相乘。这样得出的数一共有
个,各不相同,因此它们包括了所有我们集合裡的数,甚至更多。因此,
。
由于此不等式对足够大的
並不成立,因此必须存在無限个素数。
哈里·弗斯滕伯格于1950年代提出了一个使用点集拓扑学的证明。(見弗斯滕伯格对素数无限性的证明)
胡安·帕布洛·皮纳西科(Juan Pablo Pinasco)写下了以下的证明[6]。
设
为最小的
个素数。然后根据容斥原理可得,少於或等如
又同時能被那些素数中其中一个整除的正整数的个数为
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/816a9cae28e981791439422b8df881604d5dd4ab)
把全式除以
,并且让
,得
![{\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)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d570e4f8661749dfdb392b28a261b03c1e9a7de2)
上式可被改写为
![{\displaystyle 1-\prod _{i=1}^{N}\left(1-{\frac {1}{p_{i}}}\right).\qquad (3)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c45aa5c531bc43454f1df81bc00082c8d7eca78)
若除了
以外不存在其他素数的话,则式(1)与
相等,而式(2)则等于
,但很明顯地式(3)并不等于
。因此除了
以外必须要存在其他素数。
俊浩·彼得·黃(Junho Peter Whang)于2010年发表了使用反证法的证明[7]。设
为任何正整数,
为素数。根据勒让德定理,则可得:
![{\displaystyle k!=\prod _{p{\text{ prime}}}p^{f(p,k)}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e435a8b8b0756a951d68daea71b7f5be1076ceb7)
其中
![{\displaystyle f(p,k)=\left\lfloor {\frac {k}{p}}\right\rfloor +\left\lfloor {\frac {k}{p^{2}}}\right\rfloor +\cdots .}](https://wikimedia.org/api/rest_v1/media/math/render/svg/974b72f6cc517e7a6bb4d86daaea56826e3c713e)
![{\displaystyle f(p,k)<{\frac {k}{p}}+{\frac {k}{p^{2}}}+\cdots ={\frac {k}{p-1}}\leq k.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/789c314c976d4234df909b46ecd7e33804b2cc16)
但若只存在有限个素数,則
![{\displaystyle \lim _{k\to \infty }{\frac {\left(\prod _{p}p\right)^{k}}{k!}}=0,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/db77b3374f27dbb5e41f579c61f353a31d37fefa)
(上式分子呈单指數增長,但斯特灵公式指出分母的增长速度比分子快),这样就违反了每一个
的分子要比分母大的这一点。
菲利浦·塞达克(Filip Saidak)给出了以下的证明,当中沒有用到归谬法 (而大部分欧几里得定理的证明都用了,包括欧几里得自己的证明),而同时不需要用到欧几里得引理,也就是若素数
整除
則也必能整除
或
。证明如下:
由于每个自然數(
)最少拥有一个素因子,所以兩个相邻数字
和
必定沒有共同因子,而乘积
則比数字
本身拥有更多因子。因此普洛尼克數的鏈:
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 \;}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1d0c5bd5cd1b1bcbe315b639da6f6161f147d0c9)
乘积的分子为奇数的素数,而每一个分母则是最接近分子的4的倍数。
若存在的素数是有限的话,上式所展示的就是π是一个有理数,而分母是所有與素数多1或少1的4的倍数的乘积,而这点违反了π实际上是无理数的这一点。
亞历山大·沈(音譯,Alexander Shen)与其他人发表了利用不能壓縮性的证明[9]:
设只存在
素数(
)。由算术基本定理可得,任何正整数
都能被写成:
![{\displaystyle n={p_{1}}^{e_{1}}{p_{2}}^{e_{2}}...{p_{k}}^{e_{k}},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ef2d472ac74346248f33a9f29cd2a855ed57a238)
其中非負自然数
與素数的有限集合就足够重构任何數字。由於所有
都遵守
,因此可得所有\
(其中
代表底数為2的对数)。
由此可得
的编码大小(使用大O符号):
位元。
(其中prime list size为素数集合的大小)这编码比直接用二进制代表
要有效得多,二进制的话需要
位元。无损数据压缩的一个已被确立的结果指出,一般不可能把
位元的信息压縮到少於
位元。由於
,所以當
足够大时,以上的这个表示不成立。
因此,素数的数量必不能为有限。
- ^ James Williamson (translator and commentator), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, page 63.
- ^ 欧几里德主张的準确表述为:“素数比任何可以提出的量都要多”。在这个证明中,假定了最少存在三个素数,欧几里得则由此推论出必存在第四个素数。
- ^ 一般來说,对任何整数
、
、
而言,若
和
成立的话,则
必成立。見整除性。
- ^ Michael Hardy and Catherine Woodgold, "Prime Simplicity", Mathematical Intelligencer, volume 31, number 4, fall 2009, pages 44–52.
- ^ Bostock, Linda; Chandler, Suzanne; Rourke, C. Further Pure Mathematics. Nelson Thornes. 2014-11-01: 168. ISBN 9780859501033 (英语).
- ^ Juan Pablo Pinasco, "New Proofs of Euclid's and Euler's theorems", American Mathematical Monthly, volume 116, number 2, February, 2009, pages 172–173.
- ^ Junho Peter Whang, "Another Proof of the Infinitude of the Prime Numbers", American Mathematical Monthly, volume 117, number 2, February 2010, page 181.
- ^ Debnath, Lokenath, The Legacy of Leonhard Euler: A Tricentennial Tribute, World Scientific: 214, 2010 [2017-07-13], ISBN 9781848165267, (原始内容存档于2016-07-30) .
- ^ Shen, Alexander, Kolmogorov complexity and algorithmic randomness (PDF), AMS: 245, 2016 [2017-07-13], (原始内容存档 (PDF)于2017-08-21)