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

目次

はじめに

 メルセンヌ数に似ているものとして、2p+1という形を考えることができる。

 2p+1が素数となるのは、p=2n(n≧0)となる場合に限られる。なぜならば、奇数kによりp=ek、e∈Nと表されたとすると次のように分解でき、k>1なら右辺の両因数は1よりも大きいからである。

2^p~+~1
=(2^e)^k~+~1
=(2^e~+~1)~\{~(2^e)^{k-1}~-~(2^e)^{k-2}~+~\cdots~-~2^e~+~1\}

 よって、この形で新しい素数を見つけようとするなら、p=2nの場合を考えればよい。

フェルマー数

 フェルマーはam+1の形において、a=2の場合、即ち2m+1が素数かどうかという問題について考えた。

[定理]mが奇数dで割り切れるとすると、2m+1は素数ではない。

[証明]もし、mが奇数dで割り切れるとすると、次のように分解できてしまう。

2^m~+~1
=2^{ed}~+~1 (∵mが奇数dで割り切れるので、m=deとおいた)
={2^e}^d~+~1
=N^d~+~1 (∵N:=2eとおく)
=(N-1)(N^{d-1}~-~N^{d-2}~-~\cdots~-~N~+1) (∵dが奇数なので分解できる。dが偶数だと分解できない)

よって、mが奇数dで割り切れるとすると、2m+1は素数ではない。 □

 そこで、mに奇数の約数がない場合、即ちm=2rの形をしている場合を考察すればよい。

[定義]2^{2^r}+1(r≧0)の形の数をフェルマー数と呼ぶ。
この値をFrと表記する。

[定義]フェルマー数が素数のときフェルマー素数、合成数のときフェルマー合成数という。

 17世紀にフェルマーはFnはすべて素数になると予想した。しかし、1732年にオイラーはF5が641で割り切れることを発見した。よって、F5は合成数である。

F_5~=~2^2^5~+~1=2^32~+~1=4294967297~=641~\times~6700417

[未解決問題]
(1)無限に多くのフェルマー素数があるか?
(2)無限に多くのフェルマー合成数があるか?

フェルマー数を割り切る素数の形を考察する

 F_r~=~2^{2^r}+1を割り切る素数pを1つ考える(Frが素数ならば当然p=Fr)。

[定理]フェルマー数を割り切る素数pは次の形を持つ。
p~=~2^{r+1}~l~+~1(l:整数)

[証明]

p~|~F_r
F_r~\equiv~0~\,~\pmod{p}
2^{2^r}+1~\equiv~0~\,~\pmod{p}
2^{2^r}~\equiv~-1~\,~\pmod{p} ←(*)
2^{2^r~+~1}~\equiv~1~\,~\pmod{p} (∵両辺を2乗した)

nを2^n~\equiv~1~\,~\pmod{p}となるような最小のべきとし、n=2r+1を証明する。

下記のフェルマーの小定理の拡張定理を用いる。

[定理]「p:素数、a:pの倍数でない整数とする。
このとき、a^n~\equiv~1~\,~\pmod{p}となるような最小の整数n(>0)を取る。
すると、a^m~\equiv~1~\,~\pmod{p}となるような整数m(>0)は、nの倍数である」

この定理において、a=2,m=2r+1とおくと、nは2r+1の約数である。
よって、n=2k,k≦r+1である。

ここで、k<r+1と仮定して矛盾を示す。

2^n~\equiv~1~\,~\pmod{p}
2^{2^k}~\equiv~1~\,~\pmod{p} ←(**)

(*)と(**)により、k=rはありえない。
よって、k<rである。

また、(**)は次のように変形できる。

2^{2^k}~\equiv~1~\,~\pmod{p}
2^{2^{k+1}}~\equiv~1~\,~\pmod{p} (∵両辺を2乗した)

これを繰り返して2乗していくと、2^{2^{k+2}}~\equiv~1,~2^{2^{k+3}}~\equiv~1,~\cdots,~2^{2^{r}}~\equiv~1~\,~\pmod{p}となり、(*)に矛盾する。

したがって、k=r+1である。即ち、n=2r+1である。

さらに、フェルマーの小定理より、2^{p-1}~\equiv~1~\,~\pmod{p}である。
そして、フェルマーの小定理の拡張定理より、2^n~=~2^{2^{r+1}}~\equiv~1~\,~\pmod{p}を満たす最小のべきn=2r+1はp-1を割り切る。

ここで、商をlとすると、p-1~=~2^{r+1}~lと書ける。

ゆえに、題意を満たす。 □

[例]F5=5294967297を割り切る素数pは、p=26l+1=64l+1の形をしている。

l12345678910
p=64l+165129193257321385449513577641
結果素数でない素数でないF5を193で割ってみても割り切れない割り切れない素数でない素数でない割り切れない素数でない割り切れない割り切れる

このように、F5=5294967297は641で割り切れるため、素数ではないことがわかる。

