Mersenne素数
概要
Mersenne素数（Mersenne prime）とは、正の整数 $n$ について $M_n=2^n-1$ の形に書ける素数のことである。$3,7,31,127$ がその例である。$\gcd(2^m-1,2^n-1)=2^{\gcd(m,n)}-1$ であることから、$2^n-1$ が素数なら $n$ は素数でなければならないが、逆は成り立たず $2^{11}-1=2047=23\cdot89$ である。奇素数 $p$ に対する $2^p-1$ の素因数は $2p$ で割って $1$ 余り、$8$ で割って $\pm1$ 余るものに限られ、$2^p-1$ が素数かどうかは Lucas–Lehmer の判定法で決まる。偶数の完全数は Mersenne 素数と 1 対 1 に対応する。Mersenne 素数が無限にあるかどうかは未解決である。
$2$ を何回か掛けた数から $1$ を引くと、$1,3,7,15,31,63,127,255,\dots$ という数が並ぶ。これらは二進法（n進法と記数法）で書くと $1,11,111,1111,\dots$ と $1$ だけが並ぶ数である。このうち $3=2^2-1$、$7=2^3-1$、$31=2^5-1$、$127=2^7-1$ は素数だが、$15=2^4-1=3\cdot5$、$63=2^6-1=7\cdot9$、$255=2^8-1=3\cdot5\cdot17$ は素数でない。素数になったのは指数が $2,3,5,7$ という素数のときだけであり、実際、$2^n-1$ が素数なら $n$ は素数でなければならない。ところが逆は成り立たず、$11$ は素数なのに $2^{11}-1=2047=23\cdot89$ である。$2^n-1$ の形の素数を Mersenne 素数という。2026 年 9 月時点で知られている最大の Mersenne 素数は $41{,}024{,}320$ 桁の $2^{136279841}-1$（2024 年 10 月発見）であり、発見時には知られている最大の素数でもあった（GIMPS24）。このような巨大な数の素数判定ができるのは、この形の数だけに使える高速な判定法（Lucas–Lehmer の判定法）があるからである。
定義
正の整数 $n$ に対し
$$
M_n:=2^n-1
$$
を Mersenne 数（Mersenne number）という。$M_n$ が素数であるとき、$M_n$ を Mersenne 素数（Mersenne prime）という。
$M_1=1$ は素数でないので、Mersenne 素数 $M_n$ では $n\geq2$ である。後の cor-mersenne-prime-exponent により、$M_n$ が素数なら $n$ は素数である。このため文献によっては、Mersenne 数を $n$ が素数 $p$ のときの $M_p=2^p-1$ に限って呼び、Mersenne 素数を「$p$ が素数で $2^p-1$ も素数であるときの $2^p-1$」と定義する（完全数 の記事はこの流儀である）。どちらの流儀でも Mersenne 素数の全体は同じである。便宜上 $M_0:=2^0-1=0$ ともおく。
直感
$M_n$ の素数性は、指数 $n$ の性質に強く縛られている。$2^n\equiv1\pmod{M_n}$ なので、法 $M_n$ で $2$ の冪は周期 $n$ で繰り返し、指数の割り算の余りがそのまま $M_n$ の割り算の余りに反映される（prop-mersenne-prime-gcd）。また $p$ が奇素数のとき、$M_p$ の素因数 $q$ では $2$ の元の位数がちょうど $p$ になるので、$q$ は $2p$ で割って $1$ 余る数に限られる。一般の整数の素数判定では素因数の候補を絞れないが、Mersenne 数では候補が強く制限され、さらに $2+\sqrt3$ の冪の計算だけで素数かどうかが判定できる。
例と反例
$n=1,\dots,13$ に対する $M_n$ とその素因数分解は次のとおりである。
$$
\begin{array}{c|l}
n & M_n\\ \hline
1 & 1\\
2 & 3\\
3 & 7\\
4 & 15=3\cdot5\\
5 & 31\\
6 & 63=3^2\cdot7\\
7 & 127\\
8 & 255=3\cdot5\cdot17\\
9 & 511=7\cdot73\\
10 & 1023=3\cdot11\cdot31\\
11 & 2047=23\cdot89\\
12 & 4095=3^2\cdot5\cdot7\cdot13\\
13 & 8191
\end{array}
$$
素数になるのは $n=2,3,5,7,13$ のときであり、Mersenne 素数を小さい順に並べると $3,7,31,127,8191,131071,524287,2147483647,\dots$（指数 $2,3,5,7,13,17,19,31,\dots$）となる。表から $M_2=3$ は $M_4,M_6,M_8,M_{10},M_{12}$ を割り、$M_3=7$ は $M_6,M_9,M_{12}$ を割ることが読み取れる。これは $2\mid n$ なら $M_2\mid M_n$、$3\mid n$ なら $M_3\mid M_n$ という規則の表れである（prop-mersenne-prime-gcd）。
$p$ が素数でも $M_p$ は素数とは限らない。
$$
M_{11}=23\cdot89,\qquad M_{23}=47\cdot178481,\qquad M_{29}=233\cdot1103\cdot2089,
$$
$$
M_{67}=193707721\cdot761838257287.
$$
満たす性質は「指数 $p$ が素数」、満たさない性質は「$M_p$ が素数」であり、破る含意は cor-mersenne-prime-exponent の逆「$n$ が素数なら $M_n$ は素数」である。$M_{67}$ が合成数であることは Lucas が 1876 年に示し、具体的な分解は Cole が 1903 年に見つけた（Dic05 Preface p. iv）。
符号を変えた $2^n+1$ では、素数になるための指数の条件がまったく異なる。$2^3+1=9$、$2^5+1=33=3\cdot11$、$2^7+1=129=3\cdot43$ のように、指数が奇素数だと $2^n+1$ は $3$ で割り切れて合成数になる（$2\equiv-1\pmod3$ より $2^n+1\equiv(-1)^n+1=0\pmod3$）。$2^n+1$ が素数になりうるのは $n$ が $2$ の冪のときに限られ、その形の数は Fermat数 と呼ばれる。「$2^n\pm1$ が素数なら $n$ は素数」という類推は $2^n+1$ については成り立たない（$2^4+1=17$ は素数だが $4$ は素数でない）。
性質
指数の整除とMersenne数の整除
$0$ 以上の整数 $m,n$（少なくとも一方は正）に対し
$$
\gcd(M_m,M_n)=M_{\gcd(m,n)}
$$
が成り立つ。特に、正の整数 $m,n$ について、$M_m\mid M_n$ であることと $m\mid n$ であることは同値である。
まず、$n\geq1$ と $q\geq0$ について $M_n\mid M_{qn}$ である。実際、$x:=2^n$ とおくと
$$
M_{qn}=x^q-1=(x-1)(x^{q-1}+x^{q-2}+\dots+x+1)
$$
であり、$x-1=M_n$ である（$q=0$ なら $M_0=0$ で明らか）。
次に、$n\geq1$ とし、除法の原理により $m=qn+r$（$0\leq r< n$）と書くと
$$
M_m=2^{qn+r}-1=2^r(2^{qn}-1)+(2^r-1)=2^rM_{qn}+M_r
$$
である。$M_n\mid M_{qn}$ なので、$M_m$ と $M_n$ の公約数は $M_r$ を割り、逆に $M_n$ と $M_r$ の公約数は $M_m$ を割る。よって
$$
\gcd(M_m,M_n)=\gcd(M_n,M_r)
$$
である。一方 $\gcd(m,n)=\gcd(n,r)$ である。そこで $\min(m,n)$ に関する帰納法で主張を示す。$n=0$ のときは $\gcd(M_m,M_0)=\gcd(M_m,0)=M_m=M_{\gcd(m,0)}$ である（$m=0$ のときも同様）。$m,n\geq1$ で、対称性から $m\geq n$ としてよい。上の式と帰納法の仮定（$\min(n,r)=r< n$）から
$$
\gcd(M_m,M_n)=\gcd(M_n,M_r)=M_{\gcd(n,r)}=M_{\gcd(m,n)}
$$
を得る。この議論は、指数に対する Euclidの互除法 をそのまま Mersenne 数の互除法に写したものである。
後半について、$m\mid n$ なら $\gcd(m,n)=m$ なので $\gcd(M_m,M_n)=M_m$、すなわち $M_m\mid M_n$ である。逆に $M_m\mid M_n$ なら $\gcd(M_m,M_n)=M_m$ なので $M_{\gcd(m,n)}=M_m$ である。$k\mapsto M_k=2^k-1$ は狭義単調増加なので $\gcd(m,n)=m$、すなわち $m\mid n$ である。$\square$
正の整数 $n$ について、$M_n$ が素数ならば $n$ は素数である。
$n=1$ なら $M_1=1$ は素数でない。$n\geq2$ が合成数なら $n=ab$、$1< a< n$ と書ける。prop-mersenne-prime-gcd により $M_a\mid M_n$ であり、$a\geq2$ から $M_a\geq3$、$a< n$ から $M_a< M_n$ である。よって $M_n$ は $1$ でも自身でもない約数 $M_a$ をもち、素数でない。対偶を取れば主張を得る。$\square$
この系により、Mersenne 素数を探すには素数の指数 $p$ だけを調べればよい。同じ事実は 完全数 の記事の補題「Mersenne 数の指数」でも因数分解の公式から直接示されている。
正の整数 $m,n$ が互いに素ならば、$M_m$ と $M_n$ も互いに素である。特に、相異なる素数 $p,q$ に対する $M_p$ と $M_q$ は互いに素である。
prop-mersenne-prime-gcd により $\gcd(M_m,M_n)=M_{\gcd(m,n)}=M_1=1$ である。$\square$
$2$ の位数を使って同じことを直接示す証明が Cri24 Proposition 12.1.11（pp. 187–189）にある。
素因数の形
$p$ を素数とし、素数 $q$ が $M_p=2^p-1$ を割るとする。
- $q\equiv1\pmod p$ である。$p$ が奇素数なら $q\equiv1\pmod{2p}$ である。
- $p$ が奇素数なら $q\equiv\pm1\pmod8$ である。
1 は Fermatの小定理 の記事の命題「Mersenne数の素因数」である。要点は、$2^p\equiv1\pmod q$ から $q$ を法とする $2$ の位数 $\operatorname{ord}_q(2)$ が $p$ を割り、$2\not\equiv1\pmod q$ なので $\operatorname{ord}_q(2)=p$ となり、位数は $q-1$ を割ることである。
2 を示す。$M_p$ は奇数なので $q$ は奇素数である。$p$ は奇数なので $p+1$ は偶数であり、$2^p\equiv1\pmod q$ から
$$
2\equiv2\cdot2^p=2^{p+1}=\left(2^{(p+1)/2}\right)^2\pmod q
$$
となる。よって $2$ は $q$ を法とする平方剰余である（$q\nmid2$ に注意）。平方剰余 の記事の定理「第2補充法則と相互法則」の 1 により、$2$ が奇素数 $q$ を法とする平方剰余であることは $q\equiv\pm1\pmod8$ と同値なので、$q\equiv\pm1\pmod8$ である。$\square$
$p=2$ では 1 の後半と 2 は成り立たない。$M_2=3$ の素因数 $3$ は $3\equiv1\pmod2$ を満たすが、$3\not\equiv1\pmod4$ であり、$3\not\equiv\pm1\pmod8$ である。
$M_{11}=2047=23\cdot89$ では、$23=2\cdot11+1$、$89=8\cdot11+1$ はともに $22$ で割って $1$ 余り、$23\equiv7$、$89\equiv1\pmod8$ である。$M_{29}=233\cdot1103\cdot2089$ でも、$232=58\cdot4$、$1102=58\cdot19$、$2088=58\cdot36$ であり、$233\equiv1$、$1103\equiv7$、$2089\equiv1\pmod8$ である。
この制限は素数判定の手間を大きく減らす。$M_{13}=8191$ が素数であることを確かめるには、$\sqrt{8191}<91$ 以下の素因数がないことを見ればよい（素数 の記事の命題「素因数の存在」）。prop-mersenne-prime-factor-form により候補は $26k+1$ の形の素数で $8$ で割って $\pm1$ 余るものに限られる。$91$ 未満の $26k+1$ は $27,53,79$ であり、$27$ は素数でなく、$53\equiv5\pmod8$ は条件を満たさない。残る $79$ については $8191=79\cdot103+54$ なので割り切れない。よって $8191$ は素数である。
任意の素数 $p$ に対し、$M_p$ は $p$ より大きい素因数をもつ。したがって素数は無限に存在する。
$M_p\geq3$ なので $M_p$ は素因数 $q$ をもつ。prop-mersenne-prime-factor-form の 1 により $q\equiv1\pmod p$ であり、$q>1$ なので $q\geq p+1>p$ である。よってどの素数 $p$ に対しても $p$ より大きい素数が存在し、最大の素数はない。$\square$
これは 素数の無限性 の別証明の 1 つである。Mersenne 素数そのものが無限にあるかどうかは分からないが、Mersenne 数の素因数からは素数がいくらでも得られる。
$p$ を $4$ で割って $3$ 余る素数とし、$q:=2p+1$ も素数であるとする。このとき $q\mid M_p$ である。さらに $p>3$ ならば $M_p$ は合成数である。
$p=4k+3$ と書くと $q=8k+7\equiv7\pmod8$ である。平方剰余 の記事の定理「第2補充法則と相互法則」の 1 により、$2$ は $q$ を法とする平方剰余である。同じ記事の定理「Eulerの規準」により
$$
2^{(q-1)/2}=2^p\equiv1\pmod q
$$
であり、$q\mid 2^p-1=M_p$ を得る。$p>3$ なら $p\geq4$ について $2^p-1>2p+1$ である（$p=4$ で $15>9$、以後 $p$ を $1$ 増やすと左辺は $2^p$ 増え右辺は $2$ 増える）から、$q$ は $M_p$ の $1$ でも自身でもない約数であり、$M_p$ は合成数である。$\square$
たとえば $p=11,23,83,131,179,191,239$ はいずれも $4$ で割って $3$ 余り $2p+1$ が素数なので、$23\mid M_{11}$、$47\mid M_{23}$、$167\mid M_{83}$ などが従う。この事実は Euler が述べた（Dic05 Chapter I, p. 17）。$p=3$ では $q=7=M_3$ で、$M_3$ は素数である。一方、$p$ が $4$ で割って $1$ 余り $q=2p+1$ が素数のときは、$q\equiv3\pmod8$ なので $2$ は $q$ を法とする平方非剰余であり、Euler の規準から $2^p\equiv-1\pmod q$、すなわち $q\nmid M_p$ である（例：$2^5=32\equiv-1\pmod{11}$）。
Lucas–Lehmer の判定法による素数判定
整数の列 $(s_k)_{k\geq0}$ を
$$
s_0:=4,\qquad s_{k+1}:=s_k^2-2
$$
で定める。$s_0=4$、$s_1=14$、$s_2=194$、$s_3=37634$、$s_4=1416317954$ と急速に大きくなるが、判定に使うのは $M_p$ で割った余りだけなので、実際の計算では毎回 $M_p$ で割った余りを取ってから次の項を作る。
奇素数 $p$ について、$M_p=2^p-1$ が素数であることと $M_p\mid s_{p-2}$ であることは同値である。これが Lucas–Lehmerの判定法 であり、十分性・必要性の両方の証明と計算例はその記事にある。十分性は、$\omega=2+\sqrt3$ が $M_p$ の素因数 $q$ を法とした $\mathbb{Z}[\sqrt3]$ の剰余環で位数 $2^p$ をもつことから、$q^2>M_p$ を導いて示される。たとえば $p=5$ では余りは $4,14,8,0$ と進んで $M_5=31$ は素数であり、$p=11$ では $s_9\equiv1736\not\equiv0\pmod{2047}$ なので、$2047=23\cdot89$ という分解を見つけずに合成数であることが分かる。
計算は $M_p$ を法とする 2 乗と引き算を $p-2$ 回繰り返すだけで済む。しかも $M_p=2^p-1$ で割った余りは、$2^p\equiv1$ を使って二進表示の上位の桁を下位の桁に足し込むだけで計算できる。これが、巨大な Mersenne 数の素数判定が現実的に可能な理由である。
偶数の完全数との対応
正の整数 $N$ が完全数であるとは、$N$ の正の約数の和が $2N$ に等しいことをいう。完全数 の記事の定理「Euclid–Euler の定理」により、偶数の完全数は、Mersenne 素数 $M_p$ を用いた
$$
N=2^{p-1}M_p=2^{p-1}(2^p-1)
$$
の形の数にちょうど一致し、$p$ は $N$ から一意に定まる。たとえば $M_2,M_3,M_5,M_7$ から完全数 $6,28,496,8128$ が得られる。したがって Mersenne 素数が 1 つ見つかるたびに偶数の完全数が 1 つ見つかり、偶数の完全数が無限にあることと Mersenne 素数が無限にあることは同値である。
補足
名称は、1644 年の著書で $2^{p-1}(2^p-1)$ が完全数となる $p$ を $2,3,5,7,13,17,19,31,67,127,257$ と主張した Mersenne に由来する。この一覧には誤りがあり、$M_{67}$ は合成数で、$M_{61}$、$M_{89}$、$M_{107}$ は素数である（Dic05 Chapter I, pp. 12–13 と Preface p. iv）。$M_{257}$ も後に合成数であることが分かり、$257$ 以下の指数で Mersenne 素数となるのは $2,3,5,7,13,17,19,31,61,89,107,127$ の 12 個である（GIMPS24 の一覧で次の指数は $521$）。$M_{127}$ が素数であることは Lucas が示した（Dic05 Preface p. iv）。
Great Internet Mersenne Prime Search（GIMPS）の一覧（2026 年 9 月時点）には 52 個の Mersenne 素数が載っており、最大のものは 2024 年 10 月に見つかった $M_{136279841}$ である。ただし $M_{82589933}$ と $M_{136279841}$ の間の指数はすべては調べ終わっておらず、「$k$ 番目の Mersenne 素数」という番号付けの一部は暫定的である（GIMPS24）。
Mersenne 素数が無限に存在するかどうかは未解決である（Mos11 Classical Unsolved Problems 第 11 問、p. 73）。prop-mersenne-prime-euler-factor により、$4$ で割って $3$ 余る素数 $p$ で $2p+1$ も素数となるものが無限にあれば、合成数の $M_p$（$p$ は素数）も無限にあることになるが、そのような $p$ が無限にあるかどうかも知られていない。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
