梅森質數

梅森數是形如2ⁿ－1的數（n是正整數），記為${\textstyle M_{n}}$；如果梅森數是質數就稱梅森質數（英語：Mersenne prime）。

梅森預測表：n≤263

P : Mn是梅森質數 — : Mn是梅森合數 青色：顯示正確 粉紅色：顯示錯誤
n	2	3	5	7	11	13	17	19
Mn	P	P	P	P	—	P	P	P
n	23	29	31	37	41	43	47	53
Mn	—	—	P	—	—	—	—	—
n	59	61	67	71	73	79	83	89
Mn	—	P	—	—	—	—	—	P
n	97	101	103	107	109	113	127	131
Mn	—	—	—	P	—	—	P	—
n	137	139	149	151	157	163	167	173
Mn	—	—	—	—	—	—	—	—
n	179	181	191	193	197	199	211	223
Mn	—	—	—	—	—	—	—	—
n	227	229	233	239	241	251	257	263
Mn	—	—	—	—	—	—	—	—

梅森數是根據17世紀法國數學家馬蘭·梅森的名字命名，他列出了n≤257的梅森質數，不過他錯誤包括了不是梅森質數的M₆₇和M₂₅₇，而遺漏了M₆₁、M₈₉和M₁₀₇。

n為合數時，${\textstyle M_{n}}$一定為合數（當a整除b時，${\textstyle M_{a}}$一定整除${\textstyle M_{b}}$，反之亦然）。但n為質數時，${\textstyle M_{n}}$不一定皆為質數，如${\textstyle M_{2}=2^{2}-1=3}$和${\textstyle M_{3}=2^{3}-1=7}$是質數，但${\textstyle M_{11}=2^{11}-1=2047=23\times 89}$不是質數。

截至2024年10月已知52個梅森質數，最大的是2^136279841－1^[1]。從1997年至今，所有新的梅森質數都由網際網路梅森質數大搜索（GIMPS）分布式計算項目發現。

相關命題和定理

梅森數和梅森質數的性質

• ${\displaystyle M_{n}=\sum _{i=0}^{n}{n \choose i}-1=\sum _{i=0}^{n-1}2^{i}}$。

• 如果${\textstyle p\equiv 3{\pmod {4}}}$為質數。則${\displaystyle 2p+1}$是質數的充分必要條件是${\displaystyle 2p+1\mid M_{p}}$ ，因此對於這些質數${\displaystyle p}$（除了3），${\displaystyle M_{p}}$不可能會是質數，前幾個這樣的質數${\displaystyle p}$為11、23、83、131、179、191、239、251、359、419、431、443、491、659、683、719、743、911、1019、1031、1103、1223、1439、1451、1499、… （OEIS數列A002515）

• 拉馬努金－南哥爾方程式（Ramanujan–Nagell Equation）：${\displaystyle M_{p}=6+x^{2}}$。當${\displaystyle p}$為3、5和7時，${\displaystyle M_{p}}$為梅森質數，方程式有整數解；${\displaystyle p}$為合數4和15時，方程式亦有整數解；${\displaystyle p}$為其它自然數時，方程式沒有整數解。

• 如果${\displaystyle p}$是奇質數，任何能整除${\displaystyle 2^{p}-1}$的質數${\displaystyle q}$都一定是${\displaystyle 2p}$的倍數加${\displaystyle 1}$，如2¹¹ − 1 = 23 × 89, 其中23 = 1 + (2 × 11) 且 89 = 1 + 4 × (2 × 11)。

• 如果${\displaystyle p}$是奇質數，任何能整除${\displaystyle 2^{p}-1}$的質數${\displaystyle q}$都一定與${\textstyle \pm 1{\pmod {8}}}$同餘。

梅森數和梅森質數的關係

下面的命題關注什麼梅森數是梅森質數。

