完全数とMersenne素数

同義語：完全数（高校数学）Mersenne素数（高校数学）perfect numbers and Mersenne primes

概要

前提知識: 約数の個数と約数の総和, Fermatの小定理と冪の余り, 冪の余りの周期と元の位数, 因数分解の技法と既約性

高校での出発点：自分以外の約数を足す

$6$ の約数は $1,2,3,6$ である。自分自身の $6$ を除いた約数を足すと $1+2+3=6$ で、もとの数に戻る。このような数を 完全数 という。完全数はどれくらいあり、どんな形をしているだろうか。この記事では、偶数の完全数がすべて $2^{p-1}(2^p-1)$（$2^p-1$ は素数）の形であることを証明し、$2^p-1$ の形の数がいつ素数になるかを、Fermatの小定理と冪の余りと冪の余りの周期と元の位数の道具で調べる。

自分以外の約数の和を調べる

$28$ の約数は $1,2,4,7,14,28$ で、$28$ 以外を足すと $1+2+4+7+14=28$ である。$28$ も完全数である。
$12$ の約数は $1,2,3,4,6,12$ で、$12$ 以外を足すと $1+2+3+4+6=16$ である。$16>12$ なので $12$ は完全数ではない。
$8$ の約数は $1,2,4,8$ で、$8$ 以外を足すと $1+2+4=7$ である。$7<8$ なので $8$ も完全数ではない。

約数を 1 つずつ書き出すのは、数が大きくなると大変である。約数の個数と約数の総和で学んだ約数の総和の公式を使うと、素因数分解から一度に計算できる。

$8128$ は完全数か

$8128=2^6\cdot127$ で、$127$ は素数である（$\sqrt{127}<12$ で、$2,3,5,7,11$ のどれでも割り切れない）。$2^6$ の約数の和は $1+2+4+\dots+64=127$、$127$ の約数の和は $1+127=128$ である。$2^6$ と $127$ は互いに素なので、約数の総和はこの 2 つの積で
$$ 127\cdot128=16256=2\cdot8128 $$
である。約数の総和はもとの数の 2 倍で、自分自身の $8128$ を除いた約数の和は $16256-8128=8128$ である。$8128$ は完全数である。

ex-pmp-start-8128 では、$127=2^7-1$ という形の素数が効いていた。$28=2^2\cdot7$ の $7=2^3-1$、$6=2\cdot3$ の $3=2^2-1$ も同じ形である。そこで $2^n-1$ の形の数を並べてみる。

$2^n-1$ の形の数

$n=2,3,\dots,11$ で $2^n-1$ を計算し、素因数分解する。

$n$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$	$11$
$2^n-1$	$3$	$7$	$15$	$31$	$63$	$127$	$255$	$511$	$1023$	$2047$
素因数分解	素数	素数	$3\cdot5$	素数	$3^2\cdot7$	素数	$3\cdot5\cdot17$	$7\cdot73$	$3\cdot11\cdot31$	$23\cdot89$

素数になったのは $n=2,3,5,7$ のときだけで、どれも $n$ が素数である。ところが $n=11$ は素数なのに、$2^{11}-1=2047=23\cdot89$ は素数でない。

この記事で答える問いは次の 3 つである。

偶数の完全数は、$6,28,496,8128$ のように $2^{p-1}(2^p-1)$ の形に限るか。→ thm-pmp-even
$2^n-1$ が素数になるのは、$n$ が素数のときだけか。→ thm-pmp-mersenne (1)

$2^p-1$ の素因数には、どんな数が現れるか。$2^{11}-1$ の $23$ と $89$ に共通の性質はあるか。→ thm-pmp-mersenne (2)

高校の計算	この記事の言葉	大学の言葉
自分以外の約数を足すと自分に戻る	完全数 $\sigma(n)=2n$（def-pmp-perfect）	約数関数の値の条件
$1+2+4+\dots+2^{k-1}=2^k-1$	Mersenne 数 $M_k=2^k-1$（def-pmp-mersenne）	等比数列の和
$x^{ab}-1$ を $x^a-1$ で割る	指数が合成数なら $M_n$ も合成数	多項式の因数分解
$2$ の累乗の余りの周期	素因数は $2p$ で割って $1$ 余る	乗法群 $(\mathbb{Z}/q\mathbb{Z})^\times$ の元の位数と Lagrange の定理

