第一个证明是哥德巴赫(Goldbach)给出的，这个证明涉及的所谓 Fermat 数总会使得人们联想起费尔马（Fermat）和高斯（Gauss）！
我们的目的是指出任意两个 Fermat 数 \(F_n=2^{2^n}+1, n=0,1,2,\dotsc\) 互质. 下述关系式足以
\begin{equation}\prod_{i=0}^{n}F_i=F_{n+1}-2.\end{equation}
下面是Filip Saidak \(2005\) 年的证明, 发表在 “美国数学月刊” (Amer.Math.Monthly) \(2006\)年第\(113\)卷第\(10\)期\(937-938\):
任取不是 \(1\) 的自然数 \(m\), 由于 \(m\) 与 \(m+1\) 互质, 即 \((m,m+1)=1\), 于是
\begin{equation}a_1=m(m+1)\end{equation}
至少有 \(2\) 个不同的质因子.
同理, \((m(m+1),m(m+1)+1)=1\), 于是 \(m(m+1)\) 与 \(m(m+1)+1\) 有不同的质因子, 故而
\begin{equation}a_2=a_1(a_1+1)=m(m+1)(m(m+1)+1)\end{equation}
至少有 \(3\) 个不同的质因子.
很明显, 这个过程可以无限的继续下去, \(a_n=a_{n-1}(a_{n-1}+1)\), 于是 \(a_n\) 至少有 \(n+1\)个不同的质因子, 当然也就有 \(n+1\) 个不同的质数. \(n\) 可以是任意自然数, 因此也就有无限多个质数.
第三个证明与 Euler 的 \(\varphi\) 函数有关：
采用反证法.
假定只有有限个质数 \(p_1,p_2,\dotsc,p_l\), 考虑
\begin{equation}n=\prod_{i=1}^{l}p_i.\end{equation}
在所有不超过 \(n\) 的自然数中, 只有 \(1\) 与 \(n\) 是互质的, 其余的数都与 \(n\) 有共同的质因子, 于是
\begin{equation}\varphi(n)=1.\end{equation}
但是, 由 \(\varphi\) 的性质
\begin{equation}\varphi(n)=\prod_{i=1}^{l}(p_i-1)\end{equation}
不可能是 \(1\). 矛盾说明我们的假设不成立!
定义\(1\) 用 \(\Bbb P\) 表示全体质数所成的集合, 即
\begin{equation}\Bbb P := \{2,3,5,7,\dotsc\}.\end{equation}
定义\(2\) \(x>0\), 命
\begin{equation}\pi(x) := \#\{p\leq x|p\in\Bbb P \}\end{equation}
为不大于 \(x\) 的质数个数.
与前面的途径不同, 下面这个证明是对 \(\pi(x)\) 进行估计, 直接讨论数量的多寡, 此乃解析数论(analytic number theory)常用.
设 \(x\) 是一个正整数, 记 \(\leqslant x\) 的质数是 \(p_1,p_2,\dotsc,p_{\pi(x)}\). 考察不超过 \(x\) 的正整数 \(n\). 由算术基本定理,
\(n\) 有下述的分解式
\begin{equation}n=\prod_{i=1}^{\pi(x)}p_i^{\alpha_i},\end{equation}
其中 \(\alpha_1,\alpha_2,\dotsc,\alpha_{\pi(x)}\) 是非负整数. 于是有正整数 \(u,v\) 使得
\begin{equation}n=u^2v,\end{equation}
其中 \(v\) 无平方因子, 即
\begin{equation}v=\prod_{i=1}^{\pi(x)}p_i^{\beta_i},\end{equation}
这里每个 \(\beta_i\) 只能是 \(0\) 或 \(1\)(\(i=1,2,\dotsc,\pi(x)\)).
由 \(n\leqslant x\) 得 \(u\leqslant \sqrt x\), 所以 \(u\) 的种数 \(\leqslant \sqrt x\); 显而易见, \(v\) 的种数 \(\leqslant 2^{\pi(x)}\).
进而
\begin{equation}x\leqslant\sqrt{x}2^{\pi(x)},\end{equation}
这也就是
\begin{equation}\pi(x) \geqslant \frac{\log x}{\log 4},\end{equation}
所以
\begin{equation}\lim_{x\rightarrow\infty}\pi(x)=\infty.\end{equation}
把这个证明稍作修改, 就可以证明: \(\sum\limits_{p\in\Bbb P}\frac 1p\) 发散.
用反证法. 令 \(p_1,p_2,\dotsc\) 表示升序排列的质数. 假定相反的结论成立, 则存在一个 \(k\in\Bbb N^+\), 使得
\[\sum_{i=k+1}^\infty\frac 1{p_i}\leqslant\frac 12.\]
于是, 只要 \(x>0\), 必定
\begin{equation}\sum_{i=k+1}^\infty\frac x{p_i}\leqslant\frac x2.\end{equation}
用 \(N(x)\) 表示 \(<x\) 且其质因子都在\(p_1,p_2,\dotsc,p_k\) 中的那些正整数的个数. 与上个证明同理, 应该有
\begin{equation}N(x)\leqslant\sqrt{x}2^k.\end{equation}
另一方面, \(<x\) 且可被 \(p_l\) 整除的正整数的个数 \(\leqslant\frac x{p_l}(l=k+1,k+2,\dotsc)\), 故而
\[N(x)\geqslant x-\sum_{p=k+1}^\infty\frac xp\geqslant\frac x2,\]
最后的不等式用到了 \((15)\). 结合 \((16)\), 可得
\[\sqrt{x}2^k\geqslant\frac x2\]
对任意 \(x>0\) 成立, 这显然不可能.
下一个证明, 从 matrix67的博客看到:
用反证法. 假定质数有限, 则对于任意正整数 \(n\), 有
\begin{equation}n!=\prod p^{\sum\left[\frac n{p^i}\right]},\end{equation}
这里 \(p\) 取遍所有质数. 注意
\begin{equation}\sum_{i\geqslant1}\left[\frac n{p^i}\right]<\sum_{i\geqslant1}\frac n{p^i}=\frac{n}{p-1}\leqslant n,\end{equation}
所以
\begin{equation}n!<(\prod p)^n.\end{equation}
但是, \(\prod\limits_{p\in\Bbb P}p\) 是一个常数, 当 \(n\) 足够大的时候, \((19)\) 不可能成立. 因之, 质数不可能有限.
接下来的的想法是普林斯顿大学(Applied and Computational Mathematics, Princeton University) 的 Dustin G. Mixon 发现的, 发表在 The American Mathematical Monthly, Vol.119, No.9 (November 2012), pp. 811
假定只有 \(l\) 个质数 \(p_1=2<p_2<\dotsb<p_l\), 选择正整数 \(N\) 使得 \(2^N>(N+1)^l\). 考察映射
\[\sigma:\{1,2,\dotsc,2^N\}\to\{0,1,2,\dotsc,N\}^l\]
\[n\mapsto\Big(\alpha_1,\alpha_2,\dotsc,\alpha_l\Big),\]
这里 \(n=p_1^{\alpha_1}p_2^{\alpha_2}\dotsm p_l^{\alpha_l}\) 是 \(n\) 的质因数分解. 由
\[N\geqslant\log_2n = \sum_{i=1}^l \alpha_i\log_2p_i\geqslant\sum_{i=1}^l\alpha_i\geqslant \max\Big\{\alpha_1,\alpha_2,\dotsc,\alpha_l\Big\},\]
可见 \(\sigma\) 确是到 \(\{0,1,2,\dotsc,N\}^l\) 的映射. 再根据算术基本定理, \(\sigma\) 为单射, 但这显然是不可能的, 因为有抽屉原理(the pigeonhole principle)的存在. \(\Box\)
Suppose there are a total of \(N\) primes, \(2=p_1<p_2<\dotsb<p_N\), and pick \(K\) such that \(2^K>(K+1)^N\). Consider the mapping \(f:\{1,\dotsc,2^K\}\to\{0,\dotsc,K\}^N\) defined by
\[f(x):=(k_1,\dotsc,k_N),\]
where \(x=p_1^{k_1}\dotsm p_N^{k_N}\) is the prime factorization of \(x\). Here, the fact that \(f(x)\in\{0,\dotsc,K\}^N\) follows from
\[K\geqslant\log_2x=\sum_{n=1}^Nk_n\log_2p_n\geqslant\sum_{n=1}^N k_n \geqslant \max\{k_1,\dotsc,k_N\}.\]
Then \(f\) is injective by the fundamental theorem of arithmetic, which contradicts the pigeonhole principle. \(\Box\)
[2012.10.14 收入Dustin G. Mixon 的证明]