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

先强烈推荐一本好书。前几天在TopLanguage(http://groups.google.com/group/pongba/browse_thread/thread/752a7af6f2306149#)看到有牛人推荐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，这显然是不可能的。