梅森素数对于许多教师来讲,是个陌生的名词;但在近几年的高校自主招生测试中,梅森素数却频频出现。在数千年的人类历史中,人类对梅森素数的探索脚步,也从未停止过。人类对梅森素数的痴迷,除了因为它在密码编制、程序设计、分布式计算技术、计算机测试等方面的实用价值外,还在于它是人类好奇心、求知欲和荣誉感的最好见证。
还记得你小学时背诵的素数表吗?那时候它还叫做质数表“2、3、5、7……”如今你是否已经真正理解了老师说过的话:这些只能被1和本身整除的数,具有着无穷的魅力。
还记得你中学时计算的2的整数幂吗?计算机时代,作为二进制的体现,它们正大行其道。“2、4、8、16、32、64、128、256……”十多年来,电脑内存的容量正是经历了这些熟悉的数字,直到现在的2048M(2G)以及更多。
现在,让我们从这些2的整数幂中挑出以素数为指数的,再把它减1,试试看会发现什么?22-1=3、23-1=7、25-1=31、27-1=127……
嗯,你的心是不是激动起来了?一个伟大的发现似乎就在眼前……
别急别急,你的发现很妙,只是有些儿惋惜……你已经迟到了二千年。
在2300多年前,古希腊的数学家,那位写出不朽的《几何原本》的欧几里得在证明了素数有无穷多个之后,就顺便指出:有许多素数可以写成2P-1的形式,其中指数P也是素数。很容易想到,刚才你所发现的22-1、23-1、25-1、27-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具有相同性质的数都堪称完美数。
欧几里得在《几何原本》中证明了如果2P-1是一个素数,那么2P-1(2P-1)一定是一个完美数(你会发现,当P分别等于2、3时,它就对应着前两个完美数6、28)。
再后来,一个叫欧拉的人进一步证明,每一个偶完美数也必定是欧几里得所给出的形式。(不要问我奇完美数呢?就连它是否存在,本身也是无数个关于素数的难题中至今未解的一个。)
很容易看到,找到了2P-1形式的素数,也就发现了新的完美数。
形如2P-1的素数还长期占据了人们寻找到的最大素数的光荣榜(仅在1989年后被39158×2216193-1夺走三年),因为判断这样一个数是素数的方法比判断一个差不多大小的其他类型数是素数的方法要简单得多。
对2P-1型素数的搜寻之旅就这样出发了,先后投入这个漫漫长途的就有数学大师费马、笛卡尔、莱布尼兹、哥德巴赫、欧拉、高斯、哈代、图灵……这一个个闪光的名字正如暗夜前行的火炬手,照亮了人类通往未知的道路。
历史的天空闪烁几颗星
现在,让我们坐上时间机器,回到过去,重新浏览这来路风光吧。
1456年,又一个没有留下姓名的人发现了第5个2P-1型的素数:213-1。若是你就降生在十五世纪,或许这次发现的光荣将归属于你。只是,你更有可能犯下和这个时代的人们一样的错误,以为对于所有的素数P,2P-1都是素数。要知道,这个错误是一百年之后,直到1536年,才由雷吉乌斯(Hudalricus Regius)打破的。他指出,211-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年,梅森在欧几里得、费马等人的有关研究的基础上对2P-1作了大量的计算、验证工作,并于1644年在他的《物理数学随感》一书中断言:对于P=2、3、5、7、13、17、19、31、67、127、257时,2P-1是素数;而对于P等于其他所有小于257的数时,2P-1是合数。这里前7个数(即2,3,5,7,13,17和19)是在前人的工作中已经证实的部分。而后面的4个数(即31,67,127和257)属于被猜测的部分。不过,人们对他的断言深信不疑,连大数学家莱布尼兹和哥德巴赫都认为它是对的。
梅森的工作极大地激发了人们研究2P-1型素数的热情,成为素数研究的一个转折点和里程碑。为了纪念他,数学界就把这种数称为“梅森数”,并以Mp记之(其中M为梅森姓名的首字母),即Mp=2P-1。如果梅森数为素数,则称之为“梅森素数”(即2P-1型素数)。
对梅森素数的验证,需要进行艰巨的计算,即使是“猜测”部分中最小的M31=231-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年,数学家柯尔在美国数学学会的大会上作了一个报告。他先是专注地在黑板上算出267-1,接着又算出193707721×761838257287,两个算式结果完全相同!换句话说,他成功地把267-1分解为两个素数相乘的形式,从而证明了M67是个合数。
报告中,他一言未发,却赢得了现场听众的起立鼓掌,更成了数学史上的佳话。阅读这段历史,我们懂得了什么叫做“事实胜于雄辩”。当时,记者好奇地问他是怎样得到这么精彩的发现的,柯尔回答“三年里的全部星期天”。他后来当选为美国数学协会的会长,去世后,该协会专门设立了“柯尔奖”,用于奖励作出杰出贡献的数学家。
1922年,数学家克莱契克验证了M257并不是素数,而是合数(但他没有给出这一合数的因子,直到20世纪80年代人们才知道它有3个素因子)。
于是乎,梅森的四个猜测获得了两正确、三遗漏和两错误的成绩,但这无损于他的光荣。
直到1947年,对于p≤257的梅森素数Mp的正确结果才被确定,也就是当p=2,3,5,7,13,17,19,31,61,89,107和127时,Mp是素数。现在这个表已经被反复验证,一定不会有错误了。
我们看到,在手工计算的时代,人们一共找到了12个梅森素数。