ブログ

Blogs

メルセンヌ数Mnが素数ならnも素数である

Art Of MathematicsというFBのグルーブで、メルセンヌ数(Mn = 2^n-1)を説明した写真がシェアされてたので覗いてみると、「メルセンヌ数Mnが素数ならnも素数である」という命題をどうやって証明するかで色々コメントが書きこまれていたのが面白かったです。nが合成数であって、n=p*qと書けるのであれば、2^n-1 は 2^p-1 を因数に持つので合成数になるから、対偶をとれば上記命題は証明できるのですが、「2^n-1 は 2^p-1 を因数に持つ」ことが自明かどうかで議論になっていました。

直感的にわかりやすい直接素因数分解する方法は、ちょっと長くなっちゃうのですが、
(2^p-1){2^((q-1)*p)+2^((q-2)*p)+2^((q-3)*p)+…+2^p+1} を計算すると、+の項と-の項が消しあって、2^(p*q)-1 = 2^n-1 となるので、「2^n-1 は 2^p-1 を因数に持つ」ことは直接証明できちゃうのですが、そこまで言及してるコメントはなかったですね。