梅森質數檢查器

測試給定的指數 p 是否能使 2^p − 1 成為梅森質數。使用帶有動畫迭代追蹤的 Lucas-Lehmer 質性測試、二進制位元模式視覺化、Euclid-Euler 完全數配對，以及關於 52 個已知梅森質數的歷史背景。

梅森質數檢查器

歡迎使用梅森質數檢查器，這是一個互動式工具，用於測試當指數 $p$ 高達 5000 時，$2^p - 1$ 是否為梅森質數。此工具運行著名的盧卡斯-萊默質數性檢驗 (Lucas-Lehmer primality test)，顯示遞迴關係 $S_i = S_{i-1}^2 - 2 \pmod{M_p}$ 的動畫迭代軌跡，視覺化二進位位元模式（這是每個梅森數的定義特徵），並且當結果為質數時，會透過歐幾里得-歐拉定理將其與對應的偶完全數配對。

什麼是梅森質數？

梅森數是形如 $M_p = 2^p - 1$ 的數字。當 $M_p$ 本身也是質數時，它就被稱為梅森質數。這個名稱是為了紀念馬蘭·梅森 (Marin Mersenne, 1588-1648)，這位法國修士編製了早期案例的目錄，並推測了 257 以下的哪些指數會產生質數——雖然該列表後來被證明部分錯誤，但它開啟了長達三個世紀的研究。

梅森質數

$$M_p = 2^p - 1 \;\; \text{為質數，其中 } p \text{ 本身必須是質數}$$

依序排列的前幾個梅森質數：

$M_2 = 3$
$M_3 = 7$
$M_5 = 31$
$M_7 = 127$
$M_{13} = 8{,}191$
$M_{17} = 131{,}071$
$M_{19} = 524{,}287$
$M_{31} = 2{,}147{,}483{,}647$（由歐拉於 1772 年發現——在之後的 104 年裡一直是已知最大的質數）

截至 2024 年，目前已知恰好有 52 個梅森質數。目前的紀錄是 $M_{136{,}279{,}841}$，由 GIMPS 分散式運算專案於 2024 年 10 月發現——這是一個擁有 41,024,320 位十進位數的數字。

盧卡斯-萊默檢驗法

梅森質數之所以能在質數紀錄簿中佔據主導地位，是因為愛德華·盧卡斯 (Édouard Lucas, 1878) 發現並由德里克·萊默 (Derrick Lehmer, 1930) 簡化的一種專門且極其快速的質數性測試：

盧卡斯-萊默檢驗法

$$S_0 = 4, \quad S_i = S_{i-1}^2 - 2 \pmod{M_p}$$

對於質數 $p \geq 3$: $\;M_p$ 是質數 $\iff S_{p-2} \equiv 0 \pmod{M_p}$

此測試僅需要 $p-2$ 次模平方運算——使用傳統乘法大約需要 $O(p^3)$ 位元操作，若使用 FFT 則為 $O(p^2 \log p \log\log p)$。與對 $M_p$ 大小（數百萬位數）的數字進行通用質數測試相比，後者完全不可行。盧卡斯-萊默捷徑正是梅森質數搜尋成為可能的關鍵。

為什麼 $p$ 必須是質數？

如果 $p = a \cdot b$ 且 $a, b > 1$，一個古典恆等式顯示 $2^a - 1$ 會整除 $2^{ab} - 1$：

因式分解恆等式

$$2^{ab} - 1 = (2^a - 1)\left(2^{a(b-1)} + 2^{a(b-2)} + \cdots + 2^a + 1\right)$$

因此，如果指數是合數，$M_p$ 自動也是合數。反之則不然： $p$ 是質數並不能保證 $M_p$ 也是質數。例如，$p = 11$ 是質數，但 $M_{11} = 2047 = 23 \times 89$。

梅森質數與完全數 (歐幾里得-歐拉)

歐幾里得在西元前 300 年左右觀察到，如果 $2^p - 1$ 是質數，那麼 $2^{p-1}(2^p - 1)$ 就是一個完全數——一個等於其所有真因數之和的數字。歐拉後來證明了其逆命題：每個偶完全數都以此方式產生。

歐幾里得-歐拉定理

$$N \text{ 是偶完全數} \iff N = 2^{p-1}(2^p - 1),\;\; 2^p - 1 \text{ 為質數}$$

因此，發現一個新的梅森質數會立即產生一個新的完全數。前四個偶完全數是 6、28、496 和 8128——自古以來就為人所知。是否存在奇完全數，仍是一個超過 2300 年未解的問題。

二進位位元模式

每個梅森數都有一個獨特且整齊的二進位表示：二進位的 $2^p$ 是 $1$ 後面跟著 $p$ 個零，所以 $2^p - 1$ 恰好是 $p$ 個連續的 1 位元：

M_5 = 2^5 − 1 = 11111₂ = 31

M_7 = 2^7 − 1 = 1111111₂ = 127

這就是為什麼本工具將每個位元視覺化為獨立的方塊——位元模式是梅森數的視覺特徵，無論該數字是否為質數。

如何使用此計算機