n = 1 から 10000 までの σ(n)/n の値の散布図。値がちょうど 2（破線）になる点は n = 6, 28, 496, 8128 の 4 つだけ
図 1 は、$n=1$ から $10000$ までについて、約数の総和 $\sigma(n)$ を $n$ で割った値を描いたものである。完全数は $\sigma(n)/n=2$ となる数で、この範囲には $6,28,496,8128$ の 4 つしかない（計算機で全部調べた結果）。$\sigma(n)/n$ の値は $2$ の上にも下にも広く散らばっていて、ちょうど $2$ になることはまれである。

言葉の準備：約数の総和と Mersenne 数

約数の総和と完全数

正の整数 $n$ の正の約数すべての和を $\sigma(n)$ と書く。$\sigma(n)=2n$ となる正の整数 $n$ を 完全数 という。

$\sigma(n)$ には $n$ 自身が含まれるので、$\sigma(n)=2n$ は「$n$ 以外の正の約数の和が $n$ に等しい」と同じことである。ex-pmp-start-small の言葉で言えば、$\sigma(6)=12$、$\sigma(28)=56$ は完全数、$\sigma(12)=28>24$、$\sigma(8)=15<16$ は完全数でない。
$\sigma(n)$ の計算には、約数の個数と約数の総和の 2 つの定理を使う。

使う事実：約数の総和の公式と乗法性

約数の個数と約数の総和の定理「約数の個数と総和の公式」と定理「約数の個数と総和の乗法性」から、次の 2 つが成り立つ。
(1) 素数 $q$ について、$q$ の正の約数は $1$ と $q$ だけなので $\sigma(q)=1+q$ である。
(2) $m$ と $n$ が互いに素な正の整数なら $\sigma(mn)=\sigma(m)\,\sigma(n)$ である。

$2$ の累乗の約数の総和は、この記事で何度も使うので、計算しておく。

$2$ の累乗の約数の総和

$0$ 以上の整数 $k$ について $\sigma(2^k)=2^{k+1}-1$ である。

方針：約数を書き出して、等比数列の和の公式を使う。
段 1（約数を書き出す）。$2^k$ の正の約数は、素因数分解の一意性（素因数分解の一意性）により $2$ 以外の素因数をもたないので、$1,2,2^2,\dots,2^k$ の $k+1$ 個である。
段 2（足す）。初項 $1$、公比 $2$、項数 $k+1$ の等比数列の和なので
$$ \sigma(2^k)=1+2+2^2+\dots+2^k=\frac{2^{k+1}-1}{2-1}=2^{k+1}-1 $$
である。$\square$

$2$ の累乗の約数の総和

$\sigma(16)=1+2+4+8+16=31=2^5-1$ である。
$\sigma(2^6)=\sigma(64)=127=2^7-1$ である。ex-pmp-start-8128 で使った値である。
$\sigma(2^k)=2^{k+1}-1$ は $2\cdot2^k$ より $1$ だけ小さい。$2$ の累乗は、完全数にわずかに届かない数である。

Mersenne 数

Mersenne 数と Mersenne 素数

正の整数 $n$ について $M_n=2^n-1$ を Mersenne 数 という。$M_n$ が素数のとき、$M_n$ を Mersenne 素数 という。

prop-pmp-sigma-power-of-two は $\sigma(2^k)=M_{k+1}$ と書ける。$2$ の累乗の約数の総和が Mersenne 数になることが、完全数と Mersenne 数を結びつける。

小さな Mersenne 数

$M_1=1$ は素数でない。$M_2=3$、$M_3=7$、$M_5=31$、$M_7=127$ は Mersenne 素数である。
$M_4=15$、$M_6=63$ は素数でない。$15=3\cdot5$ の $3=M_2$、$63=7\cdot9$ の $7=M_3$ のように、指数の約数に当たる Mersenne 数で割り切れている（理由は lem-pmp-factor）。

主定理 1：偶数の完全数

定理と証明

ex-pmp-start-8128 の計算は、$127$ を別の Mersenne 素数に替えても同じように進む。逆に、偶数の完全数はこの形しかないことも示せる。

偶数の完全数

偶数 $n$ について、次の 2 つは同値である。
(R1) $n$ は完全数である。
(R1) $2$ 以上のある整数 $k$ について $M_k=2^k-1$ が素数であり、$n=2^{k-1}(2^k-1)$ と書ける。

条件 (ii) の $k$ は、実は素数である（thm-pmp-mersenne (1)）。そこで条件 (ii) を「素数 $p$ について $2^p-1$ が素数で、$n=2^{p-1}(2^p-1)$」と書いてもよい。

