梅森素数

1. 素数

大于1的自然数,只能被1和自身整除,称之为素数。素数也称质数。大于1的自然数若非素数,则称之为合数。

素数只有1和自身两个正因数。例如,2的正因数只有1和2;4的正因数除了1和4外,还有2。所以2是素数,4是合数。

算术基本定理:任何大于1的自然数都可以表示成多个素数的乘积。该定理确立了素数在数论里的核心地位。为了确保定理的唯一性,1被定义为不是素数,因为任意多个1相乘结果只为1,因式分解中就可以有任意多个1,如3、1×3、1×1×3都是3的因数分解。

2. 梅森素数

公元前300多年,古希腊数学家欧几里得开创了研究形如2^p-1素数的先河。他在名著《几何原本》第九章中论述完全数时指出,当2^p-1为素数时,2^(p-1) × (2^p-1)是完全数。即完全数恰好等于除了它本身之外的因数之和。例如6的因数为l、2、3、6,除了6本身这个因数之外,其他因数之和1+2+3等于它本身6。前5个完全数是6、28、496、8128、33550336。

1644年,法国数学家梅森在欧几里得等前人有关研究的基础上对2^p-1作了大量的计算,在《物理数学随感》一书中断言,在p不大于257的素数中,当p = 2、3、5、7、13、17、19、31、67、127、257 时,2^p-1是素数,其它都是合数。其中,前面的7个数(2、3、5、7、13、17、19)已被前人所证实,而后面的4个数(31、67、127、257)为梅森自己的推断。事实上梅森的断言错误地包括了67和257,遗漏了61、89和107。由于梅森的系统研究,数学界把形如2^p-1的素数称为梅森素数。

Mp=2^p-1

当p为合数时,Mp一定为合数;但当p为素数时,Mp不一定为素数。例如,M2=2^2-1=3、M3=2^3-1=7是素数,但M11=2^11-1=2047却不是素数:

1000以内的168个素数中,只有4个梅森素数。它珍奇而迷人,引起了数学家和爱好者的极大兴趣,纷纷加入寻找新素数的征程。下表列出了1996年10月前已知的前34个梅森素数:

p Mp 位数 发现日期 发现者
1 2 3 1 -500 希腊数学家
2 3 7 1 -500 希腊数学家
3 5 31 2 -300 希腊数学家
4 7 127 3 -300 希腊数学家
5 13 8191 4 1456 (无记录)
6 17 131071 6 1588 Pietro Cataldi
7 19 524287 6 1588 Pietro Cataldi
8 31 2147483647 10 1772 Leonhard Euler
9 61 2305843009213693951 19 1883 Ivan M. Pervushin
10 89 6189700196…7449562111 27 1911 Ralph E. Powers
11 107 1622592768…8010288127 33 1914 Ralph E. Powers
12 127 1701411834…5884105727 39 1876 Édouard Lucas
13 521 6864797660…1115057151 157 1952-1-30 Raphael M. Robinson
14 607 5311379928…9031728127 183 1952-1-30 Raphael M. Robinson
15 1,279 1040793219…3168729087 386 1952-6-25 Raphael M. Robinson
16 2,203 1475979915…6697771007 664 1952-10-7 Raphael M. Robinson
17 2,281 4460875571…8132836351 687 1952-10-9 Raphael M. Robinson
18 3,217 2591170860…2909315071 969 1957-9-8 Hans Riesel
19 4,253 1907970075…5350484991 1,281 1961-11-3 Alexander Hurwitz
20 4,423 2855425422…2608580607 1,332 1961-11-3 Alexander Hurwitz
21 9,689 4782202788…6225754111 2,917 1963-5-11 Donald B. Gillies
22 9,941 3460882824…3789463551 2,993 1963-5-16 Donald B. Gillies
23 11,213 2814112013…7696392191 3,376 1963-6-2 Donald B. Gillies
24 19,937 4315424797…0968041471 6,002 1971-3-4 Bryant Tuckerman
25 21,701 4486791661…3511882751 6,533 1978-10-30 Landon Curt Noll
Laura Nickel
26 23,209 4028741157…3779264511 6,987 1979-2-9 Landon Curt Noll
27 44,497 8545098243…1011228671 13,395 1979-4-8 Harry Nelson
David Slowinski
28 86,243 5369279955…9433438207 25,962 1982-9-25 David Slowinski
29 110,503 5219283133…3465515007 33,265 1988-1-28 Walt Colquitt
Luke Welsh
30 132,049 5127402762…5730061311 39,751 1983-9-20 David Slowinski
31 216,091 7460931030…3815528447 65,050 1985-9-6 David Slowinski
32 756,839 1741359068…8544677887 227,832 1992-2-19 David Slowinski
Paul Gage
33 859,433 1294981256…3500142591 258,716 1994-1-10 David Slowinski
Paul Gage
34 1,257,787 4122457736…6089366527 378,632 1996-9-3 David Slowinski
Paul Gage

3. 互联网梅森素数大搜索

1996年,George Woltman创立互联网梅森素数大搜索(Great Internet Mersenne Prime Search, GIMPS)组织,征召志愿者的计算机寻找梅森素数。这是世界上第一个基于互联网的分布式计算项目。

如果你感兴趣,可以下载程序参与搜索下一个梅森素数。如果大海捞针成功,可以获得3000美元现金奖励。如果你还好奇,可以下载源代码(版本29.4b7,包含Windows、Linux、FreeBSD和MacOS平台)。

截止2018年12月7日,GIMPS发现了该项目第17个梅森素数,即已知的第51个梅森素数。

发现日期 发现者 梅森素数 总序号
1 1996-11-13 Joel Armengaud 2^1,398,269-1 35
2 1997-8-24 Gordon Spence 2^2,976,221-1 36
3 1998-1-27 Roland Clarkson 2^3,021,377-1 37
4 1999-6-1 Nayan Hajratwala 2^6,972,593-1 38
5 2001-11-14 Michael Cameron 2^13,466,917-1 39
6 2003-11-17 Michael Shafer 2^20,996,011-1 40
7 2004-5-15 Josh Findley 2^24,036,583-1 41
8 2005-2-18 Dr. Martin Nowak 2^25,964,951-1 42
9 2005-12-15 Curtis Cooper, Steven Boone 2^30,402,457-1 43
10 2006-9-4 Curtis Cooper, Steven Boone 2^32,582,657-1 44
11 2008-9-6 Hans-Michael Elvenich 2^37,156,667-1 45
12 2009-6-4 Odd Magnar Strindmo 2^42,643,801-1 46
13 2008-8-23 Edson Smith 2^43,112,609-1 47
14 2013-1-25 Curtis Cooper 2^57,885,161-1 48
15 2016-1-7 Curtis Cooper 2^74,207,281-1 49
16 2017-12-26 Jonathan Pace 2^77,232,917-1 50
17 2018-12-7 Patrick Laroche 2^82,589,933-1 51