大素?cái)?shù)新紀(jì)錄

胡作玄

2008年8、9月，也就是刀世矚目的奧運(yùn)會(huì)和殘奧會(huì)期間，另一個(gè)領(lǐng)域也就是數(shù)學(xué)領(lǐng)域的世界紀(jì)錄被刷新，美國(guó)人和德國(guó)人分別發(fā)現(xiàn)了當(dāng)前已知的最大素?cái)?shù)——第45個(gè)和第46個(gè)梅森素?cái)?shù)。

讓我們來(lái)解釋一下什么是梅森素?cái)?shù)。素?cái)?shù)這個(gè)概念大家都知道，也就是一個(gè)正整數(shù)，除了1和它本身之外，沒(méi)有其他因子的數(shù)?，F(xiàn)在我們規(guī)定1不是素?cái)?shù)。因此，最小的素?cái)?shù)是2，它是惟一的偶素?cái)?shù)，其他的素?cái)?shù)均為奇數(shù)。這樣10以下的素?cái)?shù)有4個(gè)，它們是：2，3，5，7；100以下的素?cái)?shù)有25個(gè)。大部分正整數(shù)不是素?cái)?shù)，我們稱(chēng)為合數(shù)，它們總可以分解成為素?cái)?shù)的乘積，也說(shuō)是它們有除1和數(shù)本身之外的因子。例如

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

顯然，在一定范圍之內(nèi)，合數(shù)要比素?cái)?shù)多得多，不過(guò)，歐幾里得早已證明素?cái)?shù)有無(wú)窮多。

雖然任何素?cái)?shù)之后肯定還有素?cái)?shù)，可是人們并不知道一個(gè)給定的數(shù)是不是素?cái)?shù)。理論上講，只要你有足夠的時(shí)間和精力就可以完成，也就是對(duì)于整數(shù)Ⅳ，用小于或等于根號(hào)N的素?cái)?shù)去除它，如果都除不盡，那Ⅳ就是素?cái)?shù)。這事看起來(lái)容易做起來(lái)難。如果Ⅳ不大，如Ⅳ只有10位，也許可以用5位以?xún)?nèi)的素?cái)?shù)一個(gè)一個(gè)去除，看看是否除得盡?？墒侨绻魹?00位，就根本辦不到了，因?yàn)槲覀冞€不知道50位以?xún)?nèi)的素?cái)?shù)到底有多少，實(shí)際上至今25位以?xún)?nèi)的素?cái)?shù)有哪些，我們也不清楚。

因此，要想摘取最大素?cái)?shù)的桂冠，還得另覓他途。找一種特殊形式的素?cái)?shù)，這就是梅森素?cái)?shù)。梅森是位教士，是科學(xué)的組織者，他那時(shí)——17世紀(jì)上半世紀(jì)，沒(méi)有科學(xué)期刊，每個(gè)人的工作通過(guò)書(shū)信傳到他那里，然后，他再傳給別人，這樣大家都可以分享最新的知識(shí)。梅森自己也對(duì)數(shù)學(xué)有極大興趣，他發(fā)現(xiàn)：

如果2^p-1是素?cái)?shù)，則p一定是素?cái)?shù)，因此后來(lái)人們就手把2^p-1型的素?cái)?shù)，稱(chēng)為梅森素?cái)?shù)，常常簡(jiǎn)記為Mp。但是，這定理反過(guò)來(lái)是否對(duì)呢?也就是：

如果p是素?cái)?shù)，2^p-1是否素?cái)?shù)?

梅森試了試最小的素?cái)?shù)，當(dāng)p=2，3，5，7時(shí)，2^p-1分別等于3，7，31，127，恰巧都是素?cái)?shù)，于是他猜想p=13，17，19，31，67，127，257時(shí)，2 p—l也是素?cái)?shù)。當(dāng)時(shí)，已經(jīng)知道211-1不是素?cái)?shù)，他們費(fèi)了很大勁把2¹¹-1=2047分解因子成23×89。不過(guò)他的上述猜想也包含后來(lái)人們?cè)谒褜っ飞財(cái)?shù)時(shí)的兩大失誤：

1、Mp不是素?cái)?shù)，證明這點(diǎn)也很困難。例如梅森猜想中，M67，M257不是素?cái)?shù)。前者在梅森之后200多年也就是1876年才證明，后者在1927年才證明。

2、梅森的猜想有遺漏，例如當(dāng)p=61，89，107時(shí)，Mp是梅森素?cái)?shù)。發(fā)現(xiàn)了一個(gè)新的梅森素?cái)?shù)之后，是否還有比它小的梅森素?cái)?shù)?

