大素數新紀錄

胡作玄

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，換句話說，有七個素因子的奇完美數只有有限多個。這是一項重大突破，但還不足以最后解決第二問題。

(責任編輯蒲暉)