方針：(ii) ⇒ (i) は rem-pmp-sigma-facts の乗法性で $\sigma(n)$ を計算するだけである。(i) ⇒ (ii) は、$n$ を「$2$ の累乗」と「奇数」の積に分け、$\sigma(n)=2n$ から奇数の部分の約数が 2 つしかないことを導く。
段 1（(ii) ⇒ (i)）。$q=2^k-1$ とおく。$q$ は素数で、奇数なので $2$ で割り切れない。よって $2^{k-1}$ と $q$ は互いに素である。rem-pmp-sigma-facts と prop-pmp-sigma-power-of-two により
$$ \sigma(n)=\sigma(2^{k-1})\,\sigma(q)=(2^k-1)(1+q)=q\cdot2^k=2\cdot2^{k-1}q=2n $$
である。$n$ は完全数である。
段 2（(i) ⇒ (ii)：$n$ を分ける）。$n$ を偶数の完全数とする。$n$ を $2$ で割り切れるだけ割り、$n=2^{k-1}m$（$m$ は奇数）と書く。$n$ は偶数なので $k-1\ge1$、つまり $k\ge2$ である。$2^{k-1}$ と奇数 $m$ は互いに素なので、rem-pmp-sigma-facts と prop-pmp-sigma-power-of-two により
$$ \sigma(n)=\sigma(2^{k-1})\,\sigma(m)=(2^k-1)\,\sigma(m) $$
である。一方 $n$ は完全数なので $\sigma(n)=2n=2^km$ である。2 つを合わせて
$$ (2^k-1)\,\sigma(m)=2^k\,m $$
を得る。
段 3（$2^k-1$ は $m$ を割る）。$2^k-1$ と $2^k$ の公約数は、差 $2^k-(2^k-1)=1$ を割るので $1$ だけであり、$2^k-1$ と $2^k$ は互いに素である。段 2 の式から $2^k-1$ は $2^km$ を割るので、整数の割り算と互除法の系「互いに素な数による割り算」により $2^k-1$ は $m$ を割る。$m=(2^k-1)M$（$M$ は正の整数）と書く。これを段 2 の式に代入すると $(2^k-1)\,\sigma(m)=2^k(2^k-1)M$ で、両辺を $2^k-1$ で割って
$$ \sigma(m)=2^kM=(2^k-1)M+M=m+M $$
を得る。
段 4（$m$ は素数で $M=1$）。$k\ge2$ なので $2^k-1\ge3$ であり、$M<3M\le(2^k-1)M=m$ である。よって $m$ と $M$ は $m$ の相異なる 2 つの正の約数で、その和 $m+M$ が段 3 により $\sigma(m)$（$m$ のすべての正の約数の和）に等しい。したがって $m$ の正の約数は $m$ と $M$ の 2 つだけである。$1$ は $m$ の約数なので $1$ は $m$ か $M$ に等しく、$m\ge3$ なので $M=1$ である。すると $m$ の正の約数は $1$ と $m$ だけで、$m$ は素数である。$m=(2^k-1)\cdot1=2^k-1$ なので、$2^k-1$ は素数で $n=2^{k-1}(2^k-1)$ である。$\square$

496 = 2⁴・31 の約数を 2 行 5 列に並べた表。上の行は 2 の累乗 1, 2, 4, 8, 16 で和は 31、下の行はその 31 倍で和は 31・31。全体の和は 31・32 = 992 = 2・496
図 2 は、段 1 の計算を $n=496=2^4\cdot31$ で見たものである。$496$ の約数は、$2$ の累乗 $1,2,4,8,16$ と、それぞれに $31$ を掛けたもので、全部で $10$ 個ある。上の行の和は $\sigma(16)=31$、下の行の和はその $31$ 倍なので、全体の和は $31\cdot(1+31)=31\cdot32=992$ である。$2$ の累乗の和がちょうど $31$ になり、下の行の $31$ 倍と合わせて $32=2^5$ 倍になることが、$\sigma(n)=2n$ を生んでいる。

定理を使う

証明の段 2〜4 を $496$ でたどる

