[欧拉数学]素数有无穷多个的两个证明
By 苏剑林 | 2011-10-02 | 68996位读者 |素数是数的基本单元,就如同高楼大厦中的砖块一样。显然,素数有无穷多个是数论研究价值的前提。不然,数的研究就局限在有限个素数之内,那么很多数字就会失去了它们的魅力。就好比只有有限块砖头,就不能创建出建筑的奇迹一般。下面介绍两个关于素数无穷的经典证明,其中一个是欧几里得的证明,这是最原始、最简单的证法,相信很多读者已经学习过了,在此还是要提一下;另外一个是我在《怎样解题》中看到的,原作者是欧拉,也是一个非常美妙的证明。当然,本文强调的思想,论证过程可能会有一些不严谨的地方,请读者完善^_^
一、欧几里得证明
这个证明思想非常简单:若干个素数的积加上1后会产生新的素数因子。要是素数只有n个,那么我们就把它们相乘,然后加上1,得到的将会是什么呢?如果是一个素数,那么将会与素数只有n个矛盾;如果是一个合数,它除以原来的n个素数都不是整数,那么它就会拥有新的素数因子了,这还是和只有n个素数矛盾。不论哪种情况,只有素数有限,就会得出矛盾,于是素数必然是无限的。
二、欧拉经典
这个证明需要做一些准备工作。它的思想是:等比数列+生成函数。
首先,我们有公式$S(p)=1+p^{-1}+p^{-2}+...+p^{-n}=\frac{1-p^{-n-1}}{1-p^{-1}}$,这是等比数列的求和公式,当$|p| > 1,n\to \infty$时,$p^{-n-1} \to 0$我们有:
$$S(p)=\sum_{n=0}^{\infty} p^{-n}=\frac{1}{1-p^{-1}}=\frac{p}{p-1}$$
下面我们尝试将p遍取所有的素数,即2,3,5,7,...,并将各S(p)相乘,得到(记为K):
$$\begin{aligned}K=S(2)\cdot S(3)\cdot S(5)... \\ =(1+\frac{1}{2}+\frac{1}{2^2}+\frac{1}{2^3}...)(1+\frac{1}{3}+\frac{1}{3^2}+\frac{1}{3^3}...)(1+\frac{1}{5}+\frac{1}{5^2}+\frac{1}{5^3}...)... \\ =\frac{2}{2-1}\cdot \frac{3}{3-1}\cdot \frac{5}{5-1}\cdot ...\end{aligned}$$
K有什么特别的地方呢?注意到这里各素数的幂都相互乘了一次,这和自然数的产生是一样的:把若干个素数的幂相乘,就可以得到任意自然数。于是我们就可以(并非毫无根据地)写出:
$$K=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+...$$
根据我们知道级数$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+...$是发散的,所以素数不可能只有有限个,因为$K=\frac{2}{2-1}*\frac{3}{3-1}*\frac{5}{5-1}*...$,要是素数只有有限个的话,那么这个乘积必然也是有限的,这会导致矛盾。所以素数无限。
三、和素数定理的一丝联系
素数定理告诉我们,不大于n的素数的个数$\pi(n)$约等于$\frac{n}{ln n}$。
而由上面的讨论我们得到:
$$K=\frac{2}{2-1}\cdot \frac{3}{3-1}\cdot \frac{5}{5-1}\cdot ...=1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+...$$
而由微积分可以证明,第二个等号右边的部分,即$1+\frac{1}{2}+\frac{1}{3}+\frac{1}{4}+\frac{1}{5}+...+\frac{1}{n}$可以近似表示为$ ln n$,那么把式子倒过来,就可以得到:
$$\frac{2-1}{2}\cdot \frac{3-1}{3}\cdot \frac{5-1}{5}\cdot ...\approx \frac{1}{ln n}$$
而对于n很大时,不大于n的偶数显然约等于$n/2$,剩下的$n/2$个奇数中,3的倍数约等于$1/3$,所以非3倍数约等于$n*1/2*2/3$,剩下的数字中,非5倍数显然会约等于$n*1/2*2/3*4/5$,依此类推,得到
$$\pi(n) \approx n\cdot 1/2\cdot 2/3\cdot 4/5\cdot 6/7\cdot ... \approx \frac{n}{ln n}$$
当然,这个压根儿就不算什么证明,顶多是一个勉强而幸运地成功的推理。不过虽然经不起严格的逻辑的考验,但作为一个初等的思考的欣赏,也是相当有趣的^_^
转载到请包括本文地址:https://spaces.ac.cn/archives/1484
更详细的转载事宜请参考:《科学空间FAQ》
如果您还有什么疑惑或建议,欢迎在下方评论区继续讨论。
如果您觉得本文还不错,欢迎分享/打赏本文。打赏并非要从中获得收益,而是希望知道科学空间获得了多少读者的真心关注。当然,如果你无视它,也不会影响你的阅读。再次表示欢迎和感谢!
如果您需要引用本文,请参考:
苏剑林. (Oct. 02, 2011). 《[欧拉数学]素数有无穷多个的两个证明 》[Blog post]. Retrieved from https://spaces.ac.cn/archives/1484
@online{kexuefm-1484,
title={[欧拉数学]素数有无穷多个的两个证明},
author={苏剑林},
year={2011},
month={Oct},
url={\url{https://spaces.ac.cn/archives/1484}},
}
October 20th, 2011
xian you ji hai shi you dan
October 25th, 2011
还是欧几里得的证明来得妙
October 31st, 2011
欧几里得的证明很简洁(这个证明我以前也自己想出来过,还有一个问题是像这样前n个素数的积+1格式的数究竟是素数多还是合数多,我猜可能还是合数多很多,不过需要写个程序验证一下),但欧拉的方法仔细一看也是很巧妙——而且重要的是,欧拉还用类似的思路证明了所有素数的倒数和是发散的——他用的是黎曼zeta函数——此函数又引出了著名的未解数学问题黎曼猜想(我还在wiki上看关于黎曼zeta函数的内容,所以藏拙,不多说了)
我们也可以很简单(但不严谨)地证明一下所有素数倒数之和发散。过一阵子我会写写。
黎曼猜想,的确是当代数论的核心问题之一,令人惊奇的是,它的应用,却不仅仅是数论这一纯粹的数学领域,它甚至涉及到了量子混沌...
October 31st, 2011
将黎曼zeta函数的wiki词条看完了——幸亏藏拙了,否则就糗大了。其实调和级数(所有自然数的倒数和,就是帖子里的K)就是该函数在1时的情形。欧拉证明所有素数的倒数和是发散的思路就是将K的那个素数表达式两边取自然对数,然后用级数展开,再作一些不等式的变换做出来的。
August 3rd, 2015
interesting
呵呵(凑中文)
February 26th, 2016
欧拉质数无限证明通过你的写法已经无法说明质数无限的问题了。。。虽然结果一样,但是过程没有了对质数舍去的讨论,让人看了一头雾水。
August 27th, 2018
我感觉楼主写第二个证明有循环论证的感觉(不知道欧拉原证明是什么样子),首先假设了K是由素数按照S(p)相乘,这时候式子里面已经假设了p有无数多个,否则调和级数发散无从谈起。然后又用调和级数的发散性去说p有无数多个,这本身应该有问题。
不能这样子理解。
所为素数的集合,可以理解为所有自然数的不可分因子的集合,也就是通过“素数集合”里边的元素相乘或者自乘,就可以得到所有自然数。我们也不知道这个集合是有限还是无限,但我们知道这个集合能生成所有的自然数。
然后,$K$是$S(p)$遍历所有素数相乘,这个连乘并没有假设$p$的个数,它可能是有限的,也可以是无限的。但我们知道,这个乘积展开后的结果,就是调和级数的形式,这是因为前面对素数集合的理解了:由素数集能够生成所有的自然数。
October 9th, 2021
欧几里得证明了素数有无限多个,但并不代表前n个素数之积再加1,得到的结果就一定是素数。这是两回事,因为可能被其他素数整除。