メルセンヌ数
Mn が素数ならば n もまた素数であることは、次の式から分かる:
2 − 1 = (2 − 1)(1 + 2 + 2 + ⋯ + 2).
対偶命題「n が合成数ならば Mn は合成数である」が示される。また、この等式より、m | n のとき Mm | Mn である。一方、 p が素数でも Mp が素数とは限らない。最小の反例は p = 11 の場合であり、M11 = 2047 = 23 × 89 が成り立つ。
(奇)素数 p に対して Mp が素数であるかどうかは、リュカ-レーマー・テストによって判定できる (#素数判定法節を参照)。
1644年、マラン・メルセンヌは「素数 p で 2 − 1 が素数になるのは、p ≦ 257 では p = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 の11個の場合だけである」という予想を公表した。しかしメルセンヌ自身はその予想を証明することができず、しかもその予想の一部は誤っていた。
成果を見るのはメルセンヌが予想を公表してから128年後、1772年、オイラー(p = 31 では素数)。その次の成果はさらに104年後、1876年、リュカ(効率的な素数判定法リュカ・テスト(英語版)を考案、p = 67 では素数でない、p = 127 では素数)であった。その後リュカ・テストは改良が加えられ、メルセンヌが予想した範囲にない3個が付け加えられた(p = 61(1883年)、p = 89(1911年)、p = 107(1914年))。メルセンヌが予想した最後の数 p = 257 について決着がついたのは1922年のことであり、 p = 257 も合成数だった。