$n=496$ から出発して、証明の段 2〜4 と同じ計算をする。
(1) 段 2。$496$ を $2$ で割り続けると $248,124,62,31$ で、$496=2^4\cdot31$ である。$k=5$、$m=31$ で、$\sigma(496)=(2^5-1)\,\sigma(31)=31\cdot32=992=2\cdot496$ なので、$(2^5-1)\,\sigma(31)=2^5\cdot31$ が成り立っている。
(2) 段 3。$2^5-1=31$ は $m=31$ を割り、$M=1$ である。$\sigma(31)=32=31+1=m+M$ である。
(3) 段 4。$31$ の約数は $31$ と $1$ だけで、$31$ は素数である。

5 番目の完全数

$2^{13}-1=8191$ は素数である（ex-pmp-8191 で確かめる）。thm-pmp-even の段 1 により
$$ n=2^{12}\cdot8191=4096\cdot8191=33550336 $$
は完全数である。実際 $\sigma(n)=(2^{13}-1)\cdot8192=8191\cdot8192=67100672=2\cdot33550336$ である。
ex-pmp-start-mersenne の表で $M_{11}=2047$ が素数でなかったので、$2^{10}\cdot2047$ は完全数ではない。$8128$ の次の偶数の完全数は $33550336$ である。

thm-pmp-even により、偶数の完全数と Mersenne 素数は 1 対 1 に対応する。Mersenne 素数 $2^p-1$ が 1 つ見つかるごとに、偶数の完全数 $2^{p-1}(2^p-1)$ が 1 つ見つかる。Cri24 によれば、(ii) ⇒ (i) は Euclid の『原論』にあり、(i) ⇒ (ii) は Euler が示した。

偶数の完全数は三角数

$q=2^p-1$ とおくと
$$ 1+2+\dots+q=\frac{q(q+1)}2=\frac{(2^p-1)\cdot2^p}2=2^{p-1}(2^p-1) $$
なので、偶数の完全数は $1$ から Mersenne 素数 $q$ までの和になっている。たとえば $28=1+2+\dots+7$、$496=1+2+\dots+31$ である（Cri24 の演習にある）。

主定理 2：Mersenne 数の約数

2 つの補題

ex-pmp-mersenne-small (2) で、$M_6=63$ が $M_2=3$ と $M_3=7$ で割り切れたのは、次の因数分解による。

$x^{ab}-1$ の因数分解

正の整数 $a,b$ と実数 $x$ について
$$ x^{ab}-1=(x^a-1)\bigl(x^{a(b-1)}+x^{a(b-2)}+\dots+x^a+1\bigr) $$
である。右辺の 2 つ目の括弧は、$x^a$ の $0$ 乗から $b-1$ 乗までの $b$ 個の和である。

方針：$y=x^a$ とおき、$y^b-1$ の因数分解に帰着させる。
段 1（置き換える）。$y=x^a$ とおくと $x^{ab}=(x^a)^b=y^b$ なので、示す式は $y^b-1=(y-1)(y^{b-1}+y^{b-2}+\dots+y+1)$ である。
段 2（展開する）。右辺を展開すると
$$ (y-1)(y^{b-1}+\dots+y+1)=\underbrace{(y^b+y^{b-1}+\dots+y)}_{y\text{ を掛けた分}}-\underbrace{(y^{b-1}+\dots+y+1)}_{1\text{ を掛けた分}} $$
で、$y^{b-1},\dots,y$ が打ち消し合い、$y^b-1$ が残る。$\square$

$x=2$ とおくと $M_{ab}=M_a\cdot(2^{a(b-1)}+\dots+2^a+1)$ で、$M_a$ は $M_{ab}$ を割る。$b$ と $a$ の役割を入れかえれば $M_b$ も $M_{ab}$ を割る。$x^{ab}-1$ のような式の因数分解は因数分解の技法と既約性でも扱っている。
2 つ目の補題は、冪の余りの周期と元の位数の定理「位数と指数の関係」の一部である。証明が短いので、ここでも示しておく。

位数と指数

$q$ を素数、$a$ を $q$ で割り切れない整数とする。$a^d\equiv1\pmod q$ となる最小の正の整数 $d$（$a$ の法 $q$ での位数）が存在し、正の整数 $k$ について
$$ a^k\equiv1\pmod q\iff d\text{ は }k\text{ を割る} $$
である。

