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

欧几里得在他的著作《几何原本》（第九卷的定理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}$足够大时，以上的这个表示不成立。

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

• 狄利克雷定理
• 素数定理

• 埃里克·韦斯坦因. Euclid's Theorem. MathWorld. 
• Euclid's Elements, Book IX, Prop. 20 （页面存档备份，存于互联网档案馆） (Euclid's proof, on David Joyce's website at Clark University)