■剰余の計算(その58)

フェルマー素数

Fn =2^2^n+1の形の素数をフェルマー素数といいます.

[1]2^n+1が素数ならば,n=2^mである.

(証)

 n≠2^mと仮定するとnの因数のひとつは奇数であり,n=kl(lは奇数)と表される.

  2^kl+1=(2^k)^;+1=(2^k+1)((2^k)^l-1−(2^k)^l-2+・・・−2^k+1)

は素数ではあり得ない.したがって,nの素因数は2だけである.

[2]フェルマーはこの型の数がすべて素数だと勘違いしていて必ず素数を与える式として考え出されたのですが,n=5であっけなく破綻してしまいました.

  F0=3(素数),F1=5(素数),F2=17素数),F3=257(素数),F4=65537(素数),F5=4294967297(非素数)

  F5 =2^2^5+1=4294967297

=641×6700417

=(5・2^7+1)(52347・2^7+1)

 

この間違いを発見したのはフェルマーから約100年後のオイラーです.彼は約数641をあてずっぽうでみつけたのでも,2,3,5,7,・・・と割っていって執念で見つけたのでもありません.オイラーはFn が合成数であるならば,それはあるkに対してk・2^n+1 +1であることを知っていて,F5 の中の因数641=10・2^6 +1を見つけたのです.

===================================