方針：Fermat の小定理で $d$ があることを確かめ、$k$ を $d$ で割った余りを調べる。
段 1（$d$ がある）。Fermatの小定理と冪の余りの定理「Fermat の小定理の主張」により $a^{q-1}\equiv1\pmod q$ なので、$a^k\equiv1$ となる正の整数 $k$ は少なくとも 1 つある（$k=q-1$）。正の整数の集まりには最小のものがあるので、$d$ が存在する。
段 2（⇐）。$k=dt$ と書けるなら $a^k=(a^d)^t\equiv1^t=1$ である。
段 3（⇒）。$a^k\equiv1$ とする。$k$ を $d$ で割って $k=dt+r$（$0\le r< d$）とすると、$a^k=(a^d)^t\,a^r\equiv a^r$ なので $a^r\equiv1$ である。$r\ge1$ なら、$d$ より小さい正の整数 $r$ で $a^r\equiv1$ となり、$d$ が最小であることに反する。よって $r=0$ で、$d$ は $k$ を割る。$\square$

$2$ の法 $23$ での位数

$2$ の累乗を $23$ で割った余りを順に書くと
$$ 2^0,2^1,\dots,2^{11}\equiv1,\ 2,\ 4,\ 8,\ 16,\ 9,\ 18,\ 13,\ 3,\ 6,\ 12,\ 1\pmod{23} $$
である（前の余りを $2$ 倍して $23$ で割った余りをとる。たとえば $16\cdot2=32=23+9$）。初めて $1$ に戻るのは $2^{11}$ なので、位数は $d=11$ である。Fermat の小定理の指数 $22$ は $11$ の倍数で、lem-pmp-order のとおりである。$2^{11}\equiv1\pmod{23}$ は、$23$ が $2^{11}-1=2047$ を割ることにほかならない。

2 の累乗を 23 で割った余り 1, 2, 4, 8, 16, 9, 18, 13, 3, 6, 12 を円周上の 0 から 22 の目盛りで順に結んだ図。11 回で 1 に戻り、11 個の余りしか通らない
図 3 は ex-pmp-order-23 の余りを、$0$ から $22$ の目盛りを打った円周の上で順に結んだものである。$2$ の累乗の余りは $11$ 回で $1$ に戻り、$1$ から $22$ までの $22$ 個の余りのうち半分の $11$ 個しか通らない。

定理と証明

Mersenne 数の約数

$2$ 以上の整数 $n$ について、$M_n=2^n-1$ が素数ならば $n$ は素数である。
$p$ を奇数の素数とする。$M_p=2^p-1$ を割る素数 $q$ は、すべて $q\equiv1\pmod{2p}$ を満たす。つまり $q=2pt+1$（$t$ は正の整数）の形である。

方針：(1) は対偶を示す。$n$ が合成数なら lem-pmp-factor で $M_n$ の約数を作る。(2) は $2$ の法 $q$ での位数が $p$ であることを示し、Fermat の小定理と lem-pmp-order で $p$ が $q-1$ を割ることを導く。
段 1（(1)：$n$ が合成数の場合）。$n$ が素数でないとすると、$n=ab$（$a,b$ は $2$ 以上の整数）と書ける。このとき $2\le a< n$ である。lem-pmp-factor で $x=2$ とおくと $M_a$ は $M_n$ を割る。$a\ge2$ なので $M_a\ge3$ であり、$a< n$ なので $M_a< M_n$ である。$M_n$ は $1$ でも自分自身でもない約数 $M_a$ をもつので、素数でない。対偶をとって (1) を得る。
段 2（(2)：$q$ は奇数）。$M_p=2^p-1$ は奇数なので、その約数 $q$ も奇数であり、$q\ne2$ である。特に $2$ は $q$ で割り切れない。
段 3（(2)：位数は $p$）。$q$ は $2^p-1$ を割るので $2^p\equiv1\pmod q$ である。$2$ の法 $q$ での位数を $d$ とすると、lem-pmp-order により $d$ は $p$ を割る。$p$ は素数なので $d=1$ か $d=p$ である。$d=1$ なら $2\equiv1\pmod q$、つまり $q$ が $1$ を割ることになり、$q\ge3$ に反する。よって $d=p$ である。
段 4（(2)：$p$ は $q-1$ を割る）。段 2 により $2$ は $q$ で割り切れないので、Fermat の小定理により $2^{q-1}\equiv1\pmod q$ である。lem-pmp-order により、位数 $d=p$ は $q-1$ を割る。$q-1=pu$（$u$ は正の整数）と書く。
段 5（(2)：$2p$ は $q-1$ を割る）。$q$ は奇数なので $q-1=pu$ は偶数である。$p$ は奇数なので $2$ と $p$ は互いに素で、$2$ が $pu$ を割ることから整数の割り算と互除法の系「互いに素な数による割り算」により $2$ は $u$ を割る。$u=2t$ と書くと $q-1=2pt$、つまり $q\equiv1\pmod{2p}$ である。$\square$

