メルセンヌ数

例

この定理はすでに紀元前3世紀頃のユークリッド原論で証明されていた^[4]。そのため、完全数の探索は専らメルセンヌ素数の探索によって行われた。

p > 1ならば、2^p−1(2^p − 1) は明らかに偶数であるが、偶数の完全数がこの生成式で表されるものに限られるのかはユークリッド以来約2000年間にわたって未解決であったが、18世紀にオイラーによりこの形に限ることが証明された^[3] （奇数の完全数が存在するかという問題は今日なお未解決である。）

古代～中世

メルセンヌ素数の探索は紀元前3世紀ごろに端を発する。

小さいメルセンヌ素数がいつから知られているかは定かではないが、少なくとも最初の4つの完全数はゲラサのニコマコスの『算術入門』ですでに言及されている^[8][9]。5番目から7番目の完全数は、13世紀イスラムの数学者イブン・ファッルース (fr:Ibn Fallus) が論文に記している^[10]。ヨーロッパでは、5番目の完全数が1456年と1461年の日付が付された古い写本に記されて^[11][12]おり、6番目と7番目のメルセンヌ素数および完全数も1603年にピエトロ・カタルディ（英: Pietro Cataldi）によって発見されている^[10]。

メルセンヌの予想

1644年、マラン・メルセンヌは「素数 p で 2^p − 1 が素数になるのは、p ≦ 257 では p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 の11個の場合だけである」という予想を発表した^[10][14]。しかしメルセンヌ自身はその予想を証明することができず、しかもその予想の一部は誤っていた。

最初の成果はメルセンヌが予想を発表してから128年後、1772年にオイラーによりp = 31 の場合は素数であること^[1][15]が証明された。その次の成果はさらに104年後、1876年にリュカが効率的な素数判定法リュカ・テスト（英語版）を考案して、p = 67 の場合は素数でないこと、p = 127 の場合は素数であること^[1][16]を証明した。その後リュカ・テストは改良されて、メルセンヌの予想に含まれていなかった素数3個が新たに発見された（p = 61の場合（1883年）、p = 89の場合（1911年）、p = 107の場合（1914年））。メルセンヌが予想した最後の数である p = 257 の場合が合成数であることが確定したのは1922年であった^[1][17]。

結局メルセンヌの4個の予想のうち2つは外れた。なおかつ、間に予想できなかった3つが含まれていたことを考えれば彼の予想は正しかったとはいえないが、その後の歴史を見ても大きな原動力となり先駆的であったことに敬意を表して、素数であるメルセンヌ数をメルセンヌ素数という^[要出典]。

1903年10月、アメリカの数学者フランク・ネルソン・コールは実際の素因数分解を探求し、ニューヨークで開かれたアメリカ数学会の会議で 193707721 × 761838257287 を黒板に計算し、M₆₇ と一致することを証明した。この間一言もしゃべらず、席に戻った後、少し間を置いて拍手が沸き起こったと伝えられている^[18]。

1952年、ラファエル・M・ロビンソン（英語版）が SWAC を利用して M₅₂₁ から M₂₂₈₁ まで、5つのメルセンヌ素数を発見^[1]して以降、発見にはコンピュータが使用されており、コンピュータの進歩と共に新たなメルセンヌ素数が発見されつつある。

GIMPSによる発見

1996年、メルセンヌ素数を発見することを目的として作られた分散コンピューティングによるプロジェクト GIMPS が発足し、35番目のメルセンヌ素数 M_1,398,269（1996年11月13日、Joel Armengaud^{[GIMPS 2]}）以来、GIMPSによるメルセンヌ素数の発見が続いている。

2008年8月23日、GIMPS は46番目の素数候補が、カリフォルニア大学ロサンゼルス校の数学部のコンピュータによって発見されたと報じた^[要出典]。この素数は電子フロンティア財団が賞金を懸けた1000万桁以上の最初の素数となるため、GIMPS によって同校数学部に50,000ドル、慈善事業に25,000ドル、残りを前の6つのメルセンヌ素数の発見者へ分配することになった^{[GIMPS 3]}。

2008年9月6日、GIMPS は45番目の素数候補が、ドイツで発見されたと報じた^[要出典]。これは、GIMPS によって発見された中では、発見順序と桁数が逆転した初めてのケースである。

リュカ・テスト

p が (4j + 3) 型の素数のとき、S₀ = 3, S_n = S_n−1² − 2 (n ≧ 1) で {S_n} を定義すると、

• 任意の${\displaystyle S_{k}}$ ${\displaystyle (0\leqq k\leqq p-2)}$ が${\displaystyle M_{p}}$で割り切れないならば、M_p は合成数である
• ${\displaystyle S_{p-2}}$ が${\displaystyle M_{p}}$で割り切れるならば、M_p は素数である^[19][20][21]

リュカ–レーマー・テスト

p が奇素数のとき、S₀ = 4, S_n = S_n−1² − 2 (n ≧1) で{S_n} を定義すると、

• ${\displaystyle S_{p-2}}$ が${\displaystyle M_{p}}$で割り切れないならば、M_p は合成数である
• ${\displaystyle S_{p-2}}$ が${\displaystyle M_{p}}$で割り切れるならば、M_p は素数である^[22][23][24]

リュカ–レーマー・テストは二進計算機用のアルゴリズムに適しており、コンピュータによるメルセンヌ素数の発見には、この判定法が用いられてきた。例えば、2^p ≡ 1 (mod M_p) より、A·2^p + B ≡ A + B (mod M_p) が成り立つので、M_p で割る割り算の代わりに、二進法で p 桁のシフト演算と足し算だけで計算できる。