判斷梅森數
法國數學家盧卡斯 (Edouard Lucas 1842-1891) |
美國數學家 D．H．雷默 (Derrick Henry Lehmer 1905-1991) |
(照片均取自「The MacTutor History of Mathematics Achieve」http://www-gap.dcs.st-and.ac.uk/~history/ )
要判定一梅森數 (Mersenne Number) Mp=2p-1 是不是素數，最簡單的方法是利用我們先前言及費馬 (Pierre de Fermat 1601-1665) 給梅森 (Marin Mersenne 1588-1648) 的一封信中提及的三個定理，它們更是研究梅森數的素性 (Primality) 的基礎：
1. 若 n 不是素數，則 2n-1 也不是素數。
2. 若 n 是素數，則 2n-2 可被 2n 整除。
3. 若 n 是素數除了 2kn+1 這種型式的數以外， 2n-1 不能被其他型式的素數整除。
當中第三項可化簡我們的測試工作，例如判斷 M11 = 211-1 = 2047 的素性，我們只要在素數判別法中測試型如 22k+1 的素數便可，計有 23，以後的 67 已大於 2047的平方根了。但 2047不是 23 的 倍數，所以 M11 是素數。
又例如判斷 M17=217-1 = 131071的素性，符合條件的素數僅有 103、137、239 和 307 四個。而它們均不可整除 131071 ，故 M17 是素數。處理細小的 p 還可以，但數越大，步驟也越多了。
1877年，法國數學家盧卡斯 (Edouard Lucas 1842-1891) 或譯作呂卡、劉卡、魯卡斯等，創製了一新判別法，後經美國人D．H．雷默 (Derrick Henry Lehmer 1905-1991) 改進，我們稱為盧卡斯 - 雷默測試 (Lucas - Lehmar Test)：
為了判斷 Mp = 2p
- 1 (p 為 奇素數) 的素性，先利用 Mp 給出下列一列數，即盧卡斯 - 雷默剩餘 (Lucas - Lehmar Residue) ：s0
= 4，s1 = s02 - 2 (mod Mp)，s2
= s12 - 2 (mod Mp) ，如此下去，直到 sp-2
為止。
Mp=
2p-1是素數的充要條件為 sp-2 = 0。
例：取 p=7，我們有數列 sn： 4, 14, 67, 42, 111, 0，所以 M7 = 127 是一素數。
其實我們可以把未經模的 sn 計出以便運算，即：4, 14, 194, 37634, 1416317954, ..... (OEIS A003010)
但隨 p 越大，Mp 越大，之外構造 s0、 s1、 s2、......、sp-2 的計算量也增加得驚人。直到上世紀 50 年代，電子計算機普及，尋找梅森素數 (Mersenne Prime) 的工作才得躍進。
參考文獻及網址：
Weisstein, E. W. "Lucas-Lehmer Test." From MathWorld. http://mathworld.wolfram.com/Lucas-LehmerTest.html.
