梅森质数

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

梅森數是根據 17 世紀法國數學家馬蘭・梅森（Marin Mersenne）的名字命名，他列出了 _n_≤257 的梅森質數，不過他錯誤包括了不是梅森質數的 _M_67 和 _M_257，而遺漏了 _M_61、_M_89 和 _M_107。

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

截至 2018 年 12 月已知 51 個梅森質數，最大的是 282589933－1。從 1997 年至今，所有新的梅森質數都由網際網路梅森質數大搜索（GIMPS）分布式計算項目發現。

## 相關命題和定理

### 梅森數和梅森質數的性質

 * $M_{n}=\sum _{i=0}^{n}{n \choose i}-1=\sum _{i=0}^{n-1}2^{i}$ 。
* _q_≡3mod4 為質數。則 **2_q_＋1 是質數**的充分必要條件是 **2_q_＋1 整除 _Mq_** ，因此對於這些質數 _q_（除了 3），_Mq_ 不可能會是質數，前幾個這樣的質數 _q_ 為 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）：_Mq_＝6＋_x_2。當 _q_ 為 3、5 和 7 時，_Mq_ 為梅森質數，方程式有整數解；_q_ 為合數 4 和 15 時，方程式亦有整數解；_q_ 為其它自然數時，方程式沒有整數解。
* 如果 _p_ 是奇質數，任何能整除 2p − 1 的質數 _q_ 都一定是 2_p_ 的倍數加 _1_，如 211 − 1＝23×89，而 23＝1＋2×11，89＝1＋8×11。
* 如果 _p_ 是奇質數，任何能整除 2p − 1 的質數 _q_ 都一定與 $\pm 1{\pmod {8}}$ 同餘。

### 梅森數和梅森質數的關係

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

* 由 $2^{ab}-1=(2^{a}-1)\times \sum _{i=0}^{b-1}2^{ia}$ 知：「_q_ 是質數」是「_Mq_ 是質數」的必要條件，但不是充分條件。_M_11＝211 − 1＝23×89 是最小的反例。
* 對 _Mq_（q 是質數）有：
  * 若 _a_ 是 _Mq_ 的因數，則 _a_ 有如下性質：
    * _a_ ≡ 1 mod 2_q_
    * _a_ ≡ ±1 mod 8
  * 形如 6_k_＋1 的數有歐拉理論表明：若且唯若有數對（_x_，_y_）使 _Mq_＝（2_x_）2＋3（3_y_）2，_Mq_ 是質數，其中 _q_≥5。
  * 最近，Bas jansen 研究了等式 _Mq_＝_x_2＋_dy_2（0≤_d_≤48），得出了 _d_＝3 時的新證明方法。
  * Reix 發現 _q_＞3 時，_Mq_ 可寫成 _Mq_＝（8_x_）2－（3_qy_）2＝（1＋_Sq_）2－（_Dq_）2；顯然，若有數對（_x_，_y_），_Mq_ 就是質數。

### 檢定梅森質數

* 盧卡斯－萊默檢定法是現在已知的檢測梅森數質數的最好的方法。
  * 該方法由愛德華・盧卡斯於 1878 年發現，並由德里克・亨利・萊默於 1930 年代改進，因此得名。
  * 該方法基於循環數列的計算，其原理是：

　
: _Mn_ 為質數若且唯若 _Mn_ 整除 _S_n-2（_S_0＝4，_S_k＝_S_2k−1 − 2，_k_＞0），此數列為 4、14、194、37634、1416317954、2005956546822746114、4023861667741036022825635656102100994、…（OEIS 數列 A003010）

### 與完全數的關係

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

## 相關問題和猜想

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

## 尋找梅森質數