の条件を満たす数 $2p+1,\ 4p+1,\ 6p+1,\dots$ がすべて $M_p$ の約数になるわけではない。(2) は「$M_p$ の素因数を探すなら、この候補だけを調べればよい」という形で使う。

素因数の候補を絞る

$M_p$ が素数かどうかを割り算で調べるには、$\sqrt{M_p}$ 以下の素数で割ってみればよい。$M_p$ が合成数なら $M_p=ab$（$2\le a\le b$）と書け、$a^2\le ab=M_p$ から $a\le\sqrt{M_p}$ で、$a$ の素因数も $\sqrt{M_p}$ 以下だからである。thm-pmp-mersenne (2) により、調べる素数は $2pt+1$ の形のものだけでよい。

$2^{11}-1=2047$ の素因数

$p=11$ なので、素因数の候補は $22t+1$ の形の数 $23,45,67,89,\dots$ である。最初の候補 $23$ は素数で、$2047=23\cdot89$ と割り切れる（ex-pmp-order-23 の $2^{11}\equiv1\pmod{23}$ と同じことである）。もう一方の $89$ も $89=22\cdot4+1$ で、(2) のとおり $22t+1$ の形をしている。$p=11$ は素数だが、$M_{11}$ は素数でない。

$2^{13}-1=8191$ は素数

$p=13$ なので、素因数の候補は $26t+1$ の形の数である。$\sqrt{8191}\approx90.5$ なので、$90$ 以下の候補 $27,53,79$ を調べればよい。$27=3^3$ は素数でないので除く。残りは
$$ 8191=53\cdot154+29,\qquad 8191=79\cdot103+54 $$
で、どちらも割り切れない。$8191$ は $\sqrt{8191}$ 以下の素因数をもたないので素数である。$1$ から $90$ までの素数 $24$ 個をすべて試す代わりに、$2$ 回の割り算で済んだ。

$2^{23}-1$ の素因数

$p=23$ なので、素因数の候補は $46t+1$ の形の数である。最初の候補 $47$ は素数で、$8388607=47\cdot178481$ と割り切れる。

もう一方の因数の形と、割り算の確かめを開く

$47\cdot178481=47\cdot178000+47\cdot481=8366000+22607=8388607$ である。$178481-1=178480=46\cdot3880$ なので、$178481$ も $46t+1$ の形である（$178481$ が素数であることは計算機で確かめた）。

$p$ が $31$ までの Mersenne 数をまとめると、次の表になる（素因数分解は計算機で確かめた）。

$p$	$M_p=2^p-1$	素数か	素因数分解	対応する完全数
$2$	$3$	素数	$3$	$6$
$3$	$7$	素数	$7$	$28$
$5$	$31$	素数	$31$	$496$
$7$	$127$	素数	$127$	$8128$
$11$	$2047$	合成数	$23\cdot89$	—
$13$	$8191$	素数	$8191$	$33550336$
$17$	$131071$	素数	$131071$	$8589869056$
$19$	$524287$	素数	$524287$	$137438691328$
$23$	$8388607$	合成数	$47\cdot178481$	—
$29$	$536870911$	合成数	$233\cdot1103\cdot2089$	—
$31$	$2147483647$	素数	$2147483647$	$2305843008139952128$

合成数になった行の素因数は、どれも $2p$ で割って $1$ 余る。たとえば $p=29$ では $233=58\cdot4+1$、$1103=58\cdot19+1$、$2089=58\cdot36+1$ である。

例と反例

2 つの主定理の条件を外すと、何が成り立たなくなるかを表にまとめる。

外す条件	反例	成り立たなくなること
thm-pmp-mersenne (1) の向き（$M_n$ が素数 ⇒ $n$ が素数）	$n=11$：$M_{11}=23\cdot89$	逆向きの「$n$ が素数 ⇒ $M_n$ が素数」
Mersenne 数の底が $2$	$3^p-1$（$p\ge2$）は偶数	指数が素数なら素数になりうること
(2) の $p$ が奇数	$p=2$：$M_2=3$	$q\equiv1\pmod{2p}$（$3\not\equiv1\pmod4$）
(2) の $p$ が素数	$n=6$：$M_6=3^2\cdot7$	$q\equiv1\pmod{2n}$（$7\not\equiv1\pmod{12}$）
thm-pmp-even の「$2^k-1$ が素数」	$k=4$：$2^3\cdot15=120$	$n=2^{k-1}(2^k-1)$ が完全数であること
thm-pmp-even の「$n$ は偶数」	奇数の完全数	分かっていない（反例も証明もない）

