このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ

目次

メルセンヌ素数

[定義]p∈Nとし、M_p=2^p~-~1の形の数をメルセンヌ数という。

[定義]Mpが素数の場合はメルセンヌ素数、そうではない場合はメルセンヌ合成数という。

[定理]Mpが(メルセンヌ)素数のときは、pも素数になる。

[証明]pが合成数と仮定する(背理法)。

 p=abとすると、Mpは次のように展開できる。

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

 a>1、b>1ならば、右辺の両因数は1よりも大きい。よって、Mpは合成数である。これは矛盾。 □

 この定理の逆は必ずしも成り立たない。つまり、pが素数であっても、Mp=2p-1が素数とは限らない。

pメルセンヌ数Mp素数か否か
23素数
37素数
5素数
7素数
112047=23×89素数でない
13素数
17素数
19素数
23素数でない
  • p=2,3,5,7に対するMpが素数になることは、古くから知られていた。
  • p=13,16,19に対するMpが素数になることは、17世紀初頭に確認された。
  • 1644年にメルセンヌはp=2,3,5,7,13,17,19に加えて、さらにp=31,67,127,257に対するMpが素数であり、p<257である他の自然数pに対するMpは合成数であると主張した。
    • 1世紀以上経った1750年に、オイラーによりp=31に対するMpが合成数であることを発見した。
    • 1903年にアメリカのコロンビア大学の数学者フランク・コールはM67が合成数であることを発見した。
  • 現在、p=67,257に対するメルセンヌの主張は誤りで、さらにp=61,89,107の場合は素数であることがわかっている。
  • リュカはメルセンヌ数が素数かどうかを判定するアルゴリズムを発見した。
    • 20世紀に入ってからD・N・レーマーによってそのアルゴリズムは改良された。

[未解決問題]
(1)無限に多くのメルセンヌ素数があるか?
(2)無限に多くのメルセンヌ合成数があるか?

メルセンヌ数の素因数分解

 メルセンヌ数は2n-1の形になっている。nが偶数2kの場合は、次のように展開できる。

a^n~-~1=a^{2k}~-~1=(a^k~-~1)(a^k~+~1)

 よって、この場合の素因数分解をするためには、ak+1の素因子を知る必要がある。

 そこで、整数a,pを決めておき、p|am+1となるmがあるかどうかを考察する。

[定理]p>2と仮定する。
そのとき、p|am+1となるような整数m(>0)があれば、p|an-1となるような最小の整数n(>0)は偶数である。
逆に、p|an-1となる最小のnが偶数ならば、p|am+1となるような整数mはn/2に等しい。

[証明]

[1]⇒を示す。

p|am+1
a^m~\equiv~-1~\,~\pmod{p} ←(*)

そのようなmを1つ決めておく。

a^n~\equiv~1~\,~\pmod{p}となるような最小のnの範囲を調べる。

(*)の両辺を2乗すると、次が成り立つ。

(a^m)^2~\equiv~(-1)^2~\,~\pmod{p}
a^{2m}~\equiv~1~\,~\pmod{p}

よって、nは最小としているので、n≦2mが成り立つ。

ここで、nを奇数と仮定する。

すると、n<2mである。

また、2mをnで割ったときの商をq、余りをrとすると、次が成り立つ。

2m=qn+r,~0~\le~r~<~n

すると、次のように展開できる。

1
\equiv~a^{2m}
=~a^{qn+r}
=~(a^n)^q~a^r
\equiv~a^r (∵a^n~\equiv~1~\,~\pmod{p}

ここで、nの最小性より、r=0でなければならない。
そうでないと、nより小さいべきr>0に対して、a^r~\equiv~1~\,~\pmod{p}となって矛盾するため。

よって、2m=qnが成り立つ。

なお、amは次のように展開できるが、p>2としたので、これは(*)と矛盾する。

a^m
=~(a^n)^{\frac{m}{n}} (∵nが奇数と仮定したので、nはmを割り切る)
\equiv~1^{\frac{m}{n}} (∵a^n~\equiv~1~\,~\pmod{p}
=~1

ゆえに、nは偶数である。

[2]←を示す。

p|an-1となる最小のnが偶数ならば、n=2kとおく。

a^n~-1~=~a^{2k}~-1~=~(a^k~-1)(a^k~+1)

ここで、a^n~-~1\equiv~0~\,~\pmod{p}かつa^k~-~1~\not{\equiv}~0~\,~\pmod{p}(k<nとnの最小性より)であるため、a^k~+~1~\equiv~0~\,~\pmod{p}である。

k=mとなる。 ←???

よって、n=2k=2mである。即ち、m=n/2が成り立つ。 □

[補講]この定理において、p>2という仮定は必要である。

もし、p=2、a=3、m=1とすると、p|am+1は成り立つが、p|an-1を満たすnとしてn=1(奇数)が存在することになってしまう。 ◇

参考文献

  • 『16歳のアセラが挑んだ世界最強の暗号』
  • 『工科系のための初等整数論入門 公開鍵暗号をめざして』
  • 『なっとくするオイラーとフェルマー』