素数有无穷多个的17个证明（1）

1. Euclid的证明

使用反证法．若只存在有限个素数，将所有素数从小到大依次排列为2=𝑝_(1)<𝑝_(2)<⋯<𝑝_(𝑟)，再设𝑃=𝑝_(1)𝑝_(2)⋯𝑝_(𝑟)+1，且𝑝为𝑃的一个素因子．由于𝑝_(1),𝑝_(2),⋯,𝑝_(𝑟)均不整除𝑃=𝑝_(1)𝑝_(2)⋯𝑝_(𝑟)+1，𝑝必为不同于它们的另一素数，这与𝑝_(1),𝑝_(2),⋯,𝑝_(𝑟)为所有素数矛盾，故素数有无穷多个．

在素数有无穷多个的所有证明中，Euclid的证明应该是最被大家熟知的一个了．
这个证明非常初等，此外，Euclid的证明能够进行一些改造从而给出素数分布的一些信息：
对任意𝑅≥2，存在一个素数𝑝，使得𝑅<𝑝≤𝑅^(𝑅)+1．
证明 将不大于𝑅的所有素数从小到大依次排列为2=𝑝_(1)<𝑝_(2)<⋯<𝑝_(𝑟)，再设𝑃=𝑝_(1)𝑝_(2)⋯𝑝_(𝑟)+1，且𝑝为𝑃的一个素因子．由于𝑝_(1),𝑝_(2),⋯,𝑝_(𝑟)均不整除𝑃=𝑝_(1)𝑝_(2)⋯𝑝_(𝑟)+1，𝑝必为不同于它们的另一素数．我们有𝑝≤𝑅^(𝑟)+1≤𝑅^(𝑅)+1，由于𝑝_(1),𝑝_(2),⋯,𝑝_(𝑟)为不大于𝑅的所有素数，故𝑝>𝑅．
注意到不超过𝑅的素数个数不超过(𝑅)/(2)+1，我们可以用𝑅^((𝑅)/(2)+1)来代替𝑅^(𝑅)+1．
当然，这是一个非常粗糙的估计．
Euclid的证明有很多的变体．

2. Kummer的证明

使用反证法．若只存在有限个素数，将所有素数从小到大依次排列为2=𝑝_(1)<𝑝_(2)<⋯<𝑝_(𝑟)，再设𝑁=𝑝_(1)𝑝_(2)⋯𝑝_(𝑟)>2，则正整数𝑁−1>𝑝_(𝑟)必有一个素因子𝑝_(𝑖)，于是𝑝_(𝑖)|𝑁−(𝑁−1)=1，这显然不成立，故素数有无穷多个．

Kummer的证明本质上和Euclid的证明一致，只不过Kummer的证明中考虑了𝑝_(1)𝑝_(2)⋯𝑝_(𝑟)−1，而Euclid 的证明中考虑了𝑝_(1)𝑝_(2)⋯𝑝_(𝑟)+1．同样地，我们可以由Kummer的证明得到：
对任意𝑅≥2，存在一个素数𝑝，使得𝑅<𝑝≤𝑅^(𝑅)−1．

3. Stieltjes的证明

使用反证法．若只存在有限个素数，设其为𝑝_(1),𝑝_(2),⋯,𝑝_(𝑟)．设𝑁=𝑝_(1)𝑝_(2)⋯𝑝_(𝑟)，将𝑁任意分解为两个正整数𝑚和𝑛的乘积，即𝑁=𝑚𝑛．注意到任意素数恰整除𝑚和𝑛其中之一，故必不整除𝑚+𝑛．而𝑚+𝑛>1，这显然不成立，故素数有无穷多个．

4. Goldbach的证明

首先证明Fermat数𝐹_(𝑛)=2^(2^(𝑛))+1（𝑛≥0）两两互素．
证明 注意到

公式：\begin{aligned} &F_m-2=2^{2^n}-1\\ =&\left(2^{2^{n}-1}+1\right)\left(2^{2^{n}-1}-1\right)\\ =&\cdots=F_0F_1\cdots F_{m-1}\text{．} \end{aligned}

于是公式：\gcd\left(F_m,F_n\right)=\gcd\left(F_m,2\right)=1．