輸入一個指數 $p$： 1 到 5,000 之間的任何正整數。
點擊「檢查」： 工具首先檢查 $p$ 是否為質數；如果不是，它會解釋為何 $M_p$ 必定是合數。
對於質數 $p$： 盧卡斯-萊默遞迴會對 $M_p$ 運行 $p - 2$ 次迭代。
查看輸出結果： 判定結果橫幅、6 行迭代軌跡（對於大指數 $p$，中間步驟會以 "..." 省略）、$M_p$ 的十進位和二進位形式，以及適用的歐幾里得-歐拉完全數配對。

前十二個已知的梅森質數

#	指數 $p$	$M_p = 2^p - 1$	位數	發現年份
1	2	3	1	古代
2	3	7	1	古代
3	5	31	2	古代
4	7	127	3	古代
5	13	8,191	4	1456 (佚名)
6	17	131,071	6	1588 Cataldi
7	19	524,287	6	1588 Cataldi
8	31	2,147,483,647	10	1772 歐拉
9	61	2.3 × 10^18	19	1883 Pervushin
10	89	6.2 × 10^26	27	1911 Powers
11	107	1.6 × 10^32	33	1914 Powers
12	127	1.7 × 10^38	39	1876 盧卡斯

GIMPS 專案

網際網路梅森質數大搜索 (GIMPS) 由 George Woltman 於 1996 年發起，是一個分散式運算專案，志願者捐獻 CPU 時間對候選指數運行盧卡斯-萊默檢驗。截至 2024 年，自 M_35 = M_{1398269} (1996) 以來的每一個梅森質數都是由 GIMPS 發現的。在現代前沿領域（指數接近 $10^8$）進行單次盧卡斯-萊默測試需要數週的 GPU 運算時間。

關於梅森質數的趣聞

$M_{31} = 2{,}147{,}483{,}647$ 是最大的 32 位元有號整數——即 C 語言中著名的 $\texttt{INT\_MAX}$。這並非巧合：該值源於 $M_{31}$ 是質數，因此是一個自然的「溢位前夕」邊界。
相繼梅森質數之間的間距大小不明。目前尚不知道是否存在無窮多個梅森質數——Lenstra-Pomerance-Wagstaff 猜想預測存在無窮多個，且增長速度大約像 $e^\gamma \log_2 p$。
2008 年，電子前哨基金會 (EFF) 向首位發現 1000 萬位數質數的人頒發了 10 萬美元獎金。該獎項由加州大學洛杉磯分校 (UCLA) 的 GIMPS 團隊以 $M_{43112609}$ 獲得。目前仍有 15 萬美元的獎金等待首位發現 1 億位數質數的人。
$M_{31}$ 出現在 1811 年俄羅斯 100 盧布紀念鈔上，以紀念歐拉的發現——這是少數被印在貨幣上的質數之一。
因為每個梅森質數都會產生一個完全數，人類目前記錄在案的偶完全數恰好有 52 個（對應 52 個已知的梅森質數）。

常見問題

什麼是梅森質數？

梅森質數是形如 $2^p - 1$ 的質數，其中 $p$ 本身也必須是質數。前幾個是 3、7、31、127 和 8,191。截至 2024 年，已知有 52 個梅森質數；目前已知最大的質數 ($M_{136{,}279{,}841}$) 是一個擁有超過 4100 萬位數的梅森質數。

盧卡斯-萊默檢驗法是如何運作的？

對於質數指數 $p \geq 3$，定義 $S_0 = 4$ 且 $S_i = S_{i-1}^2 - 2 \pmod{M_p}$。梅森數 $M_p = 2^p - 1$ 是質數，當且僅當 $S_{p-2} \equiv 0 \pmod{M_p}$。此測試進行 $p - 2$ 次迭代，每次迭代包含一次模平方運算。

為什麼 $p$ 必須是質數？

如果 $p = ab$ 且兩個因數都大於 1，則 $2^p - 1$ 可以被 $2^a - 1$（以及 $2^b - 1$）整除，因此 $M_p$ 是合數。反之則不然：$p$ 為質數並不代表 $M_p$ 一定是質數。例如 $p = 11$ 是質數，但 $M_{11} = 2047 = 23 \times 89$ 是合數。

梅森質數與完全數之間有什麼聯繫？

歐幾里得-歐拉定理指出，每個偶完全數都具有 $2^{p-1}(2^p - 1)$ 的形式，其中 $2^p - 1$ 是一個梅森質數。因此，每個梅森質數都會精確生成一個偶完全數，而每個偶完全數都源自一個梅森質數。是否存在奇完全數是數學中最古老的未解問題之一。

為什麼 $M_p$ 在二進位中會有 $p$ 個連續的 1？

二進位中的 $2^p$ 是一個 1 後面跟著 $p$ 個零。減去 1 會將所有 $p$ 個尾隨零轉換為 1。因此，二進位中的 $2^p - 1$ 恰好是 $p$ 個 1——這是每個梅森數（無論質合）定義上的視覺特徵。

此工具可以測試的最大指數是多少？

此工具可測試高達 5,000 的指數，以便盧卡斯-萊默迭代能在正常的網頁請求時間內完成。對於更大的指數（包括指數接近 $10^8$ 的 GIMPS 前沿），則需要如 Prime95 之類的專用軟體，因為在現代 GPU 上，單次測試也可能需要數週的計算時間。

梅森質數檢查器