• 由${\displaystyle 2^{ab}-1=(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
  • 形如6k＋1的數有歐拉理論表明：若且唯若有數對（x，y）使M_q＝（2x）²＋3（3y）²，M_q是質數，其中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年代改進，因此得名。
  • 該方法基於循環數列（英語：Derrick Henry Lehmer）的計算，其原理是：

M_n為質數若且唯若M_n整除S_n-2（S₀＝4，S_k＝S²_k−1 − 2，k＞0），此數列為4、14、194、37634、1416317954、2005956546822746114、4023861667741036022825635656102100994、…（OEIS數列A003010）

與完全數的關係

• 梅森質數與偶完全數有一一對應的關係，稱為歐幾里得－歐拉定理。
  • 前4世紀，歐幾里得證明如果M是梅森質數，則${\textstyle {\frac {M(M+1)}{2}}}$是完全數。
  • 18世紀，歐拉證明所有偶完全數都有這種形式。

相關問題和猜想

• 梅森質數是否有無限個
• 梅森質數如何分布

尋找梅森質數

• 頭四個梅森質數M₂、M₃、M₅、M₇在古代已知。
• 第五個梅森質數M₁₃在1461年之前發現；
• M₁₇和M₁₉兩數隨後在1588年由Cataldi發現。
• 17世紀法國數學家馬蘭·梅森列出了他認為的冪小於等於257的梅森質數，其中錯誤包括了不是質數的M₆₇和M₂₅₇，遺漏了M₆₁、M₈₉和M₁₀₇。這也是「梅森質數」一名的由來。
• 一個多世紀後的1750年，才由歐拉證實M₃₁是第8個梅森質數。
• 下個發現的梅森質數是由盧卡斯在1876年證明的M₁₂₇；
• 1883年，Pervushin證實M₆₁。
• M₈₉和M₁₀₇在20世紀早期由Powers分別在1911年和1914年發現。
• 發明電子計算機改革了梅森質數的尋找過程。第一項成功例子是證明M₅₂₁，它由萊默指導，用拉斐爾·米切爾·羅賓遜教授編寫的軟體，利用坐落在洛杉磯加利福尼亞大學的數據分析協會的，屬於美國國家標準局的西部自動計算機（SWAC）於1952年1月30日晚上10:00獲得，並且在隨後不到兩小時發現下個梅森質數M₆₀₇。在隨後的幾個月裡，使用同樣的程序發現了另外三個梅森質數M₁₂₇₉、M₂₂₀₃和M₂₂₈₁。
• 質數P值增大，搜尋梅森質數MP的過程都艱辛無比，但各國科學家及業餘研究者仍樂此不疲，激烈競爭；1979年2月23日，當美國克雷研究公司的計算機專家史洛溫斯基和納爾遜宣布找到第26個梅森質數M₂₃₂₀₉時才知諾爾在兩星期前已得到這結果。
• 為此，史洛溫斯基潛心發憤，花了一個半月用CRAY－1型計算機找到新梅森質數M₄₄₄₉₇，這紀錄成了當時不少美國報紙的頭版新聞。

• 他之後乘勝前進，使用改進了的CRAY－XMP型計算機在1983年至1985年間找到3個梅森質數M₈₆₂₄₃、M₁₃₂₀₄₉和M₂₁₆₀₉₁，但未能確定M₈₆₂₄₃和M₂₁₆₀₉₁之間是否有異於M₁₃₂₀₄₉的梅森質數。而到了1988年，科爾魁特和韋爾什使用NEC－FX2型超高速並行計算機果然捉到「漏網之魚」M₁₁₀₅₀₃。

• 沉寂4年後，1992年3月25日，英國原子能技術權威機構哈威爾實驗室有研究小組宣布找到梅森質數M₇₅₆₈₃₉。

• 1994年1月14日，史洛溫斯基和蓋奇為其公司再次奪回發現「已知最大質數」的桂冠——M₈₅₉₄₃₃；而下個梅森質數M_1257787仍是他們的成果，用CRAY－794超級計算機在1996年找到。

• 史洛溫斯基發現7個梅森質數，獲美譽「質數大王」。

• 到2018年12月已知51個梅森質數；現在已知最大的質數是梅森質數M_82589933，像前幾個一樣都是由網際網路梅森質數大搜索（GIMPS）分布式計算項目發現。
• 2010年7月11日GIMPS確認M_2099萬6011是第40個梅森質數。^[2]
• 2011年12月1日GIMPS確認M_2403萬6583是第41個梅森質數。^[2]
• 2012年12月20日GIMPS確認M_2596萬4951是第42個梅森質數。^[2]
• 2013年1月25日GIMPS發現M_5788萬5161^[2]
• 2014年2月23日GIMPS確認M_3040萬2457是第43個梅森質數。^[2]
• 2014年11月8日GIMPS確認M_3258萬2657是第44個梅森質數。^[2]
• 2016年1月7日GIMPS發現M_7420萬7281^[2]
• 2018年1月3日GIMPS發現的M_7723萬2917有23249425位數^[3]。
• 2018年12月7日GIMPS的M_8258萬9933有24862048位數^[4]。
• 2024年10月21日GIMPS的M_{1億3627萬9841}有41024320位數^[1]。

梅森質數列表

  古代知道的梅森質數

  以試除法發現的梅森質數

  梅森遺漏的梅森質數

  GIMPS發現的梅森質數

  拉斐爾·米切爾·羅賓遜發現的梅森質數

  亞歷山大·赫維茲發現的梅森質數

  Donald B. Gillies發現的梅森質數

  Walt Colquitt和Luke Welsh發現的梅森質數

下表列出所有已知的梅森質數： A000668

序	n	Mn	Mn的位數	發現日期	發現者	算法
1	2	3	1	公元前5世紀	古希臘數學家
2	3	7	1	公元前5世紀	古希臘數學家
3	5	31	2	公元前3世紀	古希臘數學家
4	7	127	3	公元前3世紀	古希臘數學家
5	13	8191	4	1456年	無名氏	試除法
6	17	131071	6	1588年	彼得羅·卡達迪	試除法
7	19	524287	6	1588年	彼得羅·卡達迪	試除法
8	31	2147483647	10	1772年	萊昂哈德·歐拉	最佳化的試除法
9	61	2305843009213693951	19	1883年	伊萬·波佛辛	盧卡斯數列
10	89	618970019642690137449562111	27	1911年	拉爾夫·歐內斯特·鮑爾斯	盧卡斯數列
11	107	162259276829213363391578010288127	33	1914年	拉爾夫·歐內斯特·鮑爾斯	盧卡斯數列
12	127	170141183460469231731687303715884105727	39	1876年	愛德華·盧卡斯	盧卡斯數列
13	521	686479766013…291115057151	157	1952年1月30日	拉斐爾·米切爾·羅賓遜	盧卡斯－萊默檢定法
14	607	531137992816…219031728127	183	1952年1月30日	拉斐爾·米切爾·羅賓遜	盧卡斯－萊默檢定法
15	1279	104079321946…703168729087	386	1952年6月25日	拉斐爾·米切爾·羅賓遜	盧卡斯－萊默檢定法
16	2203	147597991521…686697771007	664	1952年10月7日	拉斐爾·米切爾·羅賓遜	盧卡斯－萊默檢定法
17	2281	446087557183…418132836351	687	1952年10月9日	拉斐爾·米切爾·羅賓遜	盧卡斯－萊默檢定法
18	3217	259117086013…362909315071	969	1957年9月8日	Hans Riesel	盧卡斯－萊默檢定法
19	4253	190797007524…815350484991	1281	1961年11月3日	亞歷山大·赫維茲	盧卡斯－萊默檢定法
20	4423	285542542228…902608580607	1332	1961年11月3日	亞歷山大·赫維茲	盧卡斯－萊默檢定法
21	9689	478220278805…826225754111	2917	1963年5月11日	Donald B. Gillies	盧卡斯－萊默檢定法
22	9941	346088282490…883789463551	2993	1963年5月16日	Donald B. Gillies	盧卡斯－萊默檢定法
23	1萬1213	281411201369…087696392191	3376	1963年6月2日	Donald B. Gillies	盧卡斯－萊默檢定法
24	1萬9937	431542479738…030968041471	6002	1971年3月4日	布萊恩特·塔克曼	盧卡斯－萊默檢定法
25	2萬1701	448679166119…353511882751	6533	1978年10月30日	Landon Curt Noll & Laura Nickel	盧卡斯－萊默檢定法
26	2萬3209	402874115778…523779264511	6987	1979年2月9日	Landon Curt Noll	盧卡斯－萊默檢定法
27	4萬4497	854509824303…961011228671	1萬3395	1979年4月8日	Harry Nelson & David Slowinski	盧卡斯－萊默檢定法
28	8萬6243	536927995502…209433438207	2萬5962	1982年9月25日	David Slowinski	盧卡斯－萊默檢定法
29	11萬0503	521928313341…083465515007	3萬3265	1988年1月28日	Walt Colquitt & Luke Welsh	盧卡斯－萊默檢定法
30	13萬2049	512740276269…455730061311	3萬9751	1983年9月20日	David Slowinski	盧卡斯－萊默檢定法
31	21萬6091	746093103064…103815528447	6萬5050	1985年9月6日	David Slowinski	盧卡斯－萊默檢定法
32	75萬6839	174135906820…328544677887	22萬7832	1992年2月19日	David Slowinski & Paul Gage	盧卡斯－萊默檢定法
33	85萬9433	129498125604…243500142591	25萬8716	1994年1月10日	David Slowinski & Paul Gage	盧卡斯－萊默檢定法
34	125萬7787	412245773621…976089366527	37萬8632	1996年9月3日	David Slowinski & Paul Gage	盧卡斯－萊默檢定法
35	139萬8269	814717564412…868451315711	42萬0921	1996年11月13日	GIMPS／Joel Armengaud	盧卡斯－萊默檢定法
36	297萬6221	623340076248…743729201151	89萬5932	1997年8月24日	GIMPS／Gordon Spence	盧卡斯－萊默檢定法
37	302萬1377	127411683030…973024694271	90萬9526	1998年1月27日	GIMPS／Roland Clarkson	盧卡斯－萊默檢定法
38	697萬2593	437075744127…142924193791	209萬8960	1999年6月1日	GIMPS／Nayan Hajratwala	盧卡斯－萊默檢定法
39	1346萬6917	924947738006…470256259071	405萬3946	2001年11月14日	GIMPS／Michael Cameron	盧卡斯－萊默檢定法
40	2099萬6011	125976895450…762855682047	632萬0430	2003年11月17日	GIMPS／Michael Shafer	盧卡斯－萊默檢定法
41	2403萬6583	299410429404…882733969407	723萬5733	2004年5月15日	GIMPS／Josh Findley	盧卡斯－萊默檢定法
42	2596萬4951	122164630061…280577077247	781萬6230	2005年2月18日	GIMPS／Martin Nowak	盧卡斯－萊默檢定法
43	3040萬2457	315416475618…411652943871	915萬2052	2005年12月15日	GIMPS／Curtis Cooper及Steven Boone	盧卡斯－萊默檢定法
44	3258萬2657	124575026015…154053967871	980萬8358	2006年9月4日	GIMPS／Curtis Cooper及Steven Boone	盧卡斯－萊默檢定法
45	3715萬6667	202254406890…022308220927	1118萬5272	2008年9月6日	GIMPS／Hans-Michael Elvenich	盧卡斯－萊默檢定法
46	4264萬3801	169873516452…765562314751	1283萬7064	2009年4月12日[註 1]	GIMPS／Odd M. Strindmo	盧卡斯－萊默檢定法
47	4311萬2609	316470269330…166697152511	1297萬8189	2008年8月23日	GIMPS／Edson Smith	盧卡斯－萊默檢定法
48	5788萬5161	581887266232…071724285951	1742萬5170	2013年1月25日	GIMPS／Curtis Cooper	盧卡斯－萊默檢定法
49*	7420萬7281	300376418084…391086436351	2233萬8618	2015年9月17日[註 2]	GIMPS／Curtis Cooper	盧卡斯－萊默檢定法
50*	7723萬2917	467333183359…069762179071	2324萬9425	2017年12月26日	GIMPS／Jon Pace	盧卡斯－萊默檢定法
51*	8258萬9933	148894445742…325217902591	2486萬2048	2018年12月7日	GIMPS／Patrick Laroche	盧卡斯－萊默檢定法
52	1億3627萬9841	881694327503…219486871551	4102萬4320	2024年10月21日	GIMPS／Luke Durant	盧卡斯－萊默檢定法

註：現在還不知道第48個梅森質數（M_57885161）和第51個（M_82589933）間是否還有未知梅森質數，其序號用^*標出，如有會通知遞補。

1. 2009年4月12日首次有機器發現M_4264萬3801，但直到6月4日才有人注意到，兩者皆可視為發現日期。
2. 2015年9月17日首次有機器發現M_7420萬7281，但直到2016年1月7日才有人注意到，兩者皆可視為發現日期；GIMPS以後者為正式日期。

外部連結

• （英文）Great Internet Mersenne Prime Search （頁面存檔備份，存於網際網路檔案館） GIMPS計劃
• （英文）Mersenne Primes: History, Theorems and Lists （頁面存檔備份，存於網際網路檔案館） 梅森質數：歷史，定理，以及梅森質數列表

參考

1. Mersenne Prime Number discovery - 2^136279841-1 is Prime!. www.mersenne.org. [2024-10-21].
2. GIMPS Milestones. [2012-03-03]. （原始內容存檔於2016-09-03）.
3. GIMPS Project Discovers Largest Known Prime Number: 2^77,232,917-1. Mersenne Research, Inc. 2018年1月3日 [2018年1月14日]. （原始內容存檔於2018年1月3日）.
4. Mersenne Prime Discovery - 2^82589933-1 is Prime!. www.mersenne.org. [2018-12-24]. （原始內容存檔於2018-12-22）.