Mersenne素数

まず、$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=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$

prop-mersenne-prime-gcd により $\gcd(M_m,M_n)=M_{\gcd(m,n)}=M_1=1$ である。$\square$

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$

$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$

$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$

$\sqrt3$ は無理数なので、実数 $a+b\sqrt3$（$a,b\in\mathbb{Z}$）の全体 $\mathbb{Z}[\sqrt3]$ では表し方 $(a,b)$ が一意であり、$\mathbb{Z}[\sqrt3]$ は足し算と掛け算で閉じた環である。$\omega:=2+\sqrt3$、$\bar\omega:=2-\sqrt3$ とおくと $\omega\bar\omega=4-3=1$ である。
まず、すべての $k\geq0$ について
$$ s_k=\omega^{2^k}+\bar\omega^{2^k} $$
であることを $k$ に関する数学的帰納法で示す。$k=0$ では $\omega+\bar\omega=4=s_0$ である。$k$ で成り立つとすると、$\omega\bar\omega=1$ から
$$ s_{k+1}=s_k^2-2=\omega^{2^{k+1}}+2(\omega\bar\omega)^{2^k}+\bar\omega^{2^{k+1}}-2=\omega^{2^{k+1}}+\bar\omega^{2^{k+1}} $$
となる。
$M_p\mid s_{p-2}$ と仮定し、$M_p$ が合成数であったとする。$M_p$ の最小の素因数を $q$ とすると、$M_p$ は $q$ 以上の素因数を少なくとも 2 つ（重複を込めて）もつので $q^2\leq M_p$ である。また $M_p$ は奇数なので $q\geq3$ である。
$R:=\mathbb{Z}[\sqrt3]/q\mathbb{Z}[\sqrt3]$ を、$a+b\sqrt3$ の $a,b$ を $q$ で割った余りだけで考えた環とする。$R$ の元は $0\leq a,b< q$ の $a+b\sqrt3$ で代表され、ちょうど $q^2$ 個ある。$R$ の単元（掛け算について逆元をもつ元）の全体 $R^\times$ は掛け算について群をなし、$0\notin R^\times$ なので $|R^\times|\leq q^2-1$ である。$\omega\bar\omega=1$ なので $\omega$ の像は $R^\times$ に属する。以下、$\omega,\bar\omega$ の $R$ での像も同じ記号で書く。
$q\mid M_p\mid s_{p-2}$ なので、$R$ において $\omega^{2^{p-2}}+\bar\omega^{2^{p-2}}=0$ である。両辺に $\omega^{2^{p-2}}$ を掛け、$(\omega\bar\omega)^{2^{p-2}}=1$ を使うと
$$ \omega^{2^{p-1}}=-1 $$
を得る。両辺を 2 乗して $\omega^{2^p}=1$ である。$d$ を $R^\times$ における $\omega$ の元の位数とすると、$d$ は $2^p$ を割るので $d=2^j$（$0\leq j\leq p$）の形である。$j\leq p-1$ なら $\omega^{2^{p-1}}=1$ となり、$-1=1$、すなわち $R$ で $2=0$ となる。これは $q\mid2$ を意味し、$q\geq3$ に反する。よって $d=2^p$ である。
位数 $d$ の元の冪 $\omega^0,\omega^1,\dots,\omega^{d-1}$ は $R^\times$ の相異なる元なので、$2^p=d\leq|R^\times|\leq q^2-1\leq M_p-1=2^p-2$ となり矛盾する。したがって $M_p$ は素数である。$\square$