反例：$p=11$ でも $M_{11}$ は合成数

ex-pmp-2047 のとおり $M_{11}=2047=23\cdot89$ である。thm-pmp-mersenne (1) は「$n$ が素数でなければ $M_n$ は素数でない」と言っているだけで、「$n$ が素数なら $M_n$ は素数」とは言っていない。表のとおり $p=23$、$p=29$ でも $M_p$ は合成数である。

反例：底を $3$ にすると素数にならない

$3^2-1=8$、$3^3-1=26$、$3^5-1=242$ はどれも偶数である。一般に $3^n$ は奇数なので $3^n-1$ は偶数で、$n\ge2$ なら $3^n-1\ge8>2$ だから素数でない。$x^n-1$（$x\ge2$、$n\ge2$）の形で素数になりうるのは $x=2$ のときだけで、Mersenne 数の底が $2$ なのはこのためである。

底が $3$ 以上なら素数にならない理由を開く

$a\ge3$ の整数と $n\ge2$ について、lem-pmp-factor で $x=a$、指数を $1\cdot n$ とみると $a^n-1=(a-1)(a^{n-1}+\dots+a+1)$ である。$a-1\ge2$ で、2 つ目の因数は $a+1$ 以上なので $4$ 以上であり、$a^n-1$ は $1$ でも自分自身でもない約数 $a-1$ をもつ。よって $a^n-1$ は素数でない。

反例：$p=2$ と、指数が合成数の場合

$p=2$ では $M_2=3$ で、$3$ を $2p=4$ で割った余りは $3$ である。thm-pmp-mersenne の証明の段 5 で「$p$ は奇数なので $2$ と $p$ は互いに素」を使ったが、$p=2$ ではこれが成り立たない。段 4 までの「$p$ は $q-1$ を割る」は $p=2$ でも成り立っている（$2$ は $3-1=2$ を割る）。
指数 $n=6$ は素数でない。$M_6=63=3^2\cdot7$ で、$7-1=6$ は $12$ で割り切れない。$2$ の法 $7$ での位数は $3$ で（$2^3=8\equiv1\pmod7$）、$6$ そのものではない。証明の段 3 で「$d$ は $p$ を割るので $d=1$ か $d=p$」と言えたのは $p$ が素数だからで、$n=6$ では $d=3$ のような途中の約数が現れる。$M_4=15=3\cdot5$ でも $3-1=2$ は $8$ で割り切れない。

反例：$2^k-1$ が素数でないとき

$k=4$ では $2^k-1=15$ は素数でない。$n=2^3\cdot15=120$ とすると、$120=2^3\cdot3\cdot5$ なので
$$ \sigma(120)=\sigma(8)\,\sigma(3)\,\sigma(5)=15\cdot4\cdot6=360=3\cdot120 $$
で、$\sigma(120)\ne2\cdot120$ である。$120$ は完全数でない。
同じ型の 2 例目（$k=6$）を開く
(2) $k=6$ では $n=2^5\cdot63=2016$ で、$\sigma(2016)=\sigma(32)\,\sigma(63)=63\cdot104=6552\ne4032$ である（$\sigma(63)=\sigma(9)\,\sigma(7)=13\cdot8=104$）。
$2^k-1$ が素数でないと、$\sigma(2^k-1)$ は $1+(2^k-1)=2^k$ より大きくなり（$k=4$ では $\sigma(15)=24>16$）、$\sigma(n)$ が $2n$ を超える。thm-pmp-even の段 1 で $\sigma(q)=1+q$ を使えたのは $q$ が素数だからである。

奇数の完全数

thm-pmp-even は偶数の完全数についての定理で、奇数の完全数については何も言っていない。奇数の完全数があるかどうかは分かっておらず、Mos11 の古典的な未解決問題の表にも挙がっている。Mersenne 素数が無限にあるかどうかも、同じ表に挙がっている未解決の問題である（Mersenne素数、完全数）。

大学数学で見る：乗法群の位数と Lucas–Lehmer 判定法

