梅森素數：千年不休的探尋之旅

還記得年少時的夢嗎？

還記得你小學時背誦的素數表嗎？那時候它還叫做質數表「2、3、5、7......」如今你是否已經真正理解了老師說過的話：這些只能被1和本身整除的數，具有著無窮的魅力。

還記得你中學時計算的2的整數冪嗎？計算機時代，作為二進位的體現，它們正大行其道。「2、4、8、16、32、64、128、256......」十多年來，個人計算機內存的容量正是經歷了這些熟悉的數字，直到現在的2048M（2G）以及更多。

現在，讓我們從這些2的整數冪中挑出以素數為指數的，再把它減1，試試看會發現什麼？2^2－1＝3、2^3－1＝7、2^5－1＝31、2^7－1＝127......

嗯，你的心是不是激動起來了？一個偉大的發現似乎就在眼前......

別急別急，你的發現很妙，只是有些兒惋惜......你已經遲到了二千年。

在2300多年前，古希臘的數學家，那位寫出不朽的《幾何原本》的歐幾里得在證明了素數有無窮多個之後，就順便指出：有許多素數可以寫成2P－1的形式，其中指數P也是素數。很容易想到，剛才你所發現的2^2－1、2^3－1、2^5－1、2^7－1正是其中排列最前的4個！

當P＝11、13、17、19、23......的時候，2P－1還是素數嗎？到底有多少這種2P－1型的素數呢？在計算能力低下的公元前，這個關於素數的探尋之旅就已經吸引了無數的人。

人們唯獨對素數如此著迷不是沒有理由的，它有著許多簡單而又美麗的猜想，有的已經成為定理，而有的則至今還沒有答案。例如著名的哥德巴赫猜想，讓人們苦苦追索：是否任何一個大於或等於6的偶數，都可以表示為兩個奇素數的和？再比如孿生素數問題所提出的：象5和7、41和43這樣相差2的素數，到底有多少對呢？

在數學史上起個大早的古希臘人還有許多關於素數的發現，完美數就是其中之一。畢達哥拉斯學派指出，如果一個數的所有因數（包括1但不包括它本身）的和正好等於它本身，則這個數就叫做完美數。很容易找到，6＝1＋2＋3是第一個完美數，28＝1＋2＋4＋7＋14則是第二個完美數。他們認為，上帝用6天創造了世界，因此6是最理想和完美的數字，而和6具有相同性質的數都堪稱完美數。

歐幾里得在《幾何原本》中證明了如果2^P－1是一個素數，那麼2^P－1（2^P－1）一定是一個完美數（你會發現，當P分別等於2、3時，它就對應著前兩個完美數6、28）。

再後來，歐拉進一步證明，每一個偶完美數也必定是歐幾里得所給出的形式。（不要問我奇完美數呢？就連它是否存在，本身也是無數個關於素數的難題中至今未解的一個。）

很容易看到，找到了2^P－1形式的素數，也就發現了新的完美數。

形如2^P－1的素數還長期佔據了人們尋找到的最大素數的光榮榜（僅在1989年後被39158×2^216193－1奪走三年），因為判斷這樣一個數是素數的方法比判斷一個差不多大小的其他類型數是素數的方法要簡單得多。

對2^P－1型素數的搜尋之旅就這樣出發了，先後投入這個漫漫長途的就有數學大師費馬、笛卡爾、萊布尼茲、哥德巴赫、歐拉、高斯、哈代、圖靈......這一個個閃光的名字正如暗夜前行的火炬手，照亮了人類通往未知的道路。

歷史的天空閃爍幾顆星

讓我們將坐上時間機器，回到過去，重新瀏覽這來路風光吧。

1456年，又一個沒有留下姓名的人發現了第5個2^P－1型的素數：2^13－1。若是你就降生在那個年代，或許這次發現的光榮將歸屬於你。只是，你更有可能犯下和當時的人們一樣的錯誤，以為對於所有的素數P，2^P－1都是素數。要知道，這個錯誤是近百年之後，直到1536年，才由雷吉烏斯(Hudalricus Regius)打破的。他指出，2^11-1＝2047＝23×89，不是素數。

不過你的莽撞完全可以得到諒解，在黑暗中尋找的數學家正如年輕人一樣，犯下的錯誤連上帝都會原諒。第一個對這種類型的素數進行整理的皮特羅?卡達迪(Pietro Cataldi)在他在1603年宣布的結果中就言之鑿鑿地說：對於p=17，19，23，29，31和37，2P－1是素數。只可惜，37年後，他的六個結果就被推翻了兩個，費爾馬使用著名的小費爾馬（不是那個更著名的大費爾馬定理）證明了卡達迪關於P＝23和37的結論是錯誤的。

