インテジャーズ

INTEGERS

数、特に整数に関する記事。

メルセンヌ数

自然数nに対してM_n:=2^n-1Mersenne数といいます。素数であるようなMersenne数のことをMersenne素数といいます。
127=M_7はMersenne素数です。ちなみに、

\begin{align}&M_2=3, M_3=7, M_7=127,\\ &M_{127}=170141183460469231731687303715884105727\end{align}

は全てMersenne素数です。

2^{ab}-1=(2^a-1)(2^{a(b-1)}+\cdots +2^a+1)

なので、M_nが素数ならばnは素数でなければならないことが分かります。しかしながら、nが素数であってもM_nが素数であるとは限りません(M_{11}=23\times 89)。

Mersenneはn \leq 257に対してM_nが素数になるのは

n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257

のときだけであると予想したそうです。実際には彼の予想は誤りで、Mersenne素数M_{61}, M_{89}, M_{107}が抜けており、M_{67}, M_{257}は合成数です。

伝説の講演

Cole賞で名前が残っているColeがM_{67}の素因数分解を1903年10月31日*1にニューヨークで開かれたアメリカ数学会で発表しました(合成数であることは1876年にLucasによって示されていました)。

Coleは黒板にM_{67}の値

147573952589676412927

を書き、続いて

193707721 \times 761838257287

と書きました。そうして、手計算で両者が一致することを示し、着席したそうです。その間、約一時間、一言も喋らず。着席後、会場は拍手に包まれたそうです。

Mersenne数の例

\begin{align}M_0&=0
\\ M_1&=1
\\ M_2&=3
\\ M_3&=7
\\ M_4&=15=3\times 5
\\ M_5&=31
\\ M_6&=63=3^2\times 7
\\ M_7&=127
\\ M_8&=255=3\times 5\times 17
\\ M_9&=511=7\times 73
\\ M_{10}&=1023=3\times 11\times 31
\\ M_{11}&=2047=23\times 89
\\ M_{12}&=4095=3^2\times 5\times 7\times 13
\\ M_{13}&=8191
\\ M_{14}&=16383=3\times 43\times 127
\\ M_{15}&=32767=7\times 31\times 151
\\ M_{16}&=65535=3\times 5\times 17\times 257
\\ M_{17}&=131071
\\ M_{18}&=262143=3^3\times 7\times 19\times 73
\\ M_{19}&=524287
\\ M_{20}&=1048575=3\times 5^2\times 11\times 31\times 41
\\ M_{21}&=2097151=7^2\times 127\times 337
\\ M_{22}&=4194303=3\times 23\times 89\times 683
\\ M_{23}&=8388607=47\times 178481
\\ M_{24}&=16777215=3^2\times 5\times 7\times 13\times 17\times 241
\\ M_{25}&=33554431=31\times 601\times 1801
\\ M_{26}&=67108863=3\times 2731\times 8191
\\ M_{27}&=134217727=7\times 73\times 262657
\\ M_{28}&=268435455=3\times 5\times 29\times 43\times 113\times 127
\\ M_{29}&=536870911=233\times 1103\times 2089
\\ M_{30}&=1073741823=3^2\times 7\times 11\times 31\times 151\times 331
\\ M_{31}&=2147483647
\\ M_{32}&=4294967295=3\times 5\times 17\times 257\times 65537,\dots \end{align}

発見されているMersenne素数

M_{2}, M_{3}, M_{5}, M_{7}, M_{13}, M_{17}, M_{19}, M_{31}, M_{61}, M_{89}, M_{107}, M_{127}, M_{521}, M_{607},
M_{1279}, M_{2203}, M_{2281}, M_{3217}, M_{4253}, M_{4423}, M_{9689}, M_{9941}, M_{11213}, M_{19937}, M_{21701}, M_{23209}, M_{44497}, M_{86243}, M_{110503}, M_{132049}, M_{216091}, M_{756839}, M_{859433}, M_{1257787}, M_{1398269}, M_{2976221}, M_{3021377}, M_{6972593}, M_{13466917}, M_{20996011}, M_{24036583}, M_{25964951}, M_{30402457}, M_{32582657}, M_{37156667}, M_{42643801}, M_{43112609}, M_{57885161}

の48個が見つかっています。このうち、44番目までは数え漏らしのないことが確認されています。

2016年1月20日追記
新しいMersenne素数が発見されたと宣言されたようです:
integers.hatenablog.com

Lucas-Lehmerテスト

Mersenne数にのみ適用可能な、Lucas-Lehmerテストと呼ばれる特別な素数判定法があります(Lucasの判定法をLehmerが拡張したもの)。

Lucas-Lehmerテスト
pを奇素数とし、数列\{ s_n \}s_0=4, s_n=s_{n-1}^2-2 \ (n \geq 1)で定義する。このとき、M_pが素数となるための必要十分条件はM_ps_{p-2}を割り切ることである。

証明. 証明はs_nの一般項を用いて行う。一般項がs_n=(2+\sqrt{3})^{2^n}+(2-\sqrt{3})^{2^n}で与えられることは数学的帰納法によって容易に確認できる。まず、M_ps_{p-2}を割り切る場合を考える。M_pが合成数であると仮定して矛盾を導く。このとき、

M_p=ab, (a, b \in \mathbb{Z}_{\geq 2}, a^2 \leq M_p)

