叶卢庆的博客

素数有无穷个的一个证明

所谓素数,是指只能被$1$和本身整除的大于$1$的正整数.素数有无限个,是一个古老而基本的结论.这个结论最先是被《几何原本》的著者Euclid利用反证法证明的,他的证明是构造性的.其后又涌现众多证明.再者,解析数论本身已经高度发展.因此,如果我在此声称自己的证明是独特的,那会是非常愚蠢的——虽然这个证明真的是我今天早上构思出来的.

我们先叙述思路.还是采用反证法.如果素数只有有限个,那么所有的正整数都是由有限个素数相乘得到的.令$n$为足够大的正整数,估算一下不大于$n$的正整数里由这有限个素数相乘得到的数所占的比例——这个比例在直觉里应该随着$n$趋于无穷而趋于$0$(事实上只用小于$1$就够了),因为有限个素数乘来乘去导致的指数方式的增长太快(相对于幂函数的增长方式),因此由有限个素数相乘而得到的数的分布也应该相应地越来越稀疏.这样我们就在理论上说明了,总存在大量不能由这有限个素数相乘而得到的正整数.这就与假设矛盾.因此素数有无限个.

下面我们来详细地阐述.采用反证法.假设素数只有有限个,不妨将它们从小到大排列为$p_1<p_2<\cdots<p_k$.于是将会有结论:所有的正整数都可以表达成$$p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}$$的形式,其中$\alpha_1,\cdots,\alpha_k$是自然数.我们来估算当
\begin{equation}\label{eq:1}
1\leq p_1^{\alpha_1}p_2^{\alpha_2}\cdots p_k^{\alpha_k}\leq n
\end{equation}
时,$(\alpha_1,\cdots,\alpha_k)$最多不能超过多少组解.将不等式\eqref{eq:1}两边取$\ln$,可得$$\ln 1\leq \alpha_1\ln p_1+\alpha_2\ln p_2+\cdots+\alpha_k\ln p_k\leq n,$$
因此更有
$$
0\leq (\alpha_1+\alpha_2+\cdots+\alpha_k)\ln p_1\leq n.
$$
于是
$$
0\leq \alpha_1+\alpha_2+\cdots+\alpha_k\leq \frac{\ln n}{\ln
p_1}=\frac{\ln n}{\ln 2}<2\ln n.
$$
由组合知识,
$$
0\leq \alpha_{1}+\alpha_{2}+\cdots+\alpha_k\leq [2\ln n]
$$
的所有非负整数解的个数是关于$[2\ln n]$的多项式.于是我们的问题就是:到底是$n$的增长速度大还是关于$\ln n$的多项式的增长速度大?下面我们来证明:
$$
\lim_{n\to\infty}\frac{n}{t(\ln n)^p}=+\infty,
$$
其中$t\in \mathbf{R}^+,p\in \mathbf{N}^+$.而这是最简单的数学分析题目.这样我们就证明了素数有无穷个.