由于有无穷多个Fermat数，而每一个Fermat数的素因子各不相同，故存在无穷多个素数．
注 前5个Fermat数：𝐹_(0)=3，𝐹_(1)=5，𝐹_(2)=17，𝐹_(3)=257，𝐹_(4)=65537均为素数．而𝐹_(5)=4294697297为合数，其最小的素因子为641．

5. Schorn的证明

使用反证法，假设只有𝑚个素数，令𝑛=𝑚+1．使用辗转相除法容易证明下列𝑛个正整数

两两互素．这𝑛个数的素因子各不相同，至少有𝑛个不同的素数，矛盾．故存在无穷多个素数．
Schorn的证明说明对于任意正整数𝑛，至少有𝑛个素数不大于𝑛⋅𝑛!+1．

6. Euler的证明

不同于以上的几个证明，Euler的证明使用了分析的方法．并且，Euler的方法在素数的分布问题上取得了巨大的进展．
设所有素数为𝑝_(1),𝑝_(2),⋯,𝑝_(𝑛)，注意到对于任意𝑝_(𝑖)，无穷级数

公式：\prod\limits_{i=1}^n\dfrac{1}{1-\dfrac{1}{p_i}}=\prod\limits_{i=1}^n\sum\limits_{k=0}^{\infty}\dfrac{1}{p_i^k}

同时，Euler也证明了素数的倒数和发散．
注意到对于任意正整数𝑁，有

公式：\ln\prod\limits_{p\leq N}\dfrac{1}{1-\dfrac{1}{p}}=-\sum\limits_{p\leq N}\ln\left(1-\dfrac{1}{p}\right)

且对于任意素数𝑝，有

公式：\begin{aligned} -\ln\left(1-\dfrac{1}{p}\right)=&\sum\limits_{m=1}^{\infty}\dfrac{1}{mp^m}\\ \leq&\sum\limits_{m=1}^{\infty}\dfrac{1}{p^m}\\ =&\dfrac{1}{p}+\dfrac{1}{p(p-1)}\\ < &\dfrac{1}{p}+\dfrac{1}{(p-1)^2}\text{．} \end{aligned}

于是

公式：\begin{aligned} \ln\sum\limits_{n=1}^N\dfrac{1}{n}\leq&\sum\limits_{p\leq N}\left(\dfrac{1}{p}+\dfrac{1}{(p-1)^2}\right)\\ \leq&\sum\limits_{p\leq N}\dfrac{1}{p}+\sum\limits_{n\leq N}\dfrac{1}{n^2} \end{aligned}

这说明了

公式：\sum\limits_{p\leq N}\dfrac{1}{p}\geq\ln\sum\limits_{n=1}^N\dfrac{1}{n}-c\geq \ln\ln N-C

7. Erdös的证明

设𝑝_(1)=2，𝑝_(2)=3，⋯，𝑝_(𝑗)为所有不超过𝑥的素数．设𝑛=𝑛21𝑚，其中𝑚无大于1的平方因子．于是

利用Erdös的方法，同样能够证明存在无穷多个素数．

证明 假设存在𝑀，使得

将不超过𝑁的正整数分成两个集合．设存在大于𝑀的素因子的正整数有𝑁_(1)个，其余正整数有𝑁_(2)个．于是有

由前面的证明可知𝑁_(2)<2^(𝑀)√(𝑁)．
于是当𝑁足够大时，有

矛盾．故素数有无穷多个．

8. Chebysheff的证明

我们用𝑣_(𝑝)(𝑛)表示𝑛的素因数分解中素数𝑝的次数．于是有

公式：\begin{aligned} v_p(n!)=&\sum\limits_{k=1}^{\infty}\left[\dfrac{N}{p^k}\right]\\ \leq& \sum\limits_{k=1}^{\infty}\dfrac{N}{p^k}\\ < & \dfrac{N}{p-1} \end{aligned}

且当𝑝>𝑛时，有𝑣_(𝑝)(𝑛!)=0．

于是

公式：\begin{aligned} \sum\limits_{p\leq n}\dfrac{\ln p}{p-1}>&\sum\limits_{p\leq n}\dfrac{v_p(n!)\ln p}{n}\\ =&\dfrac{1}{n}\ln{n!}\\ >&\ln n-1 \end{aligned}

于是𝑛→+∞时，有∑_(𝑝≤𝑛)(ln𝑝)/(𝑝−1)→+∞，由此说明素数有无穷多个．