素数：数学起源及相关问题

梅森素数

我们把一个大于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,

M_p＝2p－1

都是素数(注意到要使2p－1是一个素数,p本身必须是一个素数,想一想为什么?)但是在1536年雷吉乌斯(Hudalricus Regius)指出,M_11＝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)在1644年他发表了他的成果。他宣称对于p＝2,3,5,7,13,17,19,31,67,127和257,2p－1都是素数,而对于其它小于257的素数p,2p－1都是合数。今天我们把形如M_p＝2p－1的素数叫做梅森素数,M_p中的M就是梅森姓氏的第一个字母。

用手工来判断一个很大的数是否素数是相当困难的,梅森神父自己也承认他的计算并不一定准确。一直要等到一个世纪以后,在1750年,欧拉宣布说找到了梅森神父的错误:M_41和M_47也是素数。可是伟大如欧拉也会犯计算错误——事实上M_41和M_47都不是素数。不过这可不是说梅森神父的结果就是对的。要等到1883年,也就是梅森神父的结果宣布了两百多年后,第一个错误才被发现:M_61是一个素数。然后其它四个错误也被找了出来:M_67和M_257不是素数,而M_89和M_107是素数。直到1947年,对于p≤257的梅森素数M_p的正确结果才被确定,也就是当p＝2,3,5,7,13,17,19,31,61,89,107和127时,M_p是素数。现在这个表已经被反复验证,一定不会有错误了。

下面是我们现在知道的所有梅森素数的列表:(我们注意到梅森神父的名字不在上面——这种素数已经由他的名字命名了,就把荣誉分给最后确认者吧。)

完美数的年代

位数

1 2 1 1——

2 3 1 2——

3 5 2 3——

4 7 3 4——

5 13 4 8 1456

6 17 6 10 1588

7 19 6 12 1588

8 31 10 19 1772

9 61 19 37 1883

10 89 27 54 1911

11 107 33 65 1914

12 127 39 77 1876

13 521 157 314 1952

14 607 183 366 1952

15 1279 386 770 1952

16 2203 664 1327 1952

17 2281 687 1373 1952

18 3217 969 1937 1957

19 4253 1281 2561 1961

20 4423 1332 2663 1961

21 9689 2917 5834 1963

22 9941 2993 5985 1963

23 11213 3376 6751 1963

24 19937 6002 12003 1971

25 21701 6533 13066 1978

26 23209 6987 13973 1979

27 44497 13395 26790 1979

28 86243 25962 51924 1982

29 110503 33265 66530 1988

30 132049 39751 79502 1983

31 216091 65050 130100 1985

32 756839 227832 455663 1992

33 859433 258716 517430 1994

34 1257787 378632 757263 1996

35 1398269 420921 841842 1996

36 2976221 895932 1791864 1997

37 3021377 909526 1819050 1998

??6972593 2098960 4197919 1999

是不是有无穷多个梅森素数呢?数学家们目前还无法回答这个问题。

寻找更大的素数

为什么要寻找梅森素数?为什么要打破已知最大素数的纪录?这有什么用处呢?

如果你所说的用处是指能够直接创造物质财富,那么我不得不告诉你——梅森素数没有什么用处,多知道一个非常大的素数似乎也没什么用处。即使我们知道了一个无比巨大的梅森素数,也不会使我们的钱包增加一分钱(嗨等一等!如果你只对钱感兴趣的话,也请不要立刻撇下我的文章。我其实是说,我上面说的话要排除我在这篇文章题目中提到的那十万美元的奖金——你的钱包也许会因此鼓起来的。所以请耐心一点)。

但是人类并不只需要物质财富。博物馆里的钻石有什么用场呢?为什么人类要收集它们?因为它们美丽而稀少。作为人类智慧的结晶,素数、梅森素数和与它密切相关的完美数是非常美丽的。它们的定义简单,却又如此神秘莫测,象欧几里德、笛卡儿、费尔马、莱布尼兹、欧拉这样的伟大数学家都因为它们的美丽而对它作过大量研究；大家也看到,两千多年来,经过无数代人的辛勤工作,我们一共只收集到38个梅森素数,它们是非常稀少的。对于数学家来说,搜集素数、梅森素数和完美数是和收集钻石一样富有乐趣的事情。

