メルセンヌ数
p が (4j + 3) 型の素数のとき、S0 = 3, Sn = Sn−1 − 2 (n ≥ 1) で {Sn} を定義すると、
M p ∤ S k ( 0 ≦ k ≦ p − 2 ) {\displaystyle M_{p}\not \mid S_{k}\ (0\leqq k\leqq p-2)} ならば、Mp は合成数である
M p ∣ S p − 2 {\displaystyle M_{p}\mid S_{p-2}} ならば、Mp は素数である
アルゴリズム
アルゴリズムは以下の擬似コードで表される。
メルセンヌ素数は無数に存在するか?
素数 p に対して Mp が合成数であるとき、これをメルセンヌ合成数と呼ぶことにして、それは無数に存在するか?
平方因子を持つメルセンヌ数 Mp(p は素数)が存在するか?
n を奇数とするとき、次の3つの条件のうち2つが満足されれば、残りの1つも満足されると予想されており、n < 10 に対してこの予想は正しいと確認されている。
Mn が素数
n = 2 ± 1 または 4 ± 3
(2 + 1)/3 が素数
メルセンヌ素数の探求は紀元前3世紀ごろに端を発する。古代エジプトの数学者エウクレイデスは『原論』の中で、「2 − 1 が素数ならば、2(2 − 1) は完全数である」ことを証明した。ここから、メルセンヌ素数の探索は完全数の探索にも繋がることとなる。
小さいメルセンヌ素数がいつから知られているかは定かではないが、少なくとも最初の4つの完全数はゲラサのニコマコスの『算術入門』ですでに言及されている。5番目から7番目の完全数は、13世紀イスラムの数学者イブン・ファッルース (fr:Ibn Fallus) が論文に記している。ヨーロッパでは、5番目の完全数が1456年と1461年の日付が付された古い写本に記されており、6番目と7番目のメルセンヌ素数および完全数も1603年にピエトロ・カタルディ(英: Pietro Cataldi)によって発見されている。