经典证明:质数无穷多与两个更强的命题

    又回来更新啦!虽然还有两门课没考,但今天已经轻松了不少。梦魇般的现代文学史总算是结束了。抱了两天两夜的佛脚,结果考试时一看卷子,仍然没一道会的题目。不定项选择多选少选均不得分,都是些文学常识题,给四篇我从没见过的小说名字问哪些是第一人称叙事,或者给四个人名字问哪些是笔名之类的。天哪……以后的古代文学史咋办啊。
    先强烈推荐一本好书。前几天在TopLanguage看到有牛人推荐Proofs from THE BOOK这本书,当即决定买了下来。这几天复习累了我都在看这本书,真的是很好很强大,里面汇集了很多著名问题的经典证明,包括很多我一直想找但没找到的证明。好了不多废话了,下面进入正题。

    很早以前,我们曾经研究过质数,证明了质数有无穷多个。后来,我们又学到了另外两种证明质数无穷多的方法。这两种方法的基本思路相同:寻找一个无穷大的集合,里面的数两两互质。只用有限个质数明显不能得到无穷多个两两互质的数,于是我们立即可知质数必然有无穷多个。今天,我们将证明两个比质数无穷多更强的定理。这两个证明都出自Proofs from THE BOOK的第一章。

    定义函数π(x)为“小于等于x的质数有多少个”。无妨规定x为一个正整数。我们将用初等微积分方法证明当x趋于无穷时π(x)也趋于无穷并给出π(x)的一个下界。我们将说明,对于所有x,π(x)>=log(x)-1,即x以内的质数至少有log(x)-1个。
    为了说明这一点,让我们考虑所有不超过x的质数的倒数的等比级数(1 + 1/p + 1/p^2 + ..)的乘积,即
    回忆等比级数的公式,则我们有:

  

    第二行的一些变换非常巧妙。第二行中间的不等号是一个关键,用到了一个基本事实:第k个质数显然比k大。最后的连乘中前一项的分子和后一项的分母正好抵消,最后消完了就只剩了一个π(x)+1。
    另一方面,想像一下把(1+1/2+1/4+…)(1+1/3+1/9+…)(1+1/5+1/25+…)…展开的样子,很显然展开后的每一项都是一个所有质因子都不大于x的数的倒数,即Σ(1/m),其中m取所有仅含1..x范围内的质因子的数。显然,原本就比x小的数,其质因子当然不可能超过x,这就是说从1到x的所有正整数都是属于m的。利用一些微积分的基本知识,我们可以立即得出Σ(1/m) >= 1+1/2+1/3+…+1/x >= log(x)。地球人都知道,log(x)是没有上界的,于是质数的个数也没有上界。
    这里还有一个类似的问题,大家可以对照着看看。


    Proofs from THE BOOK中还提到了另一个更绝的定理及其证明。下面我们将说明,质数不但有无穷多个,而且它们的倒数和发散。我们将用反证法,先假设收敛,然后你将看到这会推出一个多么荒谬的结论。
    假设收敛,则一定存在某个k,使得。这个k就把整个质数序列分成了两半:p_1,p_2,…,p_k属于前面一半(称作小质数);剩下的项都属于后面一半(称作大质数),它们的和不超过1/2。对于任意大的自然数N,总成立。下面我们把不大于N的正整数分成两类:令N_b表示在1..N里面,至少能被一个大质数整除的数的个数;再令N_s表示1..N里面有多少个数的质因子全是小质数。下面我们将计算N_b和N_s的上界,并且将找出一个N满足这样一个可笑的不等式:N_b + N_s < N。     借助前面的结论,我们能很快给出N_b的一个很不错的上界。注意到N/p_i实际上表示1..N中有多少个数是p_i的倍数,于是显然有
    下面我们集中力量计算N_s。我们把所有不超过N的且质因子都是小质数的正整数写成A*B^2 = p_a1 · p_a2 ·…· p_an · (p_b1 · p_b2 ·…· p_bm)^2的形式,其中前面部分是互不相同的质数的乘积,共有2^k种可能的组合;后面部分是能配成对的质因子,它们的乘积不可能超过sqrt(N),因此B的取值只能是从1到sqrt(N)的整数。根据乘法原理,N_s不可能超过2^k * sqrt(N)。由于我们的N是任意取的,当N足够大时必然会出现2^k * sqrt(N) < N/2的情况,但N_b也小于N/2,这显然是不可能的。

13 条评论

发表评论