和人捉迷藏的质数

58.和人捉迷藏的质数

一个大于1的整数，如果除了它本身和1以外，不能被其他正整数所整除，这个整数就叫做质数。质数也叫素数，如2、3、5、7、11等都是质数。

如何从正整数中把质数挑出来呢？自然数中有多少质数？人们还不清楚，因为它的规律很难寻找。它像一个顽皮的孩子一样，东躲西藏，和数学捉迷藏。

古希腊数学家、亚历山大图书馆馆长埃拉托塞尼提出了一种寻找质数的方法：先写出1到任意一个你所希望达到的数为止的全部自然数。然后把从4开始的所有偶数画掉；再把能被3整除的数（3除外）画掉；接着把能被5整除的数（5除外）画掉……这样一直画下去，最后剩下的数，除1以外全部都是质数。如找1～30之间的质数：

后人把这种寻找质数的方法叫埃拉托塞尼筛法。它可以像从沙子里筛石头那样，把质数选出来，质数表就是根据这个筛选原则编制出来的。

数学家并不满足用筛法去寻找质数，因为用筛法求质数带有一定的盲目性，你不能预先知道要“筛”出什么质数来。数学家渴望找到的是质数的规律，以便更好的掌握质数。

从质数表中可以看到质数分布的大致情况：

1到1000之间有168个质数；

1000到2000之间有135个质数；

2000到3000之间有127个质数；

3000到4000之间有120个质数；

4000到5000之间有119个质数；

随着自然数的变大，质数的分布越来越稀疏。

质数把自己打扮一番，混在自然数里，使人很难从外表看出它有什么特征。比如101、401、601、701都是质数，但是301和901却不是质数。又比如，11是质数，但111、11111以及由11个1、13个1、17个1排列成的数都不是质数，而由19个1、23个1、317个1排列成的数却都是质数。

有人做过这样的验算：

1²＋1＋41＝43，

2²＋2＋41＝47，

3²＋3＋41＝53，

………………

39²＋39＋41＝1601。

从43到1601连续39个这样得到的数都是质数，但是再往下算就不再是质数了。

40²＋40＋41＝1681，1681是一个合数。

被称为“17世纪最伟大的法国数学家”费马，对质数做过长期的研究。他曾提出过一个猜想：当n是非负数时，形如f（n）＝2²ⁿ＋1的数一定是质数。后来，人们把2²ⁿ＋1形式的数叫“费马数”。

费马提出这个猜想当然不是无根据的。他验算了5个费马数：

f（0）＝2²⁰＋1＝2＋1＝3

f（1）＝2²¹＋1＝4＋1＝5

f（2）＝2²²＋1＝16＋1＝17

f（3）＝2²³＋1＝256＋1＝257

f（4）＝2²⁴＋1＝65536＋1＝65537

验算的结果个个都是质数。费马没有再往下验算。为什么没往下算呢？有人猜测再往下算，数字太大了，不好算。但是，就是在第六个费马数上出了问题！费马死后67年，也就是1732年，25岁有瑞士数学家欧拉证明了第六个费数数不再是质数，而是合数。

f（5）＝2²⁵＋1＝2³²＋1＝4294967297＝641×6700417

更有趣的是，从第六个费马数开始，数学家再也没有找到哪个费马数是质数，全都是合数。现在人们找到的最大的费马数是f（1945）＝2²¹⁹⁴⁵＋1，其位数多大10¹⁰⁵⁸⁴位，这可是个超级天文数字。当然尽管它非常之大，但也不是质数。哈哈，质数和费马开了个大玩笑。

在寻找质数方面做出重大贡献的，还有17世纪法国数学家、天主教的神父梅森。梅森于1644年发表了《物理数学随感》，其中提出了著名的“梅森数”。梅森数的形式为2^p－1，梅森整理出11个p值使得2^p－1成为质数。这个11个p值是2、3、5、7、13、17、19、31、67、127和257。你仔细观察这11个数不难发现，它们都是质数。不久，人们证明了：如果梅森数是质数，那么p一定是质数。但是要注意，这个结论的逆命题并不正确，即p是质数，2^p－1不一定是质数。比如2¹¹－1＝2047＝23×89，它是一个合数。

梅森虽然提出了11个p值可以使梅森成为质数，但是，他对11个p值并没有全部进行验算，其中的一个主要原因是数字太大，难以分解。当p＝2、3，5，7，17，19时，相应的梅森数为3、7、31、127、8191、13107、524287。由于这些数比数比较小，人们已经验算出它们都是质数。

1772年，65岁又目失明的数学家欧拉，用高超的心算本领证明了p＝31的梅森数是质数：2³¹＝2147483647。

还剩下p＝67、127、257三个相应的梅森数，它们究竟是不是质数，长时期无人去论证。梅森去世250年后，1903年在纽约举行的数学学术会议上，数学家科勒教授做了一次十分精彩的学术报告。他登上讲台却一言不发，拿起粉笔在黑板上迅速写出：

2⁶⁷－1＝147573952589676412927

＝193707721×761838257287然后就走回自己的座位。开始时会场里鸦雀无声，没有过多久全场响起了经久不息的掌声。参加会议的人纷纷向科勒教授祝贺，祝贺他证明了第九个梅森数不是质数，而是合数！

1914年，第十个梅森数被证明是质数；

1952年，借助电子计算机的帮助证明了第十一个梅森数不是质数。

以后，数学家利用速度不断提高的电子计算机来寻找更大的梅森质数。1996年9月4日，美国威斯康星州克雷研究所的科学家。利用大型电子计算机找到了第三十三个梅森质数，这也是人类迄今为止所认识的最大的质数，它有378632位：2^1257787－1，同时发现了新的完全数：（2^1257787－1）×2^1257786。

数学家尽管可以找到很大的质数，但是质数分布的确切规律仍然是一个谜。古老的质数，它还在和数学家捉迷藏呢！