歐幾里得定理:歐幾里得定理是數論中的基本定理，定理指出素數的個數是無限的 -百科知識中文網

歐幾里得的證明

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

對任何有限素數的集合。在這裡將會證明最少存在一個集合中沒有的額外素數。令和。那么q是素數或者不是，二者必居其一：

1、如果q是素數，那么至少有一個素數不在有限素數集中。

2、如果q不是素數，那么存在一個素數因子p整除q，如果p在我們的有限素數集中， p必然整除 P(既然 P是素數有限集中所有素數的積)；但是，已知 p整除，如果 p同時整除P和q， p必然整除 P和q之差—— 。但是沒有素數能整除1，即有p整除q就不存在 p整除P。因此p不在有限集中。

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

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

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

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

歐拉的證明

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

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

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

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

埃爾德什的證明

埃爾德什·帕爾的第三種證明也是靠算術基本定理的。首先注意每一個自然數都能被寫成獨一無二的。其中非平方數，或任何平方數的倍數（設為能整除的最大平方數，並使）。此時假設素數的數量為有限，且其數量為。由於每個素數只有一個非平方數的因子，所以根據算術基本定理，得出共有非平方數個。（見組合#在集合中取出k項元素及）

現在把一個正整數固定，並考慮1與之間的自然數。這些數每一個都能被寫成，其中為非平方數，為平方數，例如：

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

由於此不等式對足夠大的並不成立，因此必須存在無限個素數。

近期的證明

皮納西科

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

設為最小的個素數。然後根據容斥原理可得，少於或等如又同時能被那些素數中其中一個整除的正整數的個數為

把全式除以，並且讓，得

上式可被改寫為

若除了以外不存在其他素數的話，則式(1)與相等，而式(2)則等於，但很明顯地式(3)並不等於1。因此除了以外必須要存在其他素數。

黃

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

其中

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

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

塞達克

菲利浦·塞達克（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}, · · ·
提供了一組素數集合無限增長的數列。