素数が四つ続くと、五つ目もそうだと思い込みたくなります。p = 2, 3, 5, 7 は 3, 7, 31, 127 を与え、すべて素数です。だから p が素数なら 2ᵖ − 1 も素数だと思いたくなります。しかしそうではありません。計算機は 2¹¹ − 1 を 2047 と計算し、23 × 89 も同じ 2047 です。11 が最初に失敗する素数指数であり、だからこそメルセンヌ素数は公式ではなく探索なのです。
この失敗は偶然ではなく、だからこそ検証できます。p が奇素数のとき素数 q が 2ᵖ − 1 を割り切るなら、2 の q を法とする位数は p なので、p は q − 1 を割り切ります。q は奇数だから 2p も q − 1 を割り切ります。したがって 2047 の因数はすべて 22 を法として 1 でなければならず、23 と 89 が掛け合わさって元に戻るその二つです。この絞り込みがあるからこそメルセンヌ数に手を出せます。算術を始める前にほとんどすべての候補を排除してくれるのです。
答え
2047
読み方
計算機での 2¹¹ − 1 で、23 × 89 も同一の整数を与えます。どちらも厳密です。2047 は、画面が一つずつ数えられなくなる 2⁵³ の地点よりはるかに下にあります。
出典
Mersenne numbers 2ᵖ − 1, named after Marin Mersenne, whose list in Cogitata Physico-Mathematica (1644) was later proved wrong: 2⁶⁷ − 1 is composite, as Édouard Lucas showed in 1876
電卓で解いてみる
これらのリンクは、この問題の数値が入力済みの状態で適切な電卓を開きます。上の行は画面に表示されるはずの内容です。ぜひ自分で確認してください。