F5=5294967297=641×6700417

 オイラーはさらに工夫して、次の結果を得た。これはlが偶数2kであるということである。

 これを用いると、フェルマー数が素数であるかどうかを調べる労力が半分になる。

[定理]r≧2とする。そのとき、F_r=2^{2^r}+1を割り切る素数pは次の形を持つ。
p~=~2^{r+2}~k~+~1(k:整数)

[証明]F0=3,F1=5だから、以下ではFr,r≧2の場合を考える。

pはp~=~2^{r+1}~l~+~1の形であることはすでに証明済みである。

[1]p~=~2^{r+1}~l~+~1のlが偶数であることを示す。

p~=~2^{r+1}~l~+~1
p~=~2^3~\cdot~2^{r-2}~l~+~1
p~=~8~\cdot~2^{r-2}~l~+~1
p~=~8~\cdot~m'~l~+~1 (∵m':=2r-2とおいた)
p~=~8~\cdot~m~~+~1 ←(*) (∵m:=m'lとおいた)

ここで、2^{4m}~(4m)!を次のように書き直す。

2^{4m}~(4m)!~=~(2~\cdot~1)~(2~\cdot~2)~\cdots~(2~\cdot~2m)~(2~\cdot~(2m+1))~(2~\cdot~(2m+2))~\cdots~(2~\cdot~4m)
2^{4m}~(4m)!~=~2~\cdot~4~\cdot~\cdots~\cdot~4m~(p-(4m-1))(p-(4m-3))~\cdots~(p-1) (∵(*)より、2~\cdot~(2m+1)=p-(4m-1),~2~\cdot~(2m+2)=p-(4m-3),~\cdots,~2~\cdot~4m~=~p-1
2^{4m}~(4m)!~\equiv~(-1)^{2m}~2~\cdot~4~\cdot~\cdots~\cdot~(4m-2)4m~(4m-1)(4m-3)~\cdots~1~\,~\pmod{p} (∵p-(4m-1)~\equiv~-(4m-1),~p-(4m-3)~\equiv~-(4m-3),~\cdots,~p-1~\equiv~-1~~\,~\pmod{p}
2^{4m}~(4m)!~\equiv~(4m)!~\,~\pmod{p}
2^{\frac{p-1}{2}}~(\frac{p-1}{2})!~\equiv~(\frac{p-1}{2})~\,~\pmod{p} (∵(*)より、m=\frac{p-1}{8}になり、4m=\frac{p-1}{2}
(2^{\frac{p-1}{2}}~-~1)(\frac{p-1}{2})!~\equiv~0~\,~\pmod{p} (∵右辺を左辺に移行した)

上記より、左辺はpで割り切れる。
しかし、(\frac{p-1}{2})!はpより小さい自然数の積なので、pで割り切れない。
よって、2^{\frac{p-1}{2}}~-~1がpで割り切れる。

即ち、2^{\frac{p-1}{2}}~\equiv~1~\,~\pmod{p} ←(**)

このように、pがp=8m+1の形をしているということより、(**)が得られた。

フェルマーの小定理の拡張定理を使うと、n=2r+1は(p-1)/2を割り切ることがわかる。即ち、2r+2はp-1を割り切る。商をkとして、次のように表すことができる。

p-1~=~2^{r+2}~k
p~=~2^{r+2}~k~+~1 □

[例]F5=5294967297を割り切る素数pは、p=27k+1=128k+1の形をしている。

k12345
p=128k+1129257385513641
結果素数でないF5を257で割ってみても割り切れない素数でない割り切れない割り切れる

p=64l+1のときよりも、必要な計算が半分になっており、労力は軽減されていることがわかる。

F5=5294967297=641×6700417

[補講]証明内において、pが8m+1の形の素数のときに、2^{\frac{p-1}{2}}~\equiv~1~\pmod{p}を示した。

[定理]「整数aと素数p=2s+1が互いに素とする。
そのとき、aがpを法として平方剰余であるかないかは、次によって定まる。
(1)a^s~\equiv~1~\,~\pmod{p}⇒aは(pを法とする)平方剰余
(2)a^s~\equiv~-1~\,~\pmod{p}⇒aは(pを法とする)平方非剰余」より、これは「p=8m+1の形の素数のときに、2はpを法として平方剰余である」ことを意味する。 ◇

フェルマー素数と作図問題の関係

 フェルマー素数は定規とコンパスだけによる平面図形の作図問題に関係している。当時19歳のガウスによって次の定理が証明された。

[定理](ガウス)
自然数nに対して、正n角形が作図可能であるための必要十分条件は、相異なるフェルマー素数p1,…,pkとe≧0となる整数eになり、nが次の形で表されることである。 n=2^e~p_1~\cdots~p_k

参考文献

  • 『工科系のための初等整数論入門 公開鍵暗号をめざして』
  • 『なっとくするオイラーとフェルマー』