* 頭四個梅森質數 _M_2、_M_3、_M_5、_M_7 在古代已知。
* 第五個梅森質數 _M_13 在 1461 年之前發現；
* _M_17 和 _M_19 兩數隨後在 1588 年由 Cataldi 發現。
* 17 世紀法國數學家馬蘭・梅森列出了他認為的冪小於等於 257 的梅森質數，其中錯誤包括了不是質數的 _M_67 和 _M_257，遺漏了 _M_61、_M_89 和 _M_107。這也是「梅森質數」一名的由來。
* 一個多世紀後的 1750 年，才由歐拉證實 _M_31 是第 8 個梅森質數。
* 下個發現的梅森質數是由盧卡斯在 1876 年證明的 _M_127；
* 1883 年，Pervushin 證實 _M_61。
* _M_89 和 _M_107 在 20 世紀早期由 Powers 分別在 1911 年和 1914 年發現。
* 發明電子計算機改革了梅森質數的尋找過程。第一項成功例子是證明 _M_521，它由萊默指導，用拉斐爾・米切爾・羅賓遜教授編寫的軟體，利用坐落在洛杉磯加利福尼亞大學的數據分析協會的，屬於美國國家標準局的西部自動計算機（SWAC）於 1952 年 1 月 30 日晚上 10:00 獲得，並且在隨後不到兩小時發現下個梅森質數 _M_607。在隨後的幾個月裡，使用同樣的程序發現了另外三個梅森質數 _M_1279、_M_2203 和 _M_2281。
* 質數 P 值增大，搜尋梅森質數 MP 的過程都艱辛無比，但各國科學家及業餘研究者仍樂此不疲，激烈競爭；1979 年 2 月 23 日，當美國克雷研究公司的計算機專家史洛溫斯基和納爾遜宣布找到第 26 個梅森質數 _M_23209 時才知諾爾在兩星期前已得到這結果。
* 為此，史洛溫斯基潛心發憤，花了一個半月用 CRAY－1 型計算機找到新梅森質數 _M_44497，這紀錄成了當時不少美國報紙的頭版新聞。
* 他之後乘勝前進，使用改進了的 CRAY－XMP 型計算機在 1983 年至 1985 年間找到 3 個梅森質數 _M_86243、_M_132049 和 _M_216091，但未能確定 _M_86243 和 _M_216091 之間是否有異於 _M_132049 的梅森質數。而到了 1988 年，科爾魁特和韋爾什使用 NEC－FX2 型超高速並行計算機果然捉到「漏網之魚」_M_110503。
* 沉寂 4 年後，1992 年 3 月 25 日，英國原子能技術權威機構哈威爾實驗室有研究小組宣布找到梅森質數 _M_756839。
* 1994 年 1 月 14 日，史洛溫斯基和蓋奇為其公司再次奪回發現「已知最大質數」的桂冠 ——_M_859433；而下個梅森質數 _M_1257787 仍是他們的成果，用 CRAY－794 超級計算機在 1996 年找到。
* 史洛溫斯基發現 7 個梅森質數，獲美譽「質數大王」。
* 到 2018 年 12 月已知 51 個梅森質數；現在已知最大的質數是梅森質數 _M_82589933，像前幾個一樣都是由_網際網路梅森質數大搜索_（GIMPS）分布式計算項目發現。
* 2010 年 7 月 11 日 GIMPS 確認 _M_2099 萬 6011 是第 40 個梅森質數。
* 2011 年 12 月 1 日 GIMPS 確認 _M_2403 萬 6583 是第 41 個梅森質數。
* 2012 年 12 月 20 日 GIMPS 確認 _M_2596 萬 4951 是第 42 個梅森質數。
* 2013 年 1 月 25 日 GIMPS 發現 _M_5788 萬 5161
* 2014 年 2 月 23 日 GIMPS 確認 _M_3040 萬 2457 是第 43 個梅森質數。
* 2014 年 11 月 8 日 GIMPS 確認 _M_3258 萬 2657 是第 44 個梅森質數。
* 2016 年 1 月 7 日 GIMPS 發現 _M_7420 萬 7281
* 2018 年 1 月 3 日 GIMPS 發現的 _M_7723 萬 2917 有 23249425 位數。
* 2018 年 12 月 7 日 GIMPS 的 _M_8258 萬 9933 有 24862048 位數。

### 梅森質數列表

 古代知道的梅森質數

 以試除法發現的梅森質數

 梅森遺漏的梅森質數

 GIMPS 發現的梅森質數

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

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

 Donald B. Gillies 發現的梅森質數

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

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

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

## 外部連結

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

## 參考