這些問(wèn)題看起來(lái)簡(jiǎn)單，但是找起來(lái)極難。因此，到19世紀(jì)末，只找到10個(gè)梅森素?cái)?shù)，最大的是p=127。進(jìn)入20世紀(jì)，才發(fā)現(xiàn)在127之前，還有p=89，107時(shí)Mp也是梅森素?cái)?shù)，這樣在1913年前p=127之前的梅森素?cái)?shù)才找完全，它們是p=2，3，5，7，13，17，19，31，61，89，107，127。在100以下的素?cái)?shù)25個(gè)中，只有10個(gè)素?cái)?shù)形成梅森素?cái)?shù)。

人力計(jì)算到此為止了。搜尋梅森素?cái)?shù)一直到電子計(jì)算機(jī)出現(xiàn)之后才又開(kāi)展起來(lái)。1952年利用計(jì)算機(jī)得出5個(gè)新的梅森素?cái)?shù)。其后就要靠當(dāng)時(shí)最快的計(jì)算機(jī)了，值得一提的是，1978年美國(guó)兩位18歲中學(xué)生(一男一女)發(fā)現(xiàn)了第25個(gè)，第二年升入大學(xué)的男生發(fā)現(xiàn)第26個(gè)，這兩個(gè)M p，p首次超過(guò)20000。1979年到1995年，斯洛溫斯基利用巨型計(jì)算機(jī)得出另外7個(gè)梅森素?cái)?shù)，他遺漏的一個(gè)在1988年由別人找到。

在大型計(jì)算面前，巨型計(jì)算機(jī)還是難以招架。1995年網(wǎng)絡(luò)的普及，進(jìn)一步推動(dòng)梅森素?cái)?shù)的探索。這年，沃爾特曼建立一個(gè)GIMPS的計(jì)劃，使得搜索進(jìn)度大大加快。從1996年到2000年發(fā)現(xiàn)了從35到38四個(gè)Mp，從2001年到2006年發(fā)現(xiàn)從39到44個(gè)Mp。

2008年8月23日及9月6日，美國(guó)和德國(guó)兩個(gè)小組分別發(fā)現(xiàn)了兩個(gè)新的梅森素?cái)?shù)：

2^43112609-1及2^37156667-1

前者超過(guò)1200萬(wàn)位，后者超過(guò)1100萬(wàn)位，而以前的44個(gè)梅森素?cái)?shù)都沒(méi)有超過(guò)1000萬(wàn)位。當(dāng)然，它們也是現(xiàn)在所知的最大素?cái)?shù)。在參加素?cái)?shù)奧運(yùn)的選手中，許多打破紀(jì)錄的是業(yè)余愛(ài)好者，從20歲的大學(xué)生到眼科醫(yī)生!

既然找到一個(gè)梅森素?cái)?shù)如此困難，人們?yōu)槭裁从謽?lè)此不疲呢?我看，它至少有三個(gè)方面的重要意義。

1、計(jì)算方面。梅森素?cái)?shù)的搜索要求對(duì)計(jì)算機(jī)及計(jì)算方法進(jìn)行不斷改進(jìn)。

2、應(yīng)用方面。大素?cái)?shù)有許多用處，特別是密碼學(xué)。如果你能很快地進(jìn)行素?cái)?shù)判定和因子分解，則對(duì)密碼設(shè)計(jì)是一個(gè)重要貢獻(xiàn)。如果一個(gè)密碼是由兩個(gè)大素?cái)?shù)相乘得到，那就在短時(shí)間內(nèi)很難破譯，從而保證了信息系統(tǒng)的安全。

3、理論方面。梅森素?cái)?shù)來(lái)源于一個(gè)千古未解的數(shù)學(xué)難題——完美數(shù)(也稱(chēng)完全數(shù))問(wèn)題。完美數(shù)這個(gè)概念來(lái)自畢達(dá)哥拉斯，它的原義是指十全十美的數(shù)。它的定義是一個(gè)自然數(shù)Ⅳ，它等于其真因子(即除自身之外的因子)之和，換句話說(shuō)，如果N的所有因子之和記作σ(N)，則σ(N)=2N。表面上看這個(gè)條件不是太苛刻，實(shí)際上大多數(shù)自然數(shù)并不滿(mǎn)足這個(gè)條件。我們不妨看看下面的例子：6的因子有1，2，3，6，因此，σ(6)=1+2+3+6—12=2×6，

所以6是個(gè)完美數(shù)?？墒?4的因子有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

可見(jiàn)14和24都不是完美數(shù)。6是第一個(gè)完美數(shù)，第二個(gè)完美數(shù)是28，因?yàn)?/p>

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

