首页 数学珍宝梅森素数

数学珍宝梅森素数

数学珍宝梅森素数数学珍宝梅森素数 ——迄今人类仅发现 47 个已知最大的梅森素数 1 法国数学家马林_梅森 2 数学珍宝梅森素数众所周知，素数也叫质数，是只能被 1和自身整除的数，如 2、3、5、7、 11 等等。2300 年前，古希腊数学家欧几里得就已证明素数有无穷多个，并提出一些素数可写成“2p-1”的形式，这里的指数 p也是一个素数。这种特殊形式的素数具有独特的性质和无穷的魅力，千百年来一直吸引着众多的数学家(包括数学大师费马、笛卡尔、哥德巴...

数学珍宝梅森素数 ——迄今人类仅发现 47 个已知最大的梅森素数 1 法国数学家马林_梅森 2 数学珍宝梅森素数众所周知，素数也叫质数，是只能被 1和自身整除的数，如 2、3、5、7、 11 等等。2300 年前，古希腊数学家欧几里得就已证明素数有无穷多个，并提出一些素数可写成“2p-1”的形式，这里的指数 p也是一个素数。这种特殊形式的素数具有独特的性质和无穷的魅力，千百年来一直吸引着众多的数学家(包括数学大师费马、笛卡尔、哥德巴赫、欧拉、高斯、哈代等)和无数的业余数学爱好者对它进行探究。 17 世纪法国数学家、法兰西科学院奠基人马林·梅森（Marin Mersenne,1588 –1648）是其中成果较为卓著的一位，因此后人将形如“2p-1”的正整数，其中指数 p 是素数，称为梅森数(Mersenne number)。梅森数常记为 Mp。若 Mp 是素数，则称为梅森素数(Mersenne prime)。p＝2，3，5，7 时，Mp 都是素数，但 M11＝2047＝23×89 不是素数。已发现的最大梅森素数是 p＝43,112,609 的情形，此时 Mp 是一个 12,978,189 位数。如果用普通字号将这个巨数连续写下来，其长度可超过 50 公里！是否有无穷多个梅森素数是数论中未解决的难题之一。迄今为止，人类仅发现 47 个梅森素数。由于这种素数珍奇而迷人，它被人们称为“数学珍宝”。梅森素数历来是数论研究的一项重要内容，也是当今科学探索的热点和难点之一。一、概念也许会有人感到奇怪：素数不就是在大于 1的整数中只能被 1和其自身整除的数吗？古希腊数学大师欧几里得早就证明了素数有无穷多个，既然有无穷个，那么就应该有一个素数数列的公式，为了寻找这个公式，人们耗尽了巨大的心血 (参见百度百科“素数分布”)。在数学和计算机科学高度发达的今天，为什么发现一个已知的最大素数竟如此困难？找到一个已知的最大梅森素数竟成了科学上的大事？！是的，魅力无穷的梅森素数具有许多特异的性质和现象，千百年来一直吸引着众多的数学家和数学爱好者对它进行研究；虽然已经揭示了一些规律，但围绕着它仍然有许多未解之谜，等待着人们去探索。二、由来 3 马林·梅森（Marin Mersenne,1588–1648）是 17 世纪法国著名的数学家和修道士，也是当时欧洲科学界一位独特的中心人物。他与大科学家伽利略、笛卡尔、费马、帕斯卡、罗伯瓦、迈多治等是密友。虽然梅森致力于宗教，但他却是科学的热心拥护者，在教会中为了保卫科学事业做了很多工作。他捍卫笛卡尔的哲学思想，反对来自教会的批评；也翻译过伽里略的一些著作，并捍卫了他的理论；他曾建议用单摆来作为时计以测量物体沿斜面滚下所需时间，从而使惠更斯发明了钟摆式时钟。梅森对科学所作的主要贡献是他起了一个极不平常的思想通道作用。17 世纪时，科学刊物和国际会议等还远远没有出现，甚至连科学研究机构都没有创立，交往广泛、热情诚挚和德高望众的梅森就成了欧洲科学家之间的联系的桥梁。许多科学家都乐于将成果寄给他，然后再由他转告给更多的人。因此，他被人们誉为“有定期学术刊物之前的科学信息交换站”。梅森和巴黎数学家笛卡儿、费马、罗伯瓦、迈多治等曾每周一次在梅森住所聚会，轮流讨论数学、物理等问题，这种民间学术组织被誉为“梅森学院”，它就是法兰西学院的前身。 1640 年 6 月，费马在给梅森的一封信中写道：“在艰深的数论研究中，我发现了三个非常重要的性质。我相信它们将成为今后解决素数问题的基础”。这封信讨论了形如 2P－1 的数（其中 p为素数）。早在公元前 300 多年，古希腊数学家欧几里得就开创了研究 2P－1 的先河，他在名著《几何原本》第九章中论述完美数时指出：如果 2P－1 是素数，则(2p－1)2^(p－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）属于被猜测的部分。不过，人们对其断言仍深信不疑，连大数学家莱布尼兹和哥德巴赫都认为它是对的。虽然梅森的断言中包含着若干错误（后文详述），但他的工作极大地激发了人们研究 2P－1 型素数的热情，使其摆脱作为“完美数”的附庸的地位。可以说，梅森的工作是素数研究的一个转折点和里程碑。由于梅森学识渊博，才华横溢，为人热情以及最早系统而深入地研究 2P－1 型的数，为了纪念他，数学界就把这种数称为“梅森数”；并以 Mp 记之（其中 M为梅森姓名的首字母），即 Mp=2P －1。如果梅森数为素数，则称之为“梅森素数”（即 2P－1 型素数）。 4 梅森素数貌似简单，而研究难度却很大。它不仅需要高深的理论和纯熟的技巧，而且需要进行艰巨的计算。即使属于“猜测”部分中最小的 M31=231－ 1=2147483647，也具有 10 位数。可以想象，它的证明是十分艰巨的。正如梅森推测：“一个人，使用一般的验证方法，要检验一个 15 位或 20 位的数字是否为素数，即使终生的时间也是不够的。”是啊，枯燥、冗长、单调、刻板的运算会耗尽一个人的毕生精力，谁愿让生命的风帆永远在黑暗中颠簸！人们多么想知道梅森猜测的根据和方法啊，然而年迈力衰的他来不及留下记载，四年之后就去世了；人们的希望与梅森的生命一起泯灭在流逝的时光之中。看来，伟人的“猜测” 只有等待后来的伟人来解决了。三、位数计算由于梅森数可能十分巨大，因此计算梅森数的精确位数，需要运用换底公式： log10(2p)=p*ln(2)/ln(10)，然后加 1再取整即可。（因为 10n有 n+1 位，所以要加 1）。计算梅森数的位数的 C++源代码如下： #include #include #include using namespace std; int main(){ int p; cout<<"Please input a prime number p:"; cin>>p; cout<<"M"< 表我们的心声：“读读欧拉，他是我们每一个人的老师。”欧拉还证明了欧几里得关于完美数的定理的逆定理，即：每个偶完美数都具有形式(2P－1)2^(p－1)，其中 2P－1 是素数。这就使得偶完美数完全成了梅森素数的“副产品”了。欧拉的艰辛给人们提示：在伟人难以突破的困惑面前要想确定更大的梅森素数，只有另辟蹊径了。 100 年后，法国数学家鲁卡斯提出了一个用来判别 Mp 是否是素数的重要定理——鲁卡斯定理。鲁卡斯的工作为梅森素数的研究提供了有力的工具。1883 年，数学家波佛辛利用鲁卡斯定理证明了 M61 也是素数——这是梅森漏掉的。梅森还漏掉另外两个素数：M89 和 M107，它们分别在 1911 年与 1914 年被数学家鲍尔斯发现。 1903 年，在美国数学学会的大会上，数学家柯尔作了一个一言不发的报告，他在黑板上先算出 267－1，接着又算出 193707721×761838257287，两个结果相同。这时全场观众站了起来为他热烈鼓掌，这在美国数学学会开会的历史上是绝无仅有的一次。他第一个否定了“M67 为素数”这一自梅森断言以来一直被人们相信的结论。这短短几分钟的报告却花了柯尔 3年的全部星期天。1922 年，数学家克莱契克进一步验证了 M257 并不是素数，而是合数（但他没有给出这一合数的因子，直到 20 世纪 80 年代人们才知道它有 3个素因子）。 1930 年，美国数学家雷默改进了鲁卡斯的工作，给出了一个针对 Mp 的新的素性测试方法，即鲁卡斯-雷默方法：Mp>3 是素数的充分必要条件是 Lp-2=0，其中 L0=4，Ln+1=(Ln－2)ModMp。这一方法直到今天的“计算机时代”仍发挥重要作用。 “手算笔录”的年代，人们历尽艰辛，仅找到 12 个梅森素数。而计算机的产生使寻找梅森素数的研究者如虎添翼。1952 年，数学家鲁滨逊等人将鲁卡斯- 雷默方法编译成计算机程序，使用 SWAC 型计算机在几个月内，就找到了 5个梅森素数：M521、M607、M1279、M2203 和 M2281。其后，M3217 在 1957 年被数学 6 家黎塞尔证明是素数；M4253 和 M4423 在 1961 年被数学家赫维兹证明是素数。 1963 年，美国数学家吉里斯证明 M9689 和 M9941 是素数。探究梅森素数不仅极富挑战性，而且对探究者来说有一种巨大的自豪感。 1963 年 9 月 6 日晚上 8点，当第 23 个梅森素数 M11213 通过大型计算机被找到时，美国广播公司（ABC）中断了正常的节目播放，以第一时间发布了这一重要消息；发现这一素数的美国伊利诺伊大学数学系全体师生感到无比骄傲，为了让全世界都分享这一重大成果，以致于把所有从系里发出的信件都敲上了“211213 －1 是个素数”的邮戳。伊利诺伊大学数学系盖的邮戳 1971 年 3 月 4 日晚，美国哥伦比亚广播公司（CBS）中断了正常节目播放，发布了塔可曼使用 IBM360-91 型计算机找到新的梅森素数 M19937 的消息。而到 1978 年 10 月，世界几乎所有的大新闻机构（包括我国的新华社）都报道了以下消息：两名年仅 18 岁的美国高中生诺尔和尼科尔使用 CYBER174 型计算机找到了第 25 个梅森素数：M21701。随着素数 P值的增大，每一个梅森素数的产生都艰辛无比；而各国科学家及业余研究者们仍乐此不疲，激烈竞争。1979 年 2 月 23 日，当美国克雷研究公司的计算机专家大卫·史洛温斯基和哈里·纳尔逊宣布他们找到第 26 个梅森素数 M23209 时，人们告诉他们：在两个星期前美国加州的高中生兰登·诺尔已得到这一结果。为此，史洛温斯基潜心发愤，花了一个半月的时间，使用 CRAY-1 型计算机找到了新的梅森素数 M44497。这个记录成了当时不少美国报纸的头版新闻。之后，这位计算机专家乘胜前进，使用经过改进的 CRAY-XMP 型计算机在 1983 年至 1985 年间找到了 3个梅森素数：M86243、M132049 和 M216091。但他未能确定 M86243 和 M216091 之间是否有异于 M132049 的梅森素数。而到了 1988 年，科尔魁特和韦尔什使用 NEC-FX2 型超高速并行计算机果然捕捉到了一条“漏网之鱼”——M110503。沉寂 4年之后，1992 年 3 月 25 日，英国原子能技术权威机构——哈威尔实验室的一个研究小组宣布他们找到了新的梅森素数 M756839。 1994 年 1 月 14 日，史洛温斯基和盖奇为其公司再次夺回发现“已知最大素数” 7 的桂冠——这一素数是 M859433。而下一个梅森素数 M1257787 仍是他们的成果。这一素数是使用 CRAY-794 超级计算机在 1996 年取得的。史洛温斯基由于发现 7 个梅森素数，而被人们誉为“素数大王”。但使用超级计算机寻找梅森素数的游戏实在太昂贵了。网格(Grid)这一崭新技术的出现使梅森素数的探寻如虎添翼。1996 年初，美国数学家和程序设计师乔治·沃特曼编制了一个梅森素数计算程序，并把它放在网页上供数学家和数学爱好者免费使用，这就是著名的“因特网梅森素数大搜索”（GIMPS)项目。该项目采取网格计算方式，利用大量普通计算机的闲置时间来获得相当于超级计算机的运算能力。1997 年美国数学家及程序设计师斯科特·库尔沃斯基和其他人建立了”素数网”（PrimeNet），使分配搜索区间和向 GIMPS 发送报告自动化。现在只要人们去 GIMPS 的主页下载那个免费程序，就可以立即参加该项目来搜寻新的梅森素数。为了激励人们寻找梅森素数和促进网格技术发展，设在美国的电子新领域基金会(EFF)于1999年3月向全世界宣布了为通过GIMPS项目来寻找新的更大的梅森素数而设立的奖金。它规定向第一个找到超过 1000 万位数的个人或机构颁发 10 万美元。后面的奖金依次为：超过 1 亿位数，15 万美元；超过 10 亿位数，25 万美元。其实，绝大多数研究者参与该项目并不是为了金钱，而是出于乐趣、荣誉感和探索精神。 2008 年 8 月 23 日，美国加州大学洛杉矶分校计算机专家埃德森·史密斯发现了第 45 个梅森素数“2的 43112609 次方减 1”，该素数有 12978189 位，它是目前已知的最大素数。如果用普通字号将这个巨数连续写下来，其长度可超过 50 公里！史密斯是第一个发现超过 1000 万位的梅森素数的人，他获得了 EFF 颁发的 10 万美元大奖。而另一位仁兄就没有这样的运气。美国一家电话公司的雇员麦克·福雷斯特偷偷地使用公司内的 2585 台计算机参加 GIMPS 项目；随后公司发现计算机经常会出些差错，本来只需要 5 秒钟就可以接通的电话号码，需要 5 分钟才能接通。联邦调查局最终查到了原因，福雷斯特承认“被 GIMPS 项目引诱”；他最后被解雇，并被罚款一万美元。这只能说是公事与私事没有分开，实在令人叹息。 15 年来，人们通过 GIMPS 项目找到了 13 个梅森素数，其发现者来自美国、英国、法国、德国、加拿大和挪威。目前世界上已有 180 多个国家和地区超过 23 万人参加了这一国际合作项目，并动用了 45 万多台计算机联网来进行网格计算，以寻找新的梅森素数。该项目的计算能力已超过当今世界上任何一台最先进的超级矢量计算机的计算能力，运算速度达到每秒 700 万亿次。著名的《自然》 8 杂志说：GIMPS 项目不仅会进一步激发人们对梅森素数寻找的热情，而且会引起人们对网格技术应用研究的高度重视。时至今日止，人们已经发现了 47 个梅森素数，并且确定 M20996011 位于梅森素数序列中的第 40 位。现把它们列表如下： n Mn Mn 的位数发现期发现者 1 2 3 1 古代古人 2 3 7 1 古代古人 3 5 31 2 古代古人 4 7 127 3 古代古人 5 13 8191 4 1456- 无名氏 6 17 131071 6 1588- Cataldi 7 19 524287 6 1588- Cataldi 8 31 2147483647 10 1772- 欧拉 9 61 2305843009213693951 19 1883- Pervushin 10 89 618970019 …449562111 27 1911- Powers 11 107 162259276 …010288127 33 1914- Powers 12 127 170141183 …884105727 39 1876- 卢卡斯 13 521 686479766 …115057151 157 1952-1-30 Robinson 14 607 531137992 …031728127 183 1952-1-30 Robinson 15 1,279 104079321 …168729087 386 1952-6-25 Robinson 16 2,203 147597991 …697771007 664 1952-10-7 Robinson 17 2,281 446087557 …132836351 687 1952-10-9 Robinson 18 3,217 259117086 …909315071 969 1957-9-8 Riesel 19 4,253 190797007 …350484991 1,281 1961-11-3 Hurwitz 20 4,423 285542542 …608580607 1,332 1961-11-3 Hurwitz 21 9,689 478220278 …225754111 2,917 1963-5-11 Gillies 22 9,941 346088282 …789463551 2,993 1963-5-16 Gillies 23 11,213 281411201 …696392191 3,376 1963-6-2 Gillies 9 24 19,937 431542479 …968041471 6,002 1971-3-4 布莱恩特·塔克曼 25 21,701 448679166 …511882751 6,533 1978-10-30 Noll & Nickel 26 23,209 402874115 …779264511 6,987 1979-2-9 Noll 27 44,497 854509824 …011228671 13,395 1979-4-8 Nelson & Slowinski 28 86,243 536927995 …433438207 25,962 1982-9-25 Slowinski 29 110,503 521928313 …465515007 33,265 1988-1-28 Colquitt & Welsh 30 132,049 512740276 …730061311 39,751 1983-9-20 Slowinski 31 216,091 746093103 …815528447 65,050 1985-9-6 Slowinski 32 756,839 174135906 …544677887 227,832 1992-2-19 Slowinski & Gage 33 859,433 129498125 …500142591 258,716 1994-1-10 Slowinski & Gage 34 1,257,787 412245773 …089366527 378,632 1996-9-3 Slowinski & Gage 35 1,398,269 814717564 …451315711 420,921 1996-11-13 GIMPS/Joel Armengaud 36 2,976,221 623340076 …729201151 895,932 1997-8-24 GIMPS/Gordon Spence 37 3,021,377 127411683 …024694271 909,526 1998-1-27 GIMPS/Roland Clarkson 38 6,972,593 437075744 …924193791 2,098,960 1999-6-1 GIMPS/Nayan Hajratwala 39 13,466,917 924947738 …256259071 4,053,946 2001-11-14 GIMPS/Michael Cameron 40* 20,996,011 125976895 …855682047 6,320,430 2003-11-17 GIMPS/Michael Shafer 41* 24,036,583 299410429 …733969407 7,235,733 2004-5-15 GIMPS/Josh Findley 42* 25,964,951 122164630 …577077247 7,816,230 2005-2-18 GIMPS/Martin Nowak 43* 30,402,457 315416475 …652943871 9,152,052 2005-12-15 Cooper 及 Steven Boone 44* 32,582,657 124575026 …053967871 9,808,358 2006-9-4 GIMPS/Curtis Cooper 及 Steven Boone 45* 37,156,667 202254406 …308220927 11,185,272 2008-9-6 GIMPS/Hans-Michael Elvenich 46* 42,643,801 169873516 …562314751 12,837,064 2009-4-12 GIMPS/Odd M. Strindmo 47* 43,112,609 316470269 …697152511 12,978,189 2008-8-23 GIMPS/Edson Smith 人们在寻找梅森素数的同时，对它的重要性质——分布规律的研究也一直在进行着。从已发现的梅森素数来看，它在正整数中的分布时疏时密、极不规则。我们甚至可以看到，连找到梅森素数的时间分布都极不规则，有时许多年未能找到一个，而有时则一下找到好几个。因此研究梅森素数的分布规律似乎比寻找新的梅森素数更为困难。数学家们在长期的摸索中，提出了一些猜想。英国数学家 10 香克斯、美国数学家吉里斯、法国数学家托洛塔和德国数学家伯利哈特就曾分别给出过关于梅森素数分布的猜测，但他们的猜测有一个共同点，就是都以近似表达式给出；而它们与实际情况的接近程度均未尽如人意。中国数学家及语言学家周海中是这方面研究的领先者——他运用联系观察法和不完全归纳法，经过多年的研究，于 1992 年 2 月首次给出了梅森素数分布的精确表达式，为人们寻找这一素数提供了方便；后来这一重要成果被国际上命名为“周氏猜测”。著名的《科学》杂志上有一篇评论文章指出，这项成果是素数研究中的一项重大突破。美籍挪威数论大师、菲尔茨奖和沃尔夫奖得主阿特勒·塞尔伯格认为：周氏猜测具有创新性，开创了富于启发性的新方法；其创新性还表现在揭示新的规律上。中科院院士张景中教授也对这一猜测评价很高。五、意义梅森素数历来都是数论研究的一项重要内容，也是当今科学探索的热点和难点之一。自古希腊时代直至 17 世纪，人们寻找梅森素数的意义似乎只是为了寻找完美数。但自梅森提出其著名断言以来，特别是欧拉证明了欧几里得关于完美数的定理的逆定理以来，完美数已仅仅是梅森素数的一种“副产品”了。梅森素数在当代具有重大的理论意义和丰富的实用价值。寻找梅森素数在现代已有了十分丰富的意义。寻找梅森素数是发现已知最大素数的最有效的途径，自欧拉证明 M31 为当时最大的素数以来，在发现已知最大素数的世界性竞赛中，梅森素数几乎囊括了全部冠军。其探究推动了“数学皇后”——数论的研究，促进了计算技术、密码技术、程序设计技术的发展以及快速傅立叶变换的应用。寻找梅森素数是测试计算机运算速度、硬件运算是否正确及其他功能的有力手段。如 M1257787 就是 1996 年 9 月美国克雷公司在测试其最新超级计算机的运算速度时得到的。梅森素数在推动计算机功能改进方面发挥了独特作用。发现梅森素数不仅仅需要高功能的计算机，它还需要素数判别和数值计算的理论与方法以及高超巧妙的程序设计技术等等，因而它还推动了数学皇后——数论的发展，促进了计算数学、程序设计技术的发展。梅森素数在实用领域也有用武之地。现在人们已将大素数用于现代密码设计领域。其原理是：将一个很大的数分解成若干素数的乘积非常困难，但将几个素数相乘却相对容易得多。在这种密码设计中，需要使用较大的素数，素数越大，密码被破译的可能性就越小。 11 12 寻找梅森素数最新的意义是：促进了网格技术的发展，促进了分布式计算技术的发展。而网格技术是一项应用非常广阔、前景十分诱人的高新技术。从最新的 13 个梅森素数是在因特网项目中发现这一事实，我们已可以想象到网络的威力。分布式计算技术使得用大量个人计算机去做本来要用超级计算机才能完成的项目成为可能；这是一个前景非常广阔的领域。它的探究还推动了快速傅立叶变换的应用。在当代梅森素数的探究需要多种学科和技术的支持，也由于发现新的“最大素数”所引起的国际影响。使得许多科学家认为：对于梅森素数的研究能力和成果已在一定程度上反映了着一个国家的科学技术水平，而不仅仅是代表数学的研究水平。英国顶尖科学家、牛津大学教授马科斯·索托伊甚至认为：梅森素数探究可以挑战人类科技与智慧极限，其成果是一个国家科技创新能力的重要标志之一。它是人类智力发展在数学上的一种标志,也是科学发展的里程碑之一。从各国各种传媒（而不仅仅是学术刊物）争相报道新的梅森素数的发现，我们也可清楚地看到这一点。可以相信，梅森素数这颗数学海洋中的璀璨明珠正以其独特的魅力，吸引着更多的有志者去寻找和研究。爱因斯坦曾说：“提出一个问题往往比解决一个问题更为重要，因为解决一个问题也许只是一个数学上或实验上的技巧问题。而提出新的问题、新的可能性，从新的角度看旧问题，却需要创造性的想像力，而且标志着科学的真正进步。” 周氏猜测的提出已有近 20 年，目前人们需要做的是破解这一难题。最后，有必要指出的是：梅森素数是否有无穷多个？这是目前尚未解决的著名数学谜题；而揭开这一未解之谜，正是科学追求的目标。让我们以数学大师希尔伯特的名言来结束本文：“我们必须知道，我们必将知道。”

                    本文档为【数学珍宝梅森素数】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
                    图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。 
 该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。

                    [版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。

                    本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。

                    网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
                

下载需要：免费已有0 人下载

立即下载

数学珍宝梅森素数

你可能还喜欢