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

  • 追加された行はこの色です。
  • 削除された行はこの色です。
*目次 [#i6a5115e]

#contents


*はじめに [#qcee30d9]

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

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

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

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

*フェルマー数 [#g21a27c3]

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

#divid(s,thorem)
[定理]mが奇数dで割り切れるとすると、2SUP{m};+1は素数ではない。
#divid(e,thorem)

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

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

よって、mが奇数dで割り切れるとすると、2SUP{m};+1は素数ではない。 □
#divid(e,proof)

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

#divid(s,thorem)
[定義]&mimetex("2^{2^r}+1");(r≧0)の形の数を''フェルマー数''と呼ぶ。~
この値をFSUB{r};と表記する。
#divid(e,thorem)

#divid(s,thorem)
[定義]フェルマー数が素数のとき''フェルマー素数''、合成数のとき''フェルマー合成数''という。
#divid(e,thorem)

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

&mimetex("F_5 = 2^2^5 + 1=2^32 + 1=4294967297 =641 \times 6700417");

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

*フェルマー数を割り切る素数の形を考察する [#zf272e23]

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


#divid(s,thorem)
[定理]フェルマー数を割り切る素数pは次の形を持つ。~
&mimetex("p = 2^{r+1} l + 1");(l:整数)
#divid(e,thorem)

#divid(s,proof)
[証明]

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

nを&mimetex("2^n \equiv 1 \, \pmod{p}");となるような'''最小の'''べきとし、n=2SUP{r+1};を証明する。

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

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

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

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

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

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

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

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

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

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

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

ここで、商をlとすると、&mimetex("p-1 = 2^{r+1} l");と書ける。

ゆえに、題意を満たす。 □
#divid(e,proof)

#divid(s,notice)
[例]FSUB{5};=5294967297を割り切る素数pは、p=2SUP{6};l+1=64l+1の形をしている。

|l|1|2|3|4|5|6|7|8|9|10|h
|p=64l+1|65|129|193|257|321|385|449|513|577|641|
|結果|素数でない|素数でない|FSUB{5};を193で割ってみても割り切れない|割り切れない|素数でない|素数でない|割り切れない|素数でない|割り切れない|''割り切れる''|

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

FSUB{5};=5294967297=641×6700417
#divid(e,notice)

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

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

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

#divid(s,proof)
[証明]FSUB{0};=3,FSUB{1};=5だから、以下ではFSUB{r};,r≧2の場合を考える。

pは&mimetex("p = 2^{r+1} l + 1");の形であることはすでに証明済みである。

[1]&mimetex("p = 2^{r+1} l + 1");のlが偶数であることを示す。

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

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

&mimetex("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) ");~
&mimetex("2^{4m} (4m)! = 2 \cdot 4 \cdot \cdots \cdot 4m (p-(4m-1))(p-(4m-3)) \cdots (p-1)"); (∵(*)より、&mimetex("2 \cdot (2m+1)=p-(4m-1), 2 \cdot (2m+2)=p-(4m-3), \cdots, 2 \cdot 4m = p-1");)~
&mimetex("2^{4m} (4m)! \equiv (-1)^{2m} 2 \cdot 4 \cdot \cdots \cdot (4m-2)4m (4m-1)(4m-3) \cdots 1 \, \pmod{p}"); (∵&mimetex("p-(4m-1) \equiv -(4m-1), p-(4m-3) \equiv -(4m-3), \cdots, p-1 \equiv -1  \, \pmod{p}");)~
&mimetex("2^{4m} (4m)! \equiv (4m)! \, \pmod{p}");~
&mimetex("2^{\frac{p-1}{2}} (\frac{p-1}{2})! \equiv (\frac{p-1}{2}) \, \pmod{p}"); (∵(*)より、&mimetex("m=\frac{p-1}{8}");になり、&mimetex("4m=\frac{p-1}{2}");)~
&mimetex("(2^{\frac{p-1}{2}} - 1)(\frac{p-1}{2})! \equiv 0 \, \pmod{p}"); (∵右辺を左辺に移行した)

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

即ち、&mimetex("2^{\frac{p-1}{2}} \equiv 1 \, \pmod{p}"); ←(**)

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

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

&mimetex("p-1 = 2^{r+2} k");~
&mimetex("p = 2^{r+2} k + 1"); □
#divid(e,proof)

#divid(s,notice)
[例]FSUB{5};=5294967297を割り切る素数pは、p=2SUP{7};k+1=128k+1の形をしている。

|k|1|2|3|4|5|h
|p=128k+1|129|257|385|513|641|
|結果|素数でない|FSUB{5};を257で割ってみても割り切れない|素数でない|割り切れない|''割り切れる''|

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

FSUB{5};=5294967297=641×6700417
#divid(e,notice)

#divid(s,notice)
[補講]証明内において、pが8m+1の形の素数のときに、&mimetex("2^{\frac{p-1}{2}} \equiv 1 \pmod{p}");を示した。

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

*フェルマー素数と作図問題の関係 [#b0784a9a]

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

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


*参考文献 [#lfef34da]

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