不知道下面的事實會不會讓你聯想到「屋漏偏逢連夜雨」呢？大約一百年後，1738年，歐拉證明了卡達迪的結果中P＝29也是錯誤的。幸好，歐拉又證明了P＝31的結論是對的。

雖然，卡達迪的六個結果「陣亡」了一半，但考慮到他是用手工計算取得結論的，而費爾馬和歐拉則是使用了在他們那時最先進的數學知識，避免了許多複雜的計算和因此可能造成的錯誤，因此我們仍然要對卡達迪致敬。他也由此光榮地佔據了第六個和第七個的發現者之位，在他之前的，都是無名氏。

卡達迪的成功，說明了整理和預測是正確道路。繼他之後，集研究成果大成的，是17世紀法國著名的數學家和修道士馬林?梅森（Marin Mersenne,1588-1648）。

梅森熱心於宗教，但更喜愛數學；他是一個交往廣泛、熱情誠摯的人，更是一座「科學信息交換站」。為什麼呢？那時候，學術刊物、國際會議甚至科研機構都還沒有誕生。「及時雨」般的梅森是歐洲眾多科學家之間聯繫的橋樑，大家把研究成果寄給他，然後再由他轉告給更多的人。費馬、笛卡爾等數學家每周在他家聚會，討論問題，就這樣慢慢形成的"梅森學院"，後來有了一個更響亮的名字——法蘭西科學院。

1644年，梅森在歐幾里得、費馬等人的有關研究的基礎上對2^P－1作了大量的計算、驗證工作，並於1644年在他的《物理數學隨感》一書中斷言：對於P＝2、3、5、7、13、17、19、31、67、127、257時，2^P－1是素數；而對於P等於其他所有小於257的數時，2^P－1是合數。這裡前7個數（即2，3，5，7，13，17和19）是在前人的工作已經證實的部分。而後面的4個數（即31，67，127和257）屬於被猜測的部分。不過，人們對他的斷言深信不疑，連大數學家萊布尼茲和哥德巴赫都認為它是對的。

梅森的工作極大地激發了人們研究2^P－1型素數的熱情，成為素數研究的一個轉折點和里程碑。為了紀念他，數學界就把這種數稱為「梅森數」，並以Mp記之（其中M為梅森姓名的首字母），即Mp=2^P－1。如果梅森數為素數，則稱之為「梅森素數」（即2^P－1型素數）。

對梅森素數的驗證，需要進行艱巨的計算，即使是"猜測"部分中最小的M31=2^31－1=2147483647，也是一個10位數。而梅森自己則承認：「一個人，使用一般的驗證方法，要檢驗一個15位或20位的數字是否為素數，即使終生的時間也是不夠的。」年邁力衰的他四年之後就去世了，最終並沒有任何一個梅森素數的發現權歸屬於他，但考慮到他已經享有了「冠名權」，就把榮譽分給那些在漫漫長途上跋涉的發現者們吧！

那些手扛肩挑的年代

手算筆錄的時代，每前進一步，都顯得格外艱難。1772年，在卡達迪提出近200年之後，瑞士數學家歐拉證明了M31確實是一個素數，這是人們找到的第8個梅森素數，它共有10位數，堪稱當時世界上已知的最大素數，歐拉也因此成為第二個在發現者名單上留名的人。讓人驚嘆的是，這是在他雙目失明的情況下，靠心算完成的。這種超人般的毅力與技巧讓歐拉獲得了「數學英雄」的美譽。法國大數學家拉普拉斯（P.Laplace）說的話，或許可以代表我們的心聲：「讀讀歐拉，他是我們每一個人的老師。」

100年後，法國數學家魯卡斯提出了一個用來判別Mp是否是素數的重要定理——魯卡斯定理，這為梅森素數的研究提供了有力的工具。1883年，數學家波佛辛（Pervushin）利用魯卡斯定理證明了M61也是素數--這是梅森漏掉了的。梅森還漏掉另外兩個素數：M89和M107，它們分別在1911年與1914年被數學家鮑爾斯（Powers）發現。

還記得梅森預測的四個素數嗎？其中M31已經為歐拉證明，M127則在魯卡斯提出定理時順帶證明，雖然中間漏掉了3個，但至少還有另外兩個：M67和M257是不是素數呢......

M67的證明又是一個精彩的故事。

1903年，數學家柯爾在美國數學學會的大會上作了一個報告。他先是專註地在黑板上算出2^67－1，接著又算出193707721×761838257287，兩個算式結果完全相同！換句話說，他成功地把2^67－1分解為兩個素數相乘的形式，從而證明了M67是個合數。

報告中，他一言未發，卻贏得了現場聽眾的起立鼓掌，更成了數學史上的佳話。閱讀這段歷史，我們懂得了什麼叫做「事實勝於雄辯」。記者好奇地問他是怎樣得到這麼精彩的發現的，柯爾回答「三年里的全部星期天」。他後來當選為美國數學協會的會長，去世後，該協會專門設立了「柯爾獎」，用於獎勵作出傑出貢獻的數學家。

