📂整数論

メルセンヌ素数

定義 ¹

$M_{n} = 2^{n} - 1$が素数なら、$M_{n}$をメルセンヌ素数^{mersenne Prime}と呼ぶ。

説明

メルセンヌ素数の発見は、$p=x^{n}-1$の形が素数かどうかの探求から始まる。式を見るとすぐに$x$が奇数の場合、$p=2$を除いて素数になることは不可能だと分かる。また、 $$x^{n}-1 = (x-1) ( x^{n-1} + x^{n-2} + \cdots + x^2 + x + 1 )$$ なので、$( x^{n-1} + x^{n-2} + \cdots + x^2 + x + 1 )$がどんな数であれ、少なくとも$(x-1)$は必ず$1$でなければならない。つまり$x$は偶数であるだけではなく、正確に$2$でなければならず、したがって$p= 2^{n} - 1$の形だけを気にすればよい。

2018年5月までに発見されたメルセンヌ素数は合計で$50$個あり、最も大きなメルセンヌ素数は$M_{77,232,917}$である。これは数字の長さが$23,249,425$にも及ぶ大きな数だ。一方、最初に現れるメルセンヌ素数をいくつか見てみると、興味深い点を発見できる。

$$\begin{align*} M_{2} &= 2^{2} - 1 = 3 \\ M_{3} &= 2^{3} - 1 = 7 \\ M_{5} &= 2^{5} - 1 = 31 \\ M_{7} &= 2^{7} - 1 = 127 \\ M_{13} &= 2^{13} - 1 = 8191 \end{align*}$$

定理

メルセンヌ素数$M_{n}$について、$n$は素数である。

証明

メルセンヌ素数$M_{n} = 2^{n} - 1$について、２つの整数$a,b$に対して$n=ab$と仮定してみると、 $$2^{ab} - 1 = (2^{a} - 1) ( 2^{a(b-1)} + 2^{a(b-2)} + \cdots + 2^{a} + 1 )$$ つまり、$2^{ab} - 1$は合成数であり、これは仮定に矛盾する。

■

逆が成り立たないことを示す反例としては、$n=11$の場合がある。$M_{11} : = 2^{11} - 1 = 2047$は$23$と$89$の積であり、$M_{11}$はメルセンヌ素数ではない。