lem-pmp-order と Fermat の小定理を合わせた「位数は $q-1$ を割る」は、大学数学では群の言葉で述べられる。$q$ を法とする $0$ 以外の余り $1,2,\dots,q-1$ は、掛け算について群（乗法群 $(\mathbb{Z}/q\mathbb{Z})^\times$）をなし、その元の個数は $q-1$ である。$2$ の累乗の余り全体は、その中の元の個数 $d$ の部分群で、Lagrange の定理（部分群の元の個数は全体の元の個数を割る。Lagrangeの定理）から $d$ は $q-1$ を割る。図 3 の $11$ 個の余りは、$22$ 個の余りの中の部分群である。

素因数の候補をさらに絞る条件と、Lucas–Lehmer 判定法を開く

(1) 素因数の候補は、さらに絞れる。$p$ が奇数の素数なら、$M_p$ の素因数 $q$ は $8$ で割って $1$ か $7$ 余る（Mersenne素数の命題「Mersenne数の素因数の合同条件」。証明には平方剰余の第 2 補充法則を使い、この記事では証明しない）。ex-pmp-2047 の $23$ と $89$ は $8$ で割って $7$ と $1$ 余る。

(2) $M_p$ が素数かどうかを、割り算を使わずに判定する方法がある。$s_0=4$、$s_{k+1}=s_k^2-2$ で数の列を作ると、奇数の素数 $p$ について「$M_p$ が素数 ⇔ $M_p$ が $s_{p-2}$ を割る」が成り立つ（Lucas–Lehmer 判定法。Mersenne素数の定理「Lucas–Lehmerの判定法」、Ste17 §2.4 の計算例。この記事では証明しない）。$p=5$ では、$31$ で割った余りをとりながら計算すると $s_0=4$、$s_1=14$、$s_2=194\equiv8$、$s_3\equiv8^2-2=62\equiv0\pmod{31}$ で、$M_5=31$ は素数である。$p=11$ では $s_9\equiv1736\not\equiv0\pmod{2047}$ で、$M_{11}$ は素数でない。

演習

$2^{17}-1$ は素数か

$2^{17}-1=131071$ が素数であることを、thm-pmp-mersenne (2) を使って確かめよ。$\sqrt{131071}\approx362.04$ を使ってよい。

解答を開く

$p=17$ なので、素因数の候補は $34t+1$ の形の数である。$362$ 以下の候補は $35,69,103,137,171,205,239,273,307,341$ で、このうち素数は $103,137,239,307$ である（$35=5\cdot7$、$69=3\cdot23$、$171=9\cdot19$、$205=5\cdot41$、$273=3\cdot7\cdot13$、$341=11\cdot31$）。$131071$ をこれらで割ると、余りは順に $55,99,99,289$ で、どれも割り切れない。よって $131071$ は素数で、$2^{16}\cdot131071=8589869056$ は完全数である。

$2^{29}-1$ の最小の素因数

$2^{29}-1=536870911$ の最小の素因数を、thm-pmp-mersenne (2) の候補を小さい順に調べて求めよ。

解答を開く

候補は $58t+1$ の形の数 $59,117,175,233,\dots$ である。$59$ は素数だが、$536870911=59\cdot9099506+57$ で割り切れない。$117=9\cdot13$、$175=25\cdot7$ は素数でないので除く。$233$ は素数で、$536870911=233\cdot2304167$ と割り切れる。最小の素因数は $233$ である。

さらに先へ

完全数の定義を広げて、$\sigma(n)=3n$ となる数を考えることもある。ex-pmp-cx-120 の $120$ はその例である（完全数の注意「過剰数・不足数との比較」も参照）。
thm-pmp-mersenne (2) と同じ論法で、$2^{2^m}+1$ の形の数（Fermat 数）の素因数も $2^{m+1}t+1$ の形に限ることが示せる（Fermat数）。
$\gcd(2^m-1,2^n-1)=2^{\gcd(m,n)}-1$ が成り立つ（Mersenne素数の命題「Mersenne数の最大公約数」。この記事では証明しない）。たとえば $\gcd(63,15)=3=2^{\gcd(6,4)}-1$ である。指数どうしの互除法が、Mersenne 数どうしの互除法になる。同じ形の性質は Fibonacci 数でも成り立つ（Fibonacci数の整数の性質）。
lem-pmp-order の「位数」の考え方は、Wilsonの定理（高校数学）や RSA暗号（高校数学）でも、素数を法とする余りの性質を調べる道具として使う。