判斷梅森數

法國數學家盧卡斯 (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.