📂整数論

メルセンヌ素数

定義 ¹

$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$について、$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}$はメルセンヌ素数ではない。