最大的素数 - 51windows.Net
51windows.Net > 文摘 > 知识 > 最大的素数

最大的素数

  

【最大的素数】
  这是到目前为止人类所发现的最大素数,它是由纳杨,沃特曼,库洛夫斯基三人在1999年6月1日发现的,这是一个梅森素数,有2098960位数字,是用Primes95这个软件找到的,该软件由沃特曼和库洛夫斯基共同编写的,是一个分布在因特网上的应用软件,现在已经有大约6万人在共同使用这个软件来寻找这种被称为梅森素数的类型的素数.纳扬是这6万人中之一,在1998年1月28日,美国加利福尼亚大学的大学生克拉克也是利用这个软件发现了第37个梅森素数,我现在也参加到这个行列中,现在已经检验完三个指数了,结果都不是素数,每检验一个指数,大约需要60天,当然指数越大时间越长.这个软件的客户端是一个后台运行的程序,只要你一开机,它就自动运行在后台,对于你的正常工作毫不影响.现在这个软件已经到了第9版.有兴趣的可以到如下站点去下载:ftp://entropia.com/gimps/prime95.zip

  所谓梅森素数,是以17世纪法国修道士M.梅森的名字命名的.梅森在1644年出版的著作<<物理数学随感>>的序言中宣称,对于n=2,3,5,7,13,17,19,31,67,127,257,数Mn=2n-1是素数,而对于其他所有小于257的数n,Mn是合数.但是,这里出现了5个错误,M67,M257不是素数,而M61,M89,M107是素数.显然,要使Mn是素数,n本身必须是素数,但是反过来,n是素数,Mn却不一定是素数,例如虽然11是素数,可是M11=2047=23X89是合数.由费马小定理知道,若p为素数,而a不是p的倍数,则ap-1-1恒是p的倍数.例如26-1是7的倍数.但是也有可能存在比p-1更小的数b就能使得2b-1是p的倍数了,例如23-1就能够被7整除了.很容易证明p-1是b的倍数,即p=rb+1.表面上看来对于寻找Mp的因子费马小定理一点儿也帮不上忙,但是已经证明,对于底数2来说,指数p-1可除以2而不影响该数用p去除时的可除性,如p在除以8时余数为1或为7的话,换言之,即其形状为8r+1或8r+7.从而可以推出:

               2[(8r+1)-1]/2-1与2[(8r+7)-1]/2-1

  可以被p整除.在前一种情况下,说明24r-1可以被8r+1形式的素数整除,但由于指数4r是偶数,所以这种数不属于梅森数的类型.对于后一种情况,我们的结论是24r+3-1可以被形如8r+7的素数整除.   所以当4r+3和8r+7都是素数时,8r+7必能整除相应的梅森数.

  能满足上述条件的r与n的数值,可以参看下表:

r 4r+3 8r+7 24r+3-1
2 11 23 211-1
5 23 47 223-1
20 83 167 283-1
32 131 263 2131-1
44 179 359 2179-1
47 191 383 2191-1
59 239 479 2239-1
62 251 503 2251-1

  当Mp不是素数时,那么肯定另外存在一个素数q>2,使得q-1=sp,而使2sp-1是q的倍数,从而2p-1也是q的倍数,由于q-1是偶数,而p是奇数,所以s必是偶数,令s=2k,则有
q=2kp+1,这就是说,形如2p-1(p是素数)的数具有形如q=2kp+1的因子.利用这一点可以求出梅森数的因子.例如已经知道211-1是合数,它的因子必然是形如2k*11+1=22k+1的形式,k=1时,得到23,而23果然能够整除211-1(211-1=2047=23*89).

   已经研究出一些非常巧妙的办法来大大地削减试探的工作量,1876年,法国数学家E.V.卢卡发明了一种测试法检查梅森数的素性.1930年,美国数学家D.H.莱默对此进行了改进,使之非常有效,实用.方法如下:

  定义数列:u0=4,uk+1=uk2-2 mod Mn  (k=0,1,2...n)

  若uk-2=0 mod Mn 则Mn是素数,否则Mn不是素数.有关这个定理的证明可以到素数检验法中找到它.

  这个检验法是如此简单,以至于两位对此定理还不十分理解的高中生L.尼科尔和C.诺尔经过3年的努力,在1978年利用CYBER174型计算机发现了有6533位数的梅森素数M21701.一年以后,诺尔又一次改写了这个记录,找到了有6987位数的梅森素数M23209.

  现在寻找很大的梅森素数时,已经完全依赖于计算机了,可以想象,离开了计算机,我们人类将会落入一种怎样的地步.当D.H.莱默博士这位曾经在梅森素数上花费了许多时光的老学者,亲眼看到了计算机在短短的48秒钟内做完了他20年前花费了700多小时才完成的艰辛劳动,最后证明2257-1是一个合数时,他是多么地感慨万端哪.

  时至今日,人类只找到38个梅森素数.前18个梅森素数是n=2,3,5,7,13,17,19,31,61,89,107,127
,521,607,1279,2203,2281,3217时的Mn=2n-1.下表列出了从1961年以来所发现的全部梅森素数.摘自http://www.utm.edu/research/primes/

序号 素数 位数 发现人 时间 注释
42 225964951-1 7816230 2005 Mersenne 42
41 224036583-1 7235733 John Findley 2004 Mersenne 41
40 220996011-1 6320430 Michael Shafer 2003 Mersenne 40
39 213466917-1 4053946 Michael Cameron 2001 Mersenne 39
38 26972593-1 2098960 Nayan, Woltman, Kurowski 1999 Mersenne 38
37 23021377-1 909526 Clarkson, Woltman, Kurowski 1998 Mersenne 37
36 22976221-1 895932 Spence, Woltman 1997 Mersenne 36
35 21398269-1 420921 Armengaud, Woltman 1996 Mersenne 35
34 21257787-1 378632 Slowinski & Gage 1996 Mersenne 34
33 2859433-1 258716 Slowinski & Gage 1994 Mersenne 33 
32 2756839-1 227832 Slowinski & Gage 1992 Mersenne 32
31 2216091-1 65050 David Slowinski 1985 Mersenne 31 
30 2132049-1 39751 David Slowinski 1983 Mersenne 30 
29 2110503-1 33265 Welsh & Colquitt 1988 Mersenne 29
28 286243-1 25962 David Slowinski 1982 Mersenne 28
27 244497-1 13395 Slowinski & Nelson 1979 Mersenne 27 
26 223209-1 6987 L. Curt Noll 1979 Mersenne 26 
25 221701-1 6533 Nickel & Noll 1978 Mersenne 25
24 219937-1 6002 Bryant Tuckerman 1971 Mersenne 24
23 211213-1 3376 Donald B. Gillies 1963 Mersenne 23
22 29941-1 2993 Donald B. Gillies 1963 Mersenne 22
21 29689-1 2917 Donald B. Gillies 1963 Mersenne 21
20 24423-1 1332 Alexander Hurwitz 1961 Mersenne 20
19 24253-1 1281 Alexander Hurwitz 1961 Mersenne 19
最新资料http://primes.utm.edu/largest.html





网站推荐:
虎的笑话 虎的成语 虎的歇后语
在线小游戏 成语排行榜 歇后语排行榜 中华五千年 文革图片


转载本站内容,请务必保留原作者信息。
本站提供的内容部分是在网上搜集,如果侵犯了您的版权,请告之,我们会删除内容或加上您的信息。(网站留言站内搜索)