大素数新纪录

胡作玄

2008年8、9月，也就是刀世瞩目的奥运会和残奥会期间，另一个领域也就是数学领域的世界纪录被刷新，美国人和德国人分别发现了当前已知的最大素数——第45个和第46个梅森素数。

让我们来解释一下什么是梅森素数。素数这个概念大家都知道，也就是一个正整数，除了1和它本身之外，没有其他因子的数。现在我们规定1不是素数。因此，最小的素数是2，它是惟一的偶素数，其他的素数均为奇数。这样10以下的素数有4个，它们是：2，3，5，7；100以下的素数有25个。大部分正整数不是素数，我们称为合数，它们总可以分解成为素数的乘积，也说是它们有除1和数本身之外的因子。例如

21=3×7，91＝7×13，

显然，在一定范围之内，合数要比素数多得多，不过，欧几里得早已证明素数有无穷多。

虽然任何素数之后肯定还有素数，可是人们并不知道一个给定的数是不是素数。理论上讲，只要你有足够的时间和精力就可以完成，也就是对于整数Ⅳ，用小于或等于根号N的素数去除它，如果都除不尽，那Ⅳ就是素数。这事看起来容易做起来难。如果Ⅳ不大，如Ⅳ只有10位，也许可以用5位以内的素数一个一个去除，看看是否除得尽。可是如果Ⅳ为100位，就根本办不到了，因为我们还不知道50位以内的素数到底有多少，实际上至今25位以内的素数有哪些，我们也不清楚。

因此，要想摘取最大素数的桂冠，还得另觅他途。找一种特殊形式的素数，这就是梅森素数。梅森是位教士，是科学的组织者，他那时——17世纪上半世纪，没有科学期刊，每个人的工作通过书信传到他那里，然后，他再传给别人，这样大家都可以分享最新的知识。梅森自己也对数学有极大兴趣，他发现：

如果2^p-1是素数，则p一定是素数，因此后来人们就手把2^p-1型的素数，称为梅森素数，常常简记为Mp。但是，这定理反过来是否对呢?也就是：

如果p是素数，2^p-1是否素数?

梅森试了试最小的素数，当p=2，3，5，7时，2^p-1分别等于3，7，31，127，恰巧都是素数，于是他猜想p=13，17，19，31，67，127，257时，2 p—l也是素数。当时，已经知道211-1不是素数，他们费了很大劲把2¹¹-1=2047分解因子成23×89。不过他的上述猜想也包含后来人们在搜寻梅森素数时的两大失误：

1、Mp不是素数，证明这点也很困难。例如梅森猜想中，M67，M257不是素数。前者在梅森之后200多年也就是1876年才证明，后者在1927年才证明。

2、梅森的猜想有遗漏，例如当p=61，89，107时，Mp是梅森素数。发现了一个新的梅森素数之后，是否还有比它小的梅森素数?

这些问题看起来简单，但是找起来极难。因此，到19世纪末，只找到10个梅森素数，最大的是p=127。进入20世纪，才发现在127之前，还有p=89，107时Mp也是梅森素数，这样在1913年前p=127之前的梅森素数才找完全，它们是p=2，3，5，7，13，17，19，31，61，89，107，127。在100以下的素数25个中，只有10个素数形成梅森素数。

人力计算到此为止了。搜寻梅森素数一直到电子计算机出现之后才又开展起来。1952年利用计算机得出5个新的梅森素数。其后就要靠当时最快的计算机了，值得一提的是，1978年美国两位18岁中学生(一男一女)发现了第25个，第二年升入大学的男生发现第26个，这两个M p，p首次超过20000。1979年到1995年，斯洛温斯基利用巨型计算机得出另外7个梅森素数，他遗漏的一个在1988年由别人找到。

在大型计算面前，巨型计算机还是难以招架。1995年网络的普及，进一步推动梅森素数的探索。这年，沃尔特曼建立一个GIMPS的计划，使得搜索进度大大加快。从1996年到2000年发现了从35到38四个Mp，从2001年到2006年发现从39到44个Mp。

2008年8月23日及9月6日，美国和德国两个小组分别发现了两个新的梅森素数：

2^43112609-1及2^37156667-1

前者超过1200万位，后者超过1100万位，而以前的44个梅森素数都没有超过1000万位。当然，它们也是现在所知的最大素数。在参加素数奥运的选手中，许多打破纪录的是业余爱好者，从20岁的大学生到眼科医生!

