[定義]p∈Nとし、の形の数をメルセンヌ数という。
[定義]Mpが素数の場合はメルセンヌ素数、そうではない場合はメルセンヌ合成数という。
[定理]Mpが(メルセンヌ)素数のときは、pも素数になる。
[証明]pが合成数と仮定する(背理法)。
p=abとすると、Mpは次のように展開できる。
a>1、b>1ならば、右辺の両因数は1よりも大きい。よって、Mpは合成数である。これは矛盾。 □
この定理の逆は必ずしも成り立たない。つまり、pが素数であっても、Mp=2p-1が素数とは限らない。
p | メルセンヌ数Mp | 素数か否か |
2 | 3 | 素数 |
3 | 7 | 素数 |
5 | 素数 | |
7 | 素数 | |
11 | 2047=23×89 | 素数でない |
13 | 素数 | |
17 | 素数 | |
19 | 素数 | |
23 | 素数でない |
[未解決問題]
(1)無限に多くのメルセンヌ素数があるか?
(2)無限に多くのメルセンヌ合成数があるか?
メルセンヌ数は2n-1の形になっている。nが偶数2kの場合は、次のように展開できる。
よって、この場合の素因数分解をするためには、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
←(*)
そのようなmを1つ決めておく。
となるような最小のnの範囲を調べる。
(*)の両辺を2乗すると、次が成り立つ。
よって、nは最小としているので、n≦2mが成り立つ。
ここで、nを奇数と仮定する。
すると、n<2mである。
また、2mをnで割ったときの商をq、余りをrとすると、次が成り立つ。
すると、次のように展開できる。
(∵
)
ここで、nの最小性より、r=0でなければならない。
そうでないと、nより小さいべきr>0に対して、となって矛盾するため。
よって、2m=qnが成り立つ。
なお、amは次のように展開できるが、p>2としたので、これは(*)と矛盾する。
(∵nが奇数と仮定したので、nはmを割り切る)
(∵
)
ゆえに、nは偶数である。
[2]←を示す。
p|an-1となる最小のnが偶数ならば、n=2kとおく。
ここで、かつ
(k<nとnの最小性より)であるため、
である。
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(奇数)が存在することになってしまう。 ◇