第一个证明是哥德巴赫(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 的证明]