既然找到一个梅森素数如此困难，人们为什么又乐此不疲呢?我看，它至少有三个方面的重要意义。

1、计算方面。梅森素数的搜索要求对计算机及计算方法进行不断改进。

2、应用方面。大素数有许多用处，特别是密码学。如果你能很快地进行素数判定和因子分解，则对密码设计是一个重要贡献。如果一个密码是由两个大素数相乘得到，那就在短时间内很难破译，从而保证了信息系统的安全。

3、理论方面。梅森素数来源于一个千古未解的数学难题——完美数(也称完全数)问题。完美数这个概念来自毕达哥拉斯，它的原义是指十全十美的数。它的定义是一个自然数Ⅳ，它等于其真因子(即除自身之外的因子)之和，换句话说，如果N的所有因子之和记作σ(N)，则σ(N)=2N。表面上看这个条件不是太苛刻，实际上大多数自然数并不满足这个条件。我们不妨看看下面的例子：6的因子有1，2，3，6，因此，σ(6)=1+2+3+6—12=2×6，

所以6是个完美数。可是14的因子有1，2，7，14，因此，

σ(14)=1+2+7+14—2.4<2×14

而口(24)=1+2+3+4+6+8+12+24=60>2×24

可见14和24都不是完美数。6是第一个完美数，第二个完美数是28，因为

σ(28)=1+2+4+7+14+28=56＝2×28。

后来到公元1世纪才发现在100与1000之间，1000与10000之间各有一个完美数，它们是496和8128。这4个就是古代所知的所有完美数。虽然，古代知道的完美数很少，可是，欧几里得在《几何原本》中证明一个一般的定理，它给出(偶)完美数的必要条件：

如2^{n-1是素数，则2n-1(2n-1)是完美数。到17世纪，伟大的哲学家、数学家笛卡尔对}

这种数也十分有兴趣，他感慨地说：“找到完美的数也跟找到完美的人一样困难。”他说得不错。他对完美的贡献在于他声称，欧几里得的必要条件也是充分条件：

如果一个偶数是完美数，则它具有2^n-1(2ⁿ-1)的形式，其中2ⁿ-1是素数。

这样一来，找出偶完美数的问题，就归结为找2^{n-1型的素数问题。笛卡尔的同时代人梅森发现，如果2n-1为素数，则月必定为素数，因此，后来把这种素数称为梅森素数。正因为如此，找偶完全数的问题归结为找梅森素数的问题。这就是我们在前面所讲的。}

虽说偶完美数问题归结为找梅森素数，但是从理论上我们还有两大难题，它们是至今数学上未解决的最古老的难题：

1、偶完美数是否有无穷多个，也就是梅森素数是否有无穷多个?

虽然我们至今才找到46个，我们很难断定偶完美数是有限还是无穷多个。不过一般认为它有无穷多，但找到一个证明决非易事。说到现在，我们只是考虑完美数问题的一半——偶完美数，但是，奇数有没有可能是完美数呢?经过长年搜索，至今没有找到一个奇完美数。因此，一般人倾向认为奇完美数不存在。

2、奇完美数是否存在?

这个问题比前一个问题更容易下手，因此，有不少人研究，有些甚至是学位论文。由于一般猜想奇完美数不存在，我们就要找一些必要条件，使得一个数很难满足。这种必要条件很多，而且逐年进步，下面也包括一些到2008年底的纪录：

(1)奇完美数要是存在，一定非常之大：1980年已知如果Ⅳ是奇完美数，则N>10¹⁰⁰，也就是至少100位，1989年已知N>10200，1990年改进到N>10³⁰⁰，现在仍在改进之中。

(2)奇完美数的素因子的数目。

奇完美数显然是合数，可分解为多个素因子之积。人们发现，素因子的数目很多，1982年证明大于或等于23个，2005年改进为47个，2007年证明超过75个。

(3)奇完美数最大素因子。

奇完美数的许多素因子当中肯定有最大的，现在证明最大素因子也是相当大，2008年的最新结果说它超过10^{8。不仅如此，次大的素因子和三大的素因子也非常之大，这也从另一方面证明，如果奇完美数存在，那么是它是极大的数。}

(4)奇完美数的上界。1994年，英国数学家希斯布朗证明：如果奇完美数Ⅳ有七个素因子，则N<4^4z，换句话说，有七个素因子的奇完美数只有有限多个。这是一项重大突破，但还不足以最后解决第二问题。

(责任编辑蒲晖)