読者です 読者をやめる 読者になる 読者になる

メルセンヌ数を2進数で眺める

メルセンヌ数とは、「2n-1」の形で表される数のことです。例えば、
1,3,7,15,31,...
とかですね。
素数のとき、特にメルセンヌ素数といいます。
この間、「メルセンヌ数素数になるのは、nが素数のときだけであることを示せ」という問題を考えていたところ、面白いことに気付きました。

さて、 では2n-1を2進数として眺めてみましょう。
以下、数字の右下の (2)は2進数であることを示します。
まず、 2は10(2)ですから、2nはこうなります。
1000...00(2) (0がn個)
 ですから、2n-1はこうです。
 1111...111(2) (1がn個)
全部繰り下がりが起きたわけですね。
なんとこれはレピュニット数です!

レピュニット数とは何かということですが、英語で書くとrepunit、これはrepeated unitの略で、unit、1を繰り返すということです。
つまり、各桁の数字が全て1である整数を意味します。
例えば、
1,11,111,1111,11111, ...
のことです。
多くの場合、10進数でのものを指しますが、メルセンヌ数は2進数におけるレピュニットだった、というわけです。

ここまで来ると、冒頭の問題は簡単です。
例として、6=2×3の場合を示しましょう。
2^6=111111(2) ですね。
このとき、1が6個並んでいます。これを、3つずつに分けてみましょう。
111|111(2)
こんな感じです。
そうすると、この数は、111(2)で割り切れることが分かります。
なぜなら、111111(2)=111(2)×1001(2)
ですから。
または、このように2つずつに分けても良いですね。
11|11|11(2)
より、
111111(2)=11(2)×10101(2)
これを、一般の場合でやるだけです。
Wikipediaの証明よりも直感的にも分かりやすいですね。