后來(lái)到公元1世紀(jì)才發(fā)現(xiàn)在100與1000之間，1000與10000之間各有一個(gè)完美數(shù)，它們是496和8128。這4個(gè)就是古代所知的所有完美數(shù)。雖然，古代知道的完美數(shù)很少，可是，歐幾里得在《幾何原本》中證明一個(gè)一般的定理，它給出(偶)完美數(shù)的必要條件：

如2^{n-1是素?cái)?shù)，則2n-1(2n-1)是完美數(shù)。到17世紀(jì)，偉大的哲學(xué)家、數(shù)學(xué)家笛卡爾對(duì)}

這種數(shù)也十分有興趣，他感慨地說(shuō)：“找到完美的數(shù)也跟找到完美的人一樣困難?！彼f(shuō)得不錯(cuò)。他對(duì)完美的貢獻(xiàn)在于他聲稱(chēng)，歐幾里得的必要條件也是充分條件：

如果一個(gè)偶數(shù)是完美數(shù)，則它具有2^n-1(2ⁿ-1)的形式，其中2ⁿ-1是素?cái)?shù)。

這樣一來(lái)，找出偶完美數(shù)的問(wèn)題，就歸結(jié)為找2^{n-1型的素?cái)?shù)問(wèn)題。笛卡爾的同時(shí)代人梅森發(fā)現(xiàn)，如果2n-1為素?cái)?shù)，則月必定為素?cái)?shù)，因此，后來(lái)把這種素?cái)?shù)稱(chēng)為梅森素?cái)?shù)。正因?yàn)槿绱?，找偶完全?shù)的問(wèn)題歸結(jié)為找梅森素?cái)?shù)的問(wèn)題。這就是我們?cè)谇懊嫠v的。}

雖說(shuō)偶完美數(shù)問(wèn)題歸結(jié)為找梅森素?cái)?shù)，但是從理論上我們還有兩大難題，它們是至今數(shù)學(xué)上未解決的最古老的難題：

1、偶完美數(shù)是否有無(wú)窮多個(gè)，也就是梅森素?cái)?shù)是否有無(wú)窮多個(gè)?

雖然我們至今才找到46個(gè)，我們很難斷定偶完美數(shù)是有限還是無(wú)窮多個(gè)。不過(guò)一般認(rèn)為它有無(wú)窮多，但找到一個(gè)證明決非易事。說(shuō)到現(xiàn)在，我們只是考慮完美數(shù)問(wèn)題的一半——偶完美數(shù)，但是，奇數(shù)有沒(méi)有可能是完美數(shù)呢?經(jīng)過(guò)長(zhǎng)年搜索，至今沒(méi)有找到一個(gè)奇完美數(shù)。因此，一般人傾向認(rèn)為奇完美數(shù)不存在。

2、奇完美數(shù)是否存在?

這個(gè)問(wèn)題比前一個(gè)問(wèn)題更容易下手，因此，有不少人研究，有些甚至是學(xué)位論文。由于一般猜想奇完美數(shù)不存在，我們就要找一些必要條件，使得一個(gè)數(shù)很難滿(mǎn)足。這種必要條件很多，而且逐年進(jìn)步，下面也包括一些到2008年底的紀(jì)錄：

(1)奇完美數(shù)要是存在，一定非常之大：1980年已知如果Ⅳ是奇完美數(shù)，則N>10¹⁰⁰，也就是至少100位，1989年已知N>10200，1990年改進(jìn)到N>10³⁰⁰，現(xiàn)在仍在改進(jìn)之中。

(2)奇完美數(shù)的素因子的數(shù)目。

奇完美數(shù)顯然是合數(shù)，可分解為多個(gè)素因子之積。人們發(fā)現(xiàn)，素因子的數(shù)目很多，1982年證明大于或等于23個(gè)，2005年改進(jìn)為47個(gè)，2007年證明超過(guò)75個(gè)。

(3)奇完美數(shù)最大素因子。

奇完美數(shù)的許多素因子當(dāng)中肯定有最大的，現(xiàn)在證明最大素因子也是相當(dāng)大，2008年的最新結(jié)果說(shuō)它超過(guò)10^{8。不僅如此，次大的素因子和三大的素因子也非常之大，這也從另一方面證明，如果奇完美數(shù)存在，那么是它是極大的數(shù)。}

(4)奇完美數(shù)的上界。1994年，英國(guó)數(shù)學(xué)家希斯布朗證明：如果奇完美數(shù)Ⅳ有七個(gè)素因子，則N<4^4z，換句話說(shuō)，有七個(gè)素因子的奇完美數(shù)只有有限多個(gè)。這是一項(xiàng)重大突破，但還不足以最后解決第二問(wèn)題。

(責(zé)任編輯蒲暉)