一、梅森素数
我们把一个大于1的自然数叫作素数，如果只有1和它本身可以整除它。如果一个比1大的自然数不是素数，我们就叫它合数。1既不是素数，也不是合数。
比如说，你很容易就可以验证7是一个素数；而15是一个合数，因为除了1和15外，3和5都可以整除15。根据定义，2是一个素数，它是唯一的偶素数。早在公元前三百年的古希腊时代，伟大的数学家欧几里德就证明了存在着无穷多个素数。
关于素数，有许多既简单又美丽，但是极为困难的，到现在还没有答案的问题。其中有著名的哥德巴赫猜想，它是说任何一个大于6的偶数，都能表示为两个奇素数之和。还有孪生素数问题。象5和7，41和43这样相差2的素数对，被称为孪生素数。孪生素数问题是说：是不是有无穷多对孪生素数？这里要顺便提一下的是，这些看起来很简单的数学问题，它们的解决方法将一定是极其复杂的，需要最先进的数学工具。如果你不是狂妄到认为几百甚至几千年来所有在这些问题上耗费了无数聪明才智的数学家（有许多是非常伟大的）和数学爱好者加起来都不如你聪明，就不要试图用初等方法去解决这些问题，徒费时间和精力。
古希腊人还对另一种数感兴趣。他们将它称为完美数。一个大于1的自然数叫完美数，如果它的所有因子（包括1，但不包括本身）之和等于它本身。比如说6=1+2+3就是最小的完美数，古希腊人把它看作维纳斯也就是爱情的象征。28=1+2+4+7+14是另一个完美数。欧几里德证明了：一个偶数是完美数，当且仅当它具有如下形式：
2p-1 * (2p-1)
其中2p-1是素数。上面的6和28对应着p=2和3的情况。我们只要找到了一个形如2p-1的素数，也就知道了一个偶完美数；我们只要找到所有形如2p-1的素数，也就找到了所有偶完美数。所以哈吉拉特瓦拉先生不但找到了世界上已知的最大的素数，还找到了世界上已知的最大的偶完美数。嗯，你要问，关于奇完美数又是怎么样的情况？回答是：我们现在连一个奇完美数也没有找到过，我们甚至根本不知道是不是有奇完美数存在。我们只知道，要是有奇完美数存在的话，它一定是非常非常大的！奇完美数是否存在这个问题，也是一个上面所说的既简单又美丽，但是极为困难的著名数学问题。
有很长一段时间人们以为对于所有素数p，
Mp=2p-1
都是素数（注意到要使2p-1是一个素数，p本身必须是一个素数）但是在1536年雷吉乌斯(Hudalricus Regius)指出，M11=211-1=2047=23*89不是素数。
皮特罗·卡塔尔迪(Pietro Cataldi)首先对这类数进行了系统的研究。他在1603年宣布的结果中说，对于p=17，19，23，29，31和37，2p-1是素数。但是1640年费尔马使用著名的费尔马小定理（不要和那个费尔马大定理混淆起来）证明了卡塔尔迪关于p=23和37的结果是错误的，欧拉在1738年证明了p=29的结果也是错的，过后他又证明了关于p=31的结论是正确的。值得指出的是，卡塔尔迪是用手工一个一个验算取得他的结论的；而费尔马和欧拉则是使用了在他们那时最先进的数学知识，避免了许多复杂的计算和因此可能造成的错误。
马林·梅森（Marin Mersenne,1588–1648）是17世纪法国著名的数学家和修道士，也是当时欧洲科学界一位独特的中心人物。他与大科学家伽利略、笛卡尔、费马、帕斯卡、罗伯瓦、迈多治等是密友。虽然梅森致力于宗教，但他却是科学的热心拥护者，在教会中为了保卫科学事业做了很多工作。他捍卫笛卡儿的哲学思想，反对来自教会的批评；也翻译过伽里略的一些著作，并捍卫了他的理论；他曾建议用单摆来作为时计以测量物体沿斜面滚下所需时间，从而使惠更斯发明了钟摆式时钟。
梅森对科学所作的主要贡献是他起了一个极不平常的思想通道作用。17世纪时，科学刊物和国际会议等还远远没有出现，甚至连科学研究机构都没有创立，交往广泛、热情诚挚和德高望众的梅森就成了欧洲科学家之间的联系的桥梁。许多科学家都乐于将成果寄给他，然后再由他转告给更多的人。因此，他被人们誉为“有定期学术刊物之前的科学信息交换站”。梅森和巴黎数学家笛卡儿、费马、罗伯瓦、迈多治等曾每周一次在梅森住所聚会，轮流讨论数学、物理等问题，这种民间学术组织被誉为“梅森学院”，它就是法兰西科学院的前身。
1640年6月，费马在给梅森的一封信中写道：“在艰深的数论研究中，我发现了三个非常重要的性质。我相信它们将成为今后解决素数问题的基础”。这封信讨论了形如2P-1的数（其中p为素数）。早在公元前300多年，古希腊数学家欧几里得就开创了研究2P-1的先河，他在名著《几何原本》第九章中论述完美数时指出：如果2P-1是素数，则2P-1（2P-1）是完美数。
梅森在欧几里得、费马等人的有关研究的基础上对2P-1作了大量的计算、验证工作，并于1644年在他的《物理数学随感》一书中断言：对于p=2，3，5，7，13，17，19，31，67，127，257时，2P-1是素数；而对于其他所有小于257的数时，2P-1是合数。前面的7个数（即2，3，5，7，13，17和19）属于被证实的部分，是他整理前人的工作得到的；而后面的4个数（即31，67，127和257）属于被猜测的部分。不过，人们对其断言仍深信不疑，连大数学家莱布尼兹和哥德巴赫都认为它是对的。
用手工来判断一个很大的数是否素数是相当困难的，梅森神父自己也承认他的计算并不一定准确。一直要等到一个世纪以后，在1750年，欧拉宣布说找到了梅森神父的错误：M41和M47也是素数。可是伟大如欧拉也会犯计算错误——事实上M41和M47都不是素数。不过这可不是说梅森神父的结果就是对的。要等到1883年，也就是梅森神父的结果宣布了两百多年后，第一个错误才被发现：M61是一个素数。然后其它四个错误也被找了出来：M67和M257不是素数，而M89和M107是素数。直到1947年，对于p<=257的梅森素数Mp的正确结果才被确定，也就是当p=2，3，5，7，13，17，19，31，61，89，107和127时，Mp是素数。现在这个表已经被反复验证，一定不会有错误了。
虽然梅森的断言中包含着若干错误，但他的工作极大地激发了人们研究2P-1型素数的热情，使其摆脱作为“完美数”的附庸的地位。可以说，梅森的工作是素数研究的一个转折点和里程碑。由于梅森学识渊博，才华横溢，为人热情以及最早系统而深入地研究2P－1型的数，为了纪念他，数学界就把这种数称为“梅森数”；并以Mp记之（其中M为梅森姓名的首字母），即Mp=2P-1。如果梅森数为素数，则称之为“梅森素数”（即2P-1型素数）。
梅森素数貌似简单，而研究难度却很大。它不仅需要高深的理论和纯熟的技巧，而且需要进行艰巨的计算。即使属于“猜测”部分中最小的M31=231－1=2147483647，也具有10位数。可以想象，它的证明是十分艰巨的。正如梅森推测：“一个人，使用一般的验证方法，要检验一个15位或20位的数字是否为素数，即使终生的时间也是不够的。”是啊，枯燥、冗长、单调、刻板的运算会耗尽一个人的毕生精力，谁愿让生命的风帆永远在黑暗中颠簸！人们多么想知道梅森猜测的根据和方法啊，然而年迈力衰的他来不及留下记载，四年之后就去世了；人们的希望与梅森的生命一起泯灭在流逝的时光之中。看来，伟人的“猜测”只有等待后来的伟人来解决了。
下面是我们现在知道的所有梅森素数的列表：
序号
梅森素数
位数
发现时间
1
M2
1
公元前300
2
M3
1
公元前300
3
M5
2
公元前100
4
M7
3
公元前100
5
M13
4
15世纪中叶
6
M17
6
1603
7
M19
6
1603
8
M31
10
1772
9
M61
19
1883
10
M89
27
1911
11
M107
33
1914
12
M127
39
1876
13
M521
157
1952
14
M607
183
1952
15
M1279
386
1952
16
M2203
664
1952
17
M2281
687
1952
18
M3217
969
1957
19
M4253
1281
1961
20
M4423
1332
1961
21
M9689
2917
1963
22
M9941
2993
1963
23
M11213
3376
1963
24
M19937
6002
1971
25
M21701
6533
1978
26
M23209
6987
1979
27
M44497
13395
1979
28
M86293
25962
1983
29
M110503
33265
1988
30
M132049
39751
1983
31
M216091
65050
1985
32
M756839
227832
1992
33
M859433
258716
1995
34
M1257787
378632
1996
35
M1398269
420921
1996
36
M2976221
895933
1997
37
M3021377
909526
1998
38
M6972593
2098960
1999
39
M13466917
4053946
2001
40
M20996011
6320430
2003
41
M24036583
7235733
2004
42
M25964951
7816230
2005
二、梅森素数的意义
自古希腊时代直至17世纪，人们寻找梅森素数的意义似乎只是为了寻找完美数。但自梅森提出其著名断言以来，特别是欧拉证明了欧几里得关于完美数的定理的逆定理以来，完美数已仅仅是梅森素数的一种“副产品”了。
寻找梅森素数在现代已有了十分丰富的意义。寻找梅森素数是发现已知最大素数的最有效的途径，自欧拉证明M31为当时最大的素数以来，在发现已知最大素数的世界性竞赛中，梅森素数几乎囊括了全部冠军。
寻找梅森素数是测试计算机运算速度及其他功能的有力手段。如M1257787就是1996年9月美国克雷公司在测试其最新超级计算机的运算速度时得到的。梅森素数在推动计算机功能改进方面发挥了独特作用。发现梅森素数不仅仅需要高功能的计算机，它还需要素数判别和数值计算的理论与方法以及高超巧妙的程序设计技术等等，因而它还推动了数学皇后——数论的发展，促进了计算数学、程序设计技术的发展。
由于寻找梅森素数需要多种学科的支持，也由于发现新的“最大素数”所引起的国际影响使得对于梅森素数的研究能力已在某种意义上标志着一个国家的科学技术水平，而不仅仅是代表数学的研究水平。从各国各种传媒（而不仅仅是学术刊物）争相报道新的梅森素数的发现，我们也可清楚地看到这一点。
梅森素数在实用领域也有用武之地。现在人们已将大素数用于现代密码设计领域。其原理是：将一个很大的数分解成若干素数的乘积非常困难，但将几个素数相乘却相对容易得多。在这种密码设计中，需要使用较大的素数，素数越大，密码被破译的可能性就越小。
寻找梅森素数最新的意义是：它促进了分布式计算技术的发展。从最新的7个梅森素数是在因特网项目中发现这一事实，我们已可以想象到网络的威力。分布式计算技术使得用大量个人计算机去做本来要用超级计算机才能完成的项目成为可能；这是一个前景非常广阔的领域。
最后，有必要指出的是：素数有无穷多个，这一点早为欧几里得发现并证得。然而，梅森素数是否有无穷多个？这是目前尚未解决的著名数学难题；而揭开这一未解之谜，正是科学追求的目标。
三、寻找更大的素数
为什么要寻找梅森素数？为什么要打破已知最大素数的纪录？这有什么用处呢？
如果你所说的用处是指能够直接创造物质财富，那么我不得不告诉你——梅森素数没有什么用处，多知道一个非常大的素数似乎也没什么用处。即使我们知道了一个无比巨大的梅森素数，也不会使我们的钱包增加一分钱（嗨等一等！如果你只对钱感兴趣的话，也请不要立刻撇下我的文章。我其实是说，我上面说的话要排除我在这篇文章题目中提到的那十万美元的奖金——你的钱包也许会因此鼓起来的。所以请耐心一点）。
但是人类并不只需要物质财富。博物馆里的钻石有什么用场呢？为什么人类要收集它们？因为它们美丽而稀少。作为人类智慧的结晶，素数、梅森素数和与它密切相关的完美数是非常美丽的。它们的定义简单，却又如此神秘莫测，象欧几里德、笛卡尔、费尔马、莱布尼兹、欧拉这样的伟大数学家都因为它们的美丽而对它作过大量研究；大家也看到，两千多年来，经过无数代人的辛勤工作，我们一共只收集到38个梅森素数，它们是非常稀少的。对于数学家来说，搜集素数、梅森素数和完美数是和收集钻石一样富有乐趣的事情。
人类还需要荣耀——也许更胜于财富。在体育运动中，能够跑得更快一点，跳得更高一点，难道真的有实际物质方面的用途吗？不，我们喜欢接受挑战，我们希望能赢。打破一个体育世界记录，攀登珠穆朗玛峰，单身驾船横穿太平洋……，那是对人类体能极限的挑战；而寻找更大的素数，则是一项对人类智慧的挑战。当我们完成了一项前所未有的任务时，我们总会感到无比骄傲。1963年，当第23个梅森素数被找到时，发现它的美国伊利诺斯大学数学系是如此地骄傲，以致于把所有从系里发出的信件都敲上了“2^11213-1是个素数”的邮戳。
在欧拉证明M31是素数以后，下一个最大素数的记录由兰德里(Landry)于1867年获得：M_59/179951=3203431780337。这不是一个梅森素数。这个记录保持了九年。
1876年爱德华·卢卡斯使用了一个比费尔马和欧拉的方法更先进的手段，证明了M127是一个素数。这个记录保持了七十五年。直到费里叶(Ferrier)于1951年使用一部手摇计算机证明了(2^148+1)/17是一个素数，它有41位数。
借助手摇计算机的方法要算作手工计算方法还是要算做计算机方法，大概是可以探讨的问题。不过技术的发展一下子把这种争论变得毫无必要。值得指出的是，在人类寻找大素数的旅途中，数学理论的改善要远远比具有强大坚韧的计算能力重要得多。卢卡斯的方法在
1930年被勒梅(Lehmer)简化后，卢卡斯-勒梅测试成为现在寻找梅森素数的标准方法。
（卢卡斯-勒梅测试：对于所有大于1的奇数p，M_p是素数当且仅当M_p整除S(p-1)，其中S(n)由S(n+1)=S(n)^2-2，S(1)=4递归定义。4 14 194 37634 1416317954 2005956546822746114这个测试尤其适合于计算机运算，因为除以M_p=2^p-1的运算在二进制下可以简单地用计算机特别擅长的移位和加法操作来实现。判断一个梅森数是素数的方法比判断一个差不多大小的其他类型数是素数的方法要简单得多，所以在寻找最大素数的过程中，大部分纪录都是梅森素数。）
在1951年米勒和维勒(Miller & Wheeler)借助于EDSAC计算机（这种计算机还不如我们现在使用的一般计算器，它只有5K的内存）发现了长达79位的素数180(M_127)^2+1。这个记录还是没能保持多久。次年罗宾逊应用SWAC计算机，在1952年初发现了第13和第14号梅森素数：M_521和M_607，后面连续三个梅森素数也在同一年被陆续发现：M_1279，M_2203和M_2281。
在那以后的年代里，为了打破巨大素数纪录而使用的计算机越来越强大，其中有著名的IBM360型计算机，和超级计算机Cray系列。大家可以参看上面的梅森素数表来了解这个竞赛过程。在此其间只有一次一个不是梅森素数的素数坐上过“已知最大素数”的宝座，它是39158*2^216193-1，在1989年被发现。1996年发现的M_1257787是迄今为止最后一个由超级计算机发现的梅森素数，数学家使用了Cray T94。
然后，GIMPS的时代到来了。
1995年程序设计师乔治·沃特曼(George Woltman)开始收集整理有关梅森素数计算的数据。他编制了一个梅森素数寻找程序并把它放在网页上供数学爱好者免费使用。这就是“互联网梅森素数大搜索”计划(GIMPS，the Great Internet Mersenne Prime Search)。在这个计划中，十几位数学专家和几千名数学爱好者正在寻找下一个最大的梅森素数，并且检查以前梅森素数纪录之间未被探索的空隙。比如上面的梅森素数表中，最后那个素数的序号是未知的，我们不知道第37号梅森素数和它之间是否还存在着其他未被发现的梅森素数。
1997年斯科特·库尔沃斯基(Scott Kurowski)和其他人建立了“素数网”(PrimeNet)，使分配搜索区间和向GIMPS发送报告自动化。现在只要你去GIMPS的主页下载那个免费程序，你就可以立刻参加GIMPS计划搜寻梅森素数。几乎所有的常用计算机平台都有可用的版本。程序以最低的优先度在你的计算机上运行，所以对你平时正常地使用计算机几乎没有影响。程序也可以随时被停止，下一次启动时它将从停止的地方继续进行计算。
从1996年到1998年，GIMPS计划发现了三个梅森素数：M_1398269、M_2976221和M_3021377，都是使用奔腾型计算机得到的结果。
1999年3月，在互联网上活动的一个协会“电子边界基金”(EFF，Electronic Frontier Foundation)宣布了由一位匿名者资助的为寻找巨大素数而设立的奖金。它规定向第一个找到超过一百万位的素数的个人或机构颁发五万美元的奖金，这就是我们最一开始说到的哈吉拉特瓦拉得到的奖金。后面的奖金依次为：超过一千万位，十万美元；超过一亿位，十五万美元；超过十亿位，二十五万美元。
搜寻结果的验证和奖金的颁发是非常严格的。比如说，得到的结果必须是显式的——你不能宣称你的结果是一个有一百个方程组成的方程组的解，却不把它解出来。结果必须由另一台计算机独立验证。所有这些规则都在EFF网站上进行了解释。
应该指出的是，通过参加GIMPS计划来获得奖金的希望是相当小的。哈吉拉特瓦拉使用的计算机是当时21000台计算机中的一台。每一个参与者都在验证分配给他的不同梅森数，当然其中绝大多数都不是素数——他只有大约三万分之一的可能性碰到一个素数。
下一个十万美元的奖金将被颁发给第一个找到超过一千万位的素数的个人或机构。这一次的计算量将大约相当于上一次的125倍。现在GIMPS得到的计算能力为每秒7000亿次浮点运算，和一台当今最先进的超级矢量计算机，比如Cray T932的运行能力相当。但是如果GIMPS要使用这样的超级计算机，一天就需要支付大约二十万美元。而现在他们需要的费用，仅仅是支持网站运行的费用，和总共几十万美元的奖金罢了。
GIMPS只不过是互联网上众多的分布式计算计划中的一个，GIMPS主页上就有这些计划的介绍。
分布式计算是一门计算机学科，它研究如何把一个需要非常巨大的计算能力才能解决的问题分成许多小的部分，然后把这些部分分配给许多计算机进行处理，最后把这些计算结果综合起来得到最终的结果。有时侯计算量是如此之大，需要全世界成千上万甚至更多台计算机一起工作，才能在合乎情理的时间内得到结果。GIMPS计划就是在进行这样的分布式计算。
但它并不是最著名的分布式计算计划。致力于寻找宇宙中智慧生命的“搜寻地外文明计划”(SETI计划)中的SETI@HOME工程，已在全世界招募了290万名(!)志愿者，利用屏幕保护程序来处理射电望远镜接受到的大量的宇宙间传来的无线电信号。如果你参加这个计划，也许有一天会在你的计算机上破译出外星人发来的问候呢。
你也可以用你的计算机空余的计算能力为人类征服癌症作出贡献。英国科学家设计了类似SETI@HOME工程的分布式计算屏保，它从有关网站下载数据，分析化学物质分子的抗癌性能，然后将分析结果通过互联网传回给研究人员，作为研制新型抗癌药物的参考。这项工程于2001年4月3日在美国加利福尼亚州正式启动。
计算机硬件的更新令人目不暇接，上半年买的最新式的个人电脑，在下半年就变成了大路货。三四年前的CPU，现在变得一钱不值——也许不能这么说，你根本就买不到它们了——市面上最便宜的CPU也要比它们强大得多。而一台普通的家用计算机连续运转五年也是没有问题的。所以，对待计算机的最经济的态度就是：让它运转。
而人类还有那么多的东西需要计算，还有那么多的问题需要找到回答，还有那么多的难关需要克服。我们需要越来越巨大的计算能力，我们也拥有这样的计算能力，只是太多太多被白白地闲置浪费掉了。互联网已经使大规模的分布式计算计划成为可能。现在，我们唯一需要的，就是这个网每一个结点上计算机用户的意愿和信心了。