1922年，數學家克萊契克驗證了M257並不是素數，而是合數（但他沒有給出這一合數的因子，直到20世紀80年代人們才知道它有3個素因子）。

於是乎，梅森的四個猜測獲得了兩正確、三遺漏和兩錯誤的成績，但這無損於他的光榮。在千年的探尋之旅中，偉大如歐拉也會犯錯誤，他在1750年宣布說找到了梅森的「遺漏」：M41和M47也是素數，但最終上M41和M47都不是素數。

直到1947年，對於p≤257的梅森素數Mp的正確結果才被確定，也就是當p=2，3，5，7，13，17，19，31，61，89，107和127時，Mp是素數。現在這個表已經被反覆驗證，一定不會有錯誤了。

我們看到，在手工計算的時代，人們一共找到了12個梅森素數。

計算機！計算機！

1930年，美國數學家雷默改進了魯卡斯的工作，給出了一個新的測試方法，即魯卡斯－雷默方法。很快地，計算機時代到來了，這一方法發揮了重要的作用。1952年，數學家魯濱遜（Robinson）等人將魯卡斯－雷默方法編譯成計算機程序，使用SWAC型計算機在短短几小時之內，就發現了第13個、第14個，並在當年總共找到了5個梅森素數：M521、M607、M1279、M2203和M2281。

其後，M3217在1957年被黎塞爾（Riesel）證明是素數；M4253和M4423在1961年被赫維茲（Hurwitz）證明是素數。

1963年，美國數學家吉里斯（Gillies）證明M9689和M9941是素數，這已經是第21和22個梅森素數。1963年9月6日晚上8點，當吉里斯通過大型計算機找到第23個梅森素數M11213時，美國廣播公司（ABC）中斷了正常的節目播放，第一時間發布了這一重要消息，發現這一素數的美國伊利諾伊大學數學系全體師生更是激動地把所有從系裡發出的信件都敲上了「2^11213－1是個素數」的郵戳。

1971年3月4日晚，美國哥倫比亞廣播公司（CBS）中斷了正常節目播放，發布了布萊恩特?塔克曼（Bryant Tuckerman）使用IBM360-91型計算機找到新的梅森素數M19937的消息。而到1978年10月，世界幾乎所有的大新聞機構（包括我國的新華社）都報道了以下消息：兩名年僅18歲的美國高中生諾爾（Noll）和尼科爾（ Nickel）使用CYBER174型計算機找到了第25個梅森素數：M21701。

超級計算機的引入加快了梅森素數的尋找腳步，但隨著素數P值的增大，每一個梅森素數的產生都更加艱難，各國科學家及業餘研究者們之間的競爭變得越來越激烈。在1979年2月23日，當美國克雷研究公司的計算機專家史洛溫斯基和納爾遜正興緻沖沖地宣布他們找到第26個梅森數M23209時，有人澆來一盆冷水：兩星期前美國加州的高中生諾爾就已經給出了同樣結果。心有不甘的他們又花了一個半月的時間「卧薪嘗膽」，使用Cray－1型計算機找到了第27個梅森素數M44497，這件事成了當時不少報紙的頭版新聞。

為了與美國人較量，英國的哈威爾實驗室也專門成立了一個研究小組來尋找更大的梅森素數。他們用了兩年時間，花了12萬英鎊的經費，於1992年3月25日找到了新的梅森素數M756839。但到了1994年1月14日，史洛溫斯基等人為美國再次奪回發現「已知最大素數」的桂冠——這一梅森素數是M859433。史洛溫斯基本人一共發現了7個梅森素數，他因此被人們稱為「素數大王」。

數學研究的深入更重於計算能力的提升，在搜尋梅森素數的同時，對梅森素數的分布規律的研究也在進行著，英、法、印、美、德等國的數學家都曾分別給出過關於梅森素數分布規律的猜測，但這些猜測都以近似表達式給出，而與實際情況的接近程度均難如人意。中國數學家和語言學家周海中則是這方面研究的領先者，他運用聯繫觀察法和不完全歸納法，於1992年首先給出了梅森素數分布的精確表達式。著名的《科學美國人》雜誌有一篇文章指出：這一成果為人們探究梅森素數提供了方便，是素數研究的一項重大突破。後來這項重要成果被國際上命名為「周氏猜測」。

伴隨數學理論的改善，為了尋找梅森素數而使用的計算機也越來越強大，包括了著名的IBM360型計算機，和超級計算機Cray系列。1996年發現的M1257787是迄今為止最後一個由超級計算機發現的梅森素數，數學家使用了Cray T94，這也是人類發現的第34個梅森素數。

