皆さま、こんにちは。
久々に素数にまつわる記事を上げようと思います。今回取り上げるのは、「メルセンヌ素数」です。
一般に、2進数から1引いた数、すなわち
2^n -1
の形で書ける整数を「メルセンヌ数」と呼びます。
このメルセンヌ数には、以下の性質があります。
まずは、これを証明していきましょう。
この定理を直接証明するのは困難なので、対偶を取ってみます。すると、
となります。証明しやすいこちらが示せれば、元の性質も証明できたことになります。
なので、このT'を証明していきます。
nが合成数だとすると、2以上の整数p, qを使って、
n=pq
と書くことができます。このとき、2^n -1 は、
2^n - 1 = 2^(pq) - 1
= (2^p)^q -1 = X^q -1
= (X-1) × {1+ X + X^2 +・・・+ X^(q-1) }
と因数分解された形にすることができます。ここでX=2^pです。
pが2以上なので、X≧4となります。よって、
X-1 ≧3
1+ X + X^2 +・・・+ X^(q-1) ≧5
となって、2^n -1の各因数が2以上の整数になることが分かります。これは合成数の定義そのものです。
以上から、nが合成数だとすると、2^n -1 も合成数となり、T'が示せたことになり、引いては、元々の「2^n -1が素数ならば、nは素数である」 が証明できたことになります。
さて、この下で、もし「nが素数ならば、2^n -1 は素数である」という逆の定理が成り立っていれば、とんでもない大発見になります。なぜなら、
2^n -1 のnに素数を次々に突っ込んでいけばすぐさま新しい素数が作れるからです。いわば素数工場となるわけです。
しかし、世の中そう簡単には問屋が卸しません。
残念ながら「nが素数であっても、2^n -1 が素数とは限らない」のです。
実際に代入してみると、
n=2 →2^n -1 =3
n=3 →2^n -1 =7
n=5 →2^n -1 =31
n=7 →2^n -1 =127
となっていて、n=7までは2^n -1は素数になっています。ところが、
n=11 →2^n -1 = 2047 = 23×89
となって、n=11の場合は合成数となってしまいます。
実は、2^n -1 の形になる素数、メルセンヌ素数は、2021年現在51個しか発見されておらず、今のところ最大のものは、n=82589933のもので、実に2500万桁近くもある超巨大な素数となります。そして、メルセンヌ素数が無限個あるのか否かは未だに証明されていない未解決問題となっています。
とはいえ、メルセンヌ数のうち素数になる可能性があるのはnが素数のものしかないので、メルセンヌ素数は比較的探しやすいタイプの素数になっており、近年次々に発見されていく「最大の素数」は、すべてメルセンヌ素数になっています。
そして、このメルセンヌ素数は、「完全数」と呼ばれる数と密接に関わってきます。
完全数については、次回の記事で紹介します。