と仮定してよい。M_ps_{p-2}を割り切るので、ある整数kが存在して

(2+\sqrt{3})^{2^{p-2}}+(2-\sqrt{3})^{2^{p-2}}=ka

と書ける。両辺を(2+\sqrt{3})^{2^{p-2}}倍することによって(2+\sqrt{3})^{2^{p-1}}\equiv -1 \pmod{a}が分かる(合同式は\mathbb{Z}[\sqrt{3}] で考える)。すなわち、2+\sqrt{3}は群G:=(\mathbb{Z}[\sqrt{3}]/a\mathbb{Z}[\sqrt{3}])^{\times}の元として位数2^pである。よって、2^p \leq \# G \leq a^2 \leq M_p = 2^p-1となって矛盾する。

逆に、M_pが素数であると仮定する。平方剰余の相互法則を用いて証明する。\frac{M_p^2-1}{8}は偶数なので、第二補充則によって\left( \frac{2}{M_p} \right) = 1。従って、Eulerの規準により

2^{\frac{M_p-1}{2}} = 2^{2^{p-1}} \equiv 1 \pmod{M_p}-①。

また、M_p=2^p-1 \equiv 3\pmod{4}なので、平方剰余の相互法則により

\left( \frac{M_p}{3} \right) \left( \frac{3}{M_p} \right) = -1

M_p=2^p-1 \equiv (-1)^p-1 =-2 \equiv 1 \pmod{3}

なので、

\left( \frac{3}{M_p} \right) = -1

よって、Eulerの基準より

3^{\frac{M_p-1}{2}} \equiv -1 \pmod{M_p}

今、M_pは素数なので*2

(1+\sqrt{3})^{M_p} \equiv 1+\sqrt{3}^{M_p} \pmod{M_p}

直前の結果により、

(1+\sqrt{3})^{M_p} \equiv 1+3^{\frac{M_p-1}{2}}\sqrt{3} \equiv 1-\sqrt{3} \pmod{M_p}

を得る。両辺1+\sqrt{3}倍することにより、

2^{2^{p-1}}(2+\sqrt{3})^{2^{p-1}} \equiv -2 \pmod{M_p}

((1+\sqrt{3})^2=2(2+\sqrt{3})に注意)。①より

2(2+\sqrt{3})^{2^{p-1}} \equiv -2 \pmod{M_p}

が得られる。2015の階乗を10の502乗で割った数の一の位は? - INTEGERSで紹介したように、2\bmod{M_p}で可逆なので、結局

(2+\sqrt{3})^{2^{p-1}} \equiv -1 \pmod{M_p}

が示された。

(2+\sqrt{3})^{2^{p-1}}(2-\sqrt{3})^{2^{p-2}}=(2+\sqrt{3})^{2^{p-2}}

なので、

(2+\sqrt{3})^{2^{p-2}} \equiv -(2-\sqrt{3})^{2^{p-2}}\pmod{M_p}
となって、最終的に

(2+\sqrt{3})^{2^{p-2}}+(2-\sqrt{3})^{2^{p-2}} \equiv 0 \pmod{M_p}

を得る。これはs_{p-2} \equiv 0 \pmod{M_p}を意味する*3Q.E.D.

Lucas-Lehmerテストの証明はs_nの一般項を利用することが重要でしたが、実際に使う場合は漸化式でどんどん次の値を計算していきます。その際、値を出し切らなくても毎回\bmod{M_p}すれば十分です。

pが小さい場合にはありがたみがあまり伝わらないかもしれませんが、表題の127が素数であることをLucas-Lehmerテストを用いて証明してみましょう:

s_0=4
s_1=14
s_2=194\equiv 67 \pmod{127}
s_3\equiv 4487 \equiv 42 \pmod{127}
s_4\equiv 1762 \equiv 111 \pmod{127}
s_5\equiv 12419 \equiv 97\times 127
より、127は素数であることが分かります。

最大の素数

Lucas-Lehmerテストは優秀な判定法で、Mersenne数は2進法表記で1が並ぶ数ですから、とてもコンピュータ計算と相性がよいものとなっています。というわけで、巨大素数の探索は主にMersenne素数をターゲットに行われています(GIMPS)。現在発見されている最大の素数はM_{57885161}で、17425170桁です(とてつもない大きさ!!)。これが発見されたのが2013年1月25日ですので、もう3年近く記録が更新されていません*4。Lucas-Lehmerテストを実際にプログラミングを組んで試してみることはよい課題だと思いますが、私の守備範囲外ですので、以下の参考になると思われる記事を紹介しておきます:
itchyny.hatenablog.com

*1:天才(1031)の日なので覚えやすいです。

*2:integers.hatenablog.com

*3:tsujimotter氏の記事 tsujimotter.hatenablog.com の解法4がしっかりと身についていれば、後半の証明はスムーズに理解できたと思います。Eulerの規準と平方剰余の相互法則を組み合わせることによってa^{\frac{p-1}{2}}\pmod{p}を計算できることがポイントです(Fermatの小定理より強い)。tsujimotter氏の記事ではこの方法によって素早く3^{10}\equiv 16\pmod{19}が分かりましたが、他の解法でも解けるので必要性がピンとこなかったかもしれません。しかしながら、このように一般論を扱う場合には必要不可欠な論法であることが分かります。

*4:最初の方に追記したように、更新されました。