梅森素數的探尋之旅似乎正變得離普通人越來越遠，直到GIMPS時代的到來......

草根英雄，人人參與

網格(Grid)這一嶄新技術的出現使梅森素數的搜尋如虎添翼，也使它重新走到了「人人參與」的大眾時代。1996年初，美國數學家和程序設計師沃特曼(G.Woltman)編製了一個梅森素數的計算程序，並把它放在網頁上供數學家和數學愛好者免費使用，這就是聞名世界的「網際網路梅森素數大搜尋」（GIMPS）項目，是全世界第一個基於互聯網的分散式計算項目。

該項目利用大量普通計算機的閑置時間來獲得相當於超級計算機的運算能力，只要你去GIMPS的主頁下載為一個名為Prime95的免費程序，就可以立即參加GIMPS項目，一起踏上持續了千年的梅森素數探尋之旅。

12年來，人們通過GIMPS項目找到了12個梅森素數，其發現者來自美國、英國、法國、德國和加拿大。目前，世界上有160多個國家和地區近16萬人參加了這一項目，並動用了30多萬台計算機聯網來進行網格計算。該項目的計算能力已超過當今世界上任何一台最先進的超級矢量計算機的計算能力，運算速度超過每秒350萬億次！

為了激勵人們尋找梅森素數，1999年3月，設在美國的電子新領域基金會（EFF）向全世界宣布了為通過GIMPS項目來探尋梅森素數而設立的獎金。它規定向第一個找到超過一百萬位的素數的個人或機構頒發五萬美元的獎金。後面的獎金依次為：超過一千萬位，十萬美元；超過一億位，十五萬美元；超過十億位，二十五萬美元。

1999年6月1日，住在美國密歇根州普利茅茨的那揚?哈吉拉特瓦拉（Nayan Hajratwala）先生找到了第38個梅森素數：2^6972593－1，這也是我們知道的第一個位數超過一百萬位的素數。如果把它寫下來的話，共有兩百零九萬八千九百六十位數字。因此，哈吉拉特瓦拉先生獲得了五萬美元的獎勵。而他所做的，就是從互聯網上下載了一個程序，這個程序在他不使用他的奔騰II350型計算機時悄悄地運行。在經過111天的計算後，這個素數被發現了。

聽起來非常誘人，但你也要知道，通過參加GIMPS計劃來獲得獎金的希望是相當小的。哈吉拉特瓦拉使用的計算機是當時21000台計算機中的一台。每一個參與者都在驗證分配給他的不同梅森數，當然其中絕大多數都不是素數——只有大約三萬分之一的可能性碰到一個素數。所以，絕大多數研究者參與該項目並不是為了金錢，而是出於樂趣、榮譽感和探索精神。

成功者就在眼前，2008年年8月23日，美國加州大學洛杉磯分校數學系計算中心的僱員史密斯，通過GIMPS項目發現了第46個梅森素數2^43112609－1，這個發現被著名的美國《時代》周刊評為「2008年度50項最佳發明」之一。該素數是目前已知的最大素數，它有12978189位數，如果用普通字型大小將這個巨數連續寫下來，其長度可超過50公里！由於史密斯發現的梅森素數已超過1000萬位，他將有資格獲得EFF頒發的10萬美元大獎。雖然說史密斯是私自利用中心內的75台計算機參加GIMPS的，但由於為學校爭了光，他受到了校方的表彰。（目前共發現48個梅森素數，最大有17425170位，由美國中央密蘇里大學數學教授柯蒂斯·庫珀領導的研究小組於2013年發現。）

但在你心動之前，不妨也聽聽另一個人的故事。美國一家電話公司發現計算機經常出錯，本來只需要5秒鐘就可以接通的電話號碼，需要5分鐘才能接通。最終查出原來是僱員福雷斯特偷偷地使用公司內的2585台計算機參加GIMPS，福雷斯特承認了自己「被GIMPS項目引誘」，他最後被公司解僱，並被罰款一萬美元，這隻能說是工作與私事沒有分開，令人嘆息。

最後的話

素數的研究曾經在人類很長的歷史時期沒有實際用處，直到二次世界大戰之後，才在密碼學中得到了重要的應用。對於梅森素數的尋找之旅已經歷經千年，人們一共才找到46（48）個梅森素數，在數學家的眼裡，它們的價值遠勝於鑽石，而對它的研究，促進了計算技術、程序設計技術、密碼技術、分散式計算技術的發展。讓我們謹記梅森素數最早的研究者歐幾里得的教誨：當一個人問他"幾何學有什麼用"的時候，他對侍者說：「給他拿三個硬幣吧，他想從幾何學中得到好處。」

不是三枚硬幣，也不是百萬美元，激勵著人類不斷地向前探尋的，是好奇心、求知慾和榮譽感。

來源：算數學院

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！