甚麼是梅森質數？

這是我在 GIMPS 香港羣組的網站上介紹質數的文章之一，這一篇分析質數的數量，前一篇是《質數有多少個？》。

質數以各式各樣的型態出現，有一些質數比其他質數更容易處理，例如：

p = 2^82,589,933 - 1

這個數是 2 的冪減 1，也是已知的最大質數。這兩個特性同時出現並非偶然，原因是我們有特殊技巧可以快速檢驗一個 2 的冪減 1 的數是否質數，所有 2 的冪減 1 的質數稱為「梅森質數」。

梅森是一名 16 世紀的法國神父，他對「完美數」非常感興趣，古希臘數學家歐幾里德曾經證明，如果 M = 2ⁿ - 1 是一個質數，那麼 M(M+1)/2 就是一個完美數，所以尋找完美數即等於尋找 2ⁿ - 1 形式的質數，爲了尋找完美數，梅森神父於是努力尋找這種形式的質數。

一些早期的數學家認為，如果 n 是質數，那麼 2ⁿ - 1 也是質數，但 16 世紀開始一些數學家陸續發現例外的情況，例如 2¹¹ - 1 = 2047 = 23 x 89 便不是質數，2²³ - 1, 2²⁹ - 1 和 2³¹ - 1 都不是質數。

梅森聲稱對於以下數值的 n，2ⁿ - 1 都是質數：

2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257

對於其他小於 257 的 n，2ⁿ - 1 都是合成數。

對 16 世紀的人來說，這些都是十分巨大的數字，根本不可能逐一驗證，即使梅森本人也承認這點。後來的數學家陸續發現梅森漏掉了一些質數，也錯誤地把一些合成數當作質數。例如在梅森死後 200 多年，有數學家發現梅森漏掉了 2⁶¹ -1，卻誤把 2⁶⁷ - 1 當作質數，到了二十世紀初再發現梅森漏掉了 2⁸⁹ - 1 和 2¹⁰⁷ - 1 兩個質數。

提起 2⁶⁷ - 1 這個「懷疑」梅森質數，有一個有趣的故事。1876 年數學家盧卡斯證明 2⁶⁷ - 1 是一個合成數，但一直沒有人知道它的因數。1903 年一次數學家會議中，數學家高爾走到黑板前，默默地計算 2⁶⁷，然後減去 1，得出 147,573,952,589,676,412,927。他跟着在黑板另一端計算 193,707,721 × 761,838,257,287，得出同一個數值。高爾跟着安靜地走回自己的座位，全程不發一言，場內隨即爆起熱烈的掌聲。

在梅森發表他的「梅森質數名單」三百年後，這份名單內的數字才得到完全驗證。隨着電腦的興起，梅森質數的名單增加了很多新成員，最新的梅森質數是

2^82,589,933 - 1

它是第 51 個梅森質數，也是目前所知最大的質數，由 GIMPS 項目在 2018 發現。事實上，1996 開始所有新的梅森質數都是由 GIMPS 發現的。

必須注意的是，我們發現這個巨大的質數，只是巧合地它是一個梅森質數，我們利用了 2 的冪減 1 可以被快速驗證質數這個特性，跳過很多不是這個形式（2 的冪減 1）的質數。所以，比 2^82,589,933 - 1 小的質數很多仍沒被發現。

• 質數
• GIMPS