人类还需要荣耀——也许更胜于财富。在体育运动中,能够跑得更快一点,跳得更高一点,难道真的有实际物质方面的用途吗?不,我们喜欢接受挑战,我们希望能赢。打破一个体育世界记录,攀登珠穆朗玛峰,驾船横穿太平洋……,那是对人类体能极限的挑战；而寻找更大的素数,则是一项对人类智慧的挑战。当我们完成了一项前所未有的任务时,我们总会感到无比骄傲。1963年,当第23个梅森素数被找到时,发现它的美国伊利诺斯大学数学系是如此地骄傲,以致于把所有从系里发出的信件都敲上了“211213－1是个素数”的邮戳。

在欧拉证明M_31是素数以后,下一个最大素数的记录由兰德里(Landry)于1867年获得:M_59/179951＝3203431780337。这不是一个梅森素数。这个记录保持了九年。

1876年爱德华·卢卡斯使用了一个比费尔马和欧拉的方法更先进的手段,证明了M_127是一个素数。这个记录保持了七十五年。直到费里叶(Ferrier)于1951年使用一部手摇计算机证明了(2148＋1)/17是一个素数,它有41位数。

借助手摇计算机的方法要算作手工计算方法还是要算做计算机方法,大概是可以探讨的问题。不过技术的发展一下子把这种争论变得毫无必要。值得指出的是,在人类寻找大素数的旅途中,数学理论的改善要远远比具有强大坚韧的计算能力重要得多。卢卡斯的方法在1930年被勒梅(Lehmer)简化后,卢卡斯－勒梅测试成为现在寻找梅森素数的标准方法。(www.xing528.com)

