梅森素数

维基百科，自由的百科全书

[编辑] 定义

梅森数是指形如2ⁿ − 1的数，记为M_n；如果一个梅森数是素数那幺它称为梅森素数。

梅森数是根据17世纪法国数学家马兰·梅森的名字命名的，他列出了n < 257的梅森素数，不过他错误地包括了不是素数的M₆₇ 和M₂₅₇，而遗漏了M₆₁、M₈₉ 和M₁₀₇。

[编辑] 例

M₂ = 2² − 1 = 3、M₃ = 2³ − 1 = 7 是素数。
M₄ = 2⁴ − 1 = 15 不是素数。

[编辑] 相关命题和定理

[编辑] 梅森数和梅森素数的性质

$M_n = \sum_{i=0}^{n} {n \choose i} - 1$ 。

q ≡ 3 mod 4 为素数。则2q+1也是素数当且仅当2q+1 整除M_q。

拉馬努金给出：方程M_q = 6+x²当q为3、5和7时有三个解；q为合数时有2个解。

[编辑] 梅森数和梅森素数的关系

下面的命题关注什幺样的梅森数是梅森素数。

由 $2^{ab1=(2^a-1)\times\sum_{i=0}^{b-1}2^{ia}$ }-知：q是素数是M_q是素数的必要条件。但这不是充分的。M₁₁ = 2¹¹ − 1 = 23 × 89 是个反例。
对M_q（q是素数）有：
- 若a是M_q的因数，则a有如下性质：
  - a ≡ 1 mod 2q
  - a ≡ ±1 mod 8
- 欧拉的一个关于形如1+6k的数的理论表明：M_q是素数当且仅当存在数对(x,y)使得 M_q _{= (2x)² + 3(3y)²，其中q ≥ 5。}
- _{最近，Bas jansen 研究了等式M_q = x² + dy²（0≤d≤48），得出了一个对于d=3情况下的新的证明方法。}
- Reix 发现q > 3时，M_q可以写成：M_q = (8x)² - (3qy)² = (1+Sq)² - (Dq)²。显然，若存在一个数对(x,y)，那幺M_q是素数。

[编辑] 梅森数的素性检验

卢卡斯-莱默检验法是现在已知的检测梅森数素性的最好的方法。
- 该方法由爱德华·卢卡斯于1878年发现，并由莱默1930年代作了改进，因此得名。
- 该方法基于循环数列的计算，其原理是：

M_n为素数当且仅当M_n整除S_n-2（S₀=4，S_k = S_{k − 1}² − 2，k > 0）。

[编辑] 与完全数的关系

梅森素数与偶完全数有一一对应的关系。
- 前4世纪，欧几里德(Euclid)证明如果M是梅森素数，那幺M(M+1)/2是完全数。
- 18世纪，欧拉(Euler)证明所有的偶完全数都有这种形式。

[编辑] 相关问题和猜想

是否有无穷多个梅森素数.

[编辑] 寻找梅森素数

头四个梅森素数M₂、M₃、M₅、M₇在古代就已经知道。
第五个梅森素数M₁₃在1461年之前被发现；
随后的两个（M₁₇ 和M₁₉）在1588年由Cataldi发现。
一个多世纪后的1750年，才由欧拉证实M₃₁ 是第8个梅森素数。
下一个被发现的梅森素数是由卢卡斯在1876年证明的M₁₂₇；
1883年，Pervushin证实M₆₁。
M₈₉和M₁₀₇是在20世纪早期由 Powers分别在1911年和1914年发现的。
17世纪法国数学家马兰·梅森列出了他认为的幂小于257的梅森素数，其中错误地包括了不是素数的M₆₇ 和M₂₅₇，遗漏了M₆₁、M₈₉ 和M₁₀₇。
电子计算机的发明革命化的改进了梅森素数的寻找。第一个成功的例子是M₅₂₁的证明，它是在莱默指导下，使用R.M. Robinson教授编写的软件，利用坐落在洛杉矶加利福尼亚大学的数据分析协会的，属于美国国家标准局的西部自动计算机（SWAC）于1952年 1月30日晚上10:00获得。并且在随后不到两小时，下一个梅森素数M₆₀₇被发现。在随后的几个月里，使用同样的程序发现了另外三个梅森素数M₁₂₇₉、M₂₂₀₃和M₂₂₈₁。
到2006年9月，我们知道了44个梅森素数；现在已知最大的素数是梅森素数M_32,582,657。像前几个一样，都是由因特网梅森素数大搜索分布式计算项目发现的。

[编辑] 梅森素数列表

下面表中列出了所有已知的梅森素数：（OEIS中的数列A000668）

#	n	M_n	M_n的位数	发现日期	发现者
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
24	19,937	431542479…968041471	6,002	1971年 3月4日	Tuckerman
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日	GIMPS / Curtis Cooper及Steven Boone
44^*	32,582,657	124575026…053967871	9,808,358	2006年 9月4日	GIMPS / Curtis Cooper及Steven Boone