(卢卡斯－勒梅测试:对于所有大于1的奇数p,M_p是素数当且仅当M_p整除S(p－1),其中S(n)由S(n＋1)＝S(n)2－2,S(1)＝4递归定义。这个测试尤其适合于计算机运算,因为除以M_p＝2p－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∗2216193－1,在1989年被发现。1996年发现的M_1257787是迄今为止最后一个由超级计算机发现的梅森素数,数学家使用了Cray T94。

然后,GIMPS的时代到来了。

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要使用这样的超级计算机,一天就需要支付大约二十万美元。而现在他们需要的费用,只不过是支持网站运行的费用,和总共几十万美元的奖金罢了。

价值五万美元的素数

2000年4月6日,住在美国密歇根州普利茅茨的那扬·哈吉拉特瓦拉(Nayan Hajratwala)先生得到了一笔五万美元的数学奖金,因为他找到了迄今为止已知的最大素数,这是一个梅森素数:

26972593－1。

这也是我们知道的第一个位数超过一百万位的素数。精确地讲,如果把这个素数写成我们熟悉的十进制形式的话,它共有两百零九万八千九百六十位数字,如果把它以这个形式写下来,大约需要150到200篇本文的篇幅。

可是哈吉拉特瓦拉先生并不是一个数学家,他甚至很可能对寻找素数的数学理论一无所知——虽然这使他赢得了这笔奖金。他所做的一切,就是从互联网上下载了一个程序。这个程序在他不使用他的奔腾II350型计算机时悄悄地运行。在经过111天的计算后,上面所说的这个素数被发现了。

素数的分类

素数从理论上来说只能分成两类,即偶素数和奇素数,由于历史和人为习惯的原因,人们又对素数进行了各种各样的分类,这些分类中最著名的有两种,一种就是前面提到过的梅森素数,另一种是叫做费马素数。其他的类型的素数不太被人们所熟悉,比如普罗斯素数。还有另外一种分类法既是按素数本身的形态来区分的,比如说回文素数,下表列出了最近发现的最大的十个回文素数:

742950290870000078092059247,

74295029087101017802059247,

742950290872020278092059247,

742950290873030378092059247,

742950290874040478092059247,

742950290875050578092059247,

742950290876060678092059247,

742950290877070778092059247,

742950290878080878092059247,

742950290879090978092059247

另一种非常重要的是神秘的素数对,或成为孪生素数,孪生素数是指如果p是素数且p＋2也是素数,则称p和p＋2为一对孪生素数,比如5,7；11,13等等.下表是目前所发现的最大的前二十个孪生素数:

素数类型

在对素数的长期研究中,有几种类型的素数特别受到重视,这里介绍两种素数的类型Rn与Mn。

是一个n位数,n位都是1。Rn如果是素数,就称为Rn型的素数,例如R2＝11就是Rn型的素数。显然,如果Rn是素数,n必定是素数。

这样的素数一共发现了四个,即R2,R19,R23,R317。从发现R23到发现R317,中间经历了50年的时间。R317,这个素数,是1978年初,由加拿大数学教授威廉斯证明的。他在检验R317不可能有任何别的素数因子时,是用计算机来检验的。现在研究数论,大量的计算都是用电子计算机来完成的。

目前,人们猜想下一个Rn型的素数是R1031。

凡是形状是2R－1的数记作Mn,叫做麦什涅数,如果是素数,就叫做麦什涅素数。例如M2＝3,M 3＝7,M5＝31等是麦什涅素数。

人们证明了:如果Mp是麦什涅素数,p一定是素数。但是,不能认为p是素数,Mp就是麦什涅素数。例如M11＝211－1＝2047＝23×89,就不是麦什涅素数。

1978年底,美国加利福尼亚大学的两个学生尼克尔和诺尔,利用电子计算机证明了M21701是素数。M2170＝221701－1,是当时能写出来、并且能加以证明的最大素数。

我国在报导这一素数时,曾有过这么一段故事:

1978年11月21日,我国有报纸刊登了:

“[法新社美国加州赫沃兹十一月十五日电]两位美国学生发现了最大的已知质数221701。”

报纸出版没几天,这家报纸的编辑部和很多科技报刊以及许多大学的数学系,就收到了大量的群众来信,内容主要是指出:

221701肯定是合数(2的倍数),怎么能是素数呢?

后来,有的报刊更正说,新发现的最大已知素数,应该是221701－1,报纸上把221701－1的“－1”都丢了。

紧接着,一些数学教师就围绕着这个数据,出了一些供青少年解答的有趣的数学题目。比如221701－1有多少位?头两位与末两位各是什么数?(答:有6533位；头两位是44,末两位是51。)

221701＋1是素数吗?你能不能证明:若2m＋1是素数,则m＝2n。

到1979年底为止,人们已知的最大素数是244497－1。

值得注意的是:数学家在判断具体的Rn、Mn和Fn是不是素数时,虽然一般都要借助于大型电子计算机,但是困难的研究工作,还得靠人来完成。

例如,有人已经证明了216384＋1(即F14＝2214＋1)是一个合数,可是无论用现有的什么样的计算机,也找不出它的任何一个因子来。因为人们还没有把这个问题,转化到计算机能帮得上忙的程度。

为什么1不是素数

全体自然数可以分为三类:

(1)只能被“1”和它本身整除的数叫素数,如:2、3、5、7、11……。

(2)除了“1”和它本身以外,还能被其他数整除的数叫合数,如:4、6、8、9……。

(3)“1”既不是素数也不是合数。

有人要问,“1”也只能被1和它本身整除,为什么不能算素数呢?而且“1”算作素数后,全体自然数分成素数和合数两类,岂不是更简单吗?

这要从分解素因数谈起。比如,1001能被哪些数整除,其实质是将1001分解素因数,由1001＝7×11×13,而且只有这一种分解结果,知道1001除了被1和它本身整除以外,还能被7、11、13整除。若把“1”也算作素数,那么1001分解素因数就会出现下面一些结果:

1001＝7×11×13

1001＝1×7×11×13

1001＝1×1×7×11×13

……

也就是说,分解式中可随便添上几个因数“1”。这样做,一方面对求1001的因数毫无必要,另一方面分解素因数结果不唯一,又增添了不必要的麻烦。因此“1”不算作素数。