【１】フェルマー数

　フェルマー数は簡単な漸化式

　　Ｆn ＝（Ｆn-1 −１）^2＋１

　　Ｆn −１＝（Ｆn-1 −１）^2

を満たしています．

　　２^(2^2)＝１６

　　２^(2^3)＝｛２^(2^2)｝^2＝１６^2

　　２^(2^4)＝｛２^(2^3)｝^2＝（１６^2）^2

　　２^(2^5)＝｛２^(2^4)｝^2＝（（１６^2）^2）^2

　　・・・・・・・・・・・・・・・・・・・・・・・

　この式から

　　Ｆn −２＝Ｆn-1 （Ｆn-1 −１）＝・・・＝Ｆ0 Ｆ1 ・・・Ｆn-1

言い換えれば，Ｆn −２はそれより小さいすべてのフェルマー数で割り切れることがわかります．

　辺数３，４，５，６，８，１０，１２，１５，１６の正多角形は作図できますが，辺数７，９，１１，１３，１４の正多角形は作図できないことから，正１７角形もそうであろうと推察されます．ところが，１７９６年，ガウスは１９才のときに正１７角形の作図を思いつき，のみならず，ｎが素数の正ｎ角形について，ｎ＝２^2^m＋１が素数の場合に限り定規とコンパスだけで作図可能であることを発見しています．

　正７角形も正９角形も作図できないのに，まさか正１７角形が作図できるとはと思うのが普通なのでしょうが，このことを用いると，ｍ＝０のとき正３角形，ｍ＝１のとき正５角形，ｍ＝２のとき正１７角形となり，作図可能であることがわかります．当然，ずっと面倒になるでしょうが，正２５７角形（ｍ＝３），正６５５３７角形（ｍ＝４）も作図可能です．

　２^2^m＋１の形の素数をフェルマー素数といいます．フェルマー素数はガウスによって１世紀にわたる眠りから覚まされ，数論と幾何学に新たな美しさを吹き込んだことになります．フェルマーはこの型の数がすべて素数だと勘違いしていて必ず素数を与える式として考え出されたのですが，ｍ＝５のときは素数ではなく，現在，ｍ＝０，１，２，３，４の５個以外にフェルマー素数はみつかっていません．６番目のフェルマー素数の探索がコンピュータを使ってなされていますが，はたして本当に存在するのでしょうか．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

【２】メルセンヌ数

　２^n−１の形の数が素数であるためにはｎが素数であることが必要条件です．一方，２^n＋１の形が素数であるためにはｎ＝２m の形であることが必要です．しかし，このことは十分条件ではなく，指数ｎがどんな数のとき２^n−１，２n ＋１が素数になるかはいまだに解決されていません．

　添字に２^nをもつリュカ数列｛Ｌ2^n｝，すなわち，３，７，４７，２２０７，４８７０８４７，・・・では，漸化式Ｌ2^(n+1)＝（Ｌ2^n）2 −２が成り立ちますが，この漸化式とフェルマーの小定理（もしｐが素数であれば，任意の整数ａに関してａ^p−ａはｐの倍数である．１６４０年）を応用した素数判定法がリュカテストです．

　リュカはフィボナッチ数列，リュカ数列を用いてメルセンヌ数（２^n−１）が素数であるかどうかを判定し，（２^127−１）が素数であることを示しています（１８７６年）．この数は１２番目のメルセンヌ素数で，１９５２年の１３番目（２^521−１）からはコンピュータによる発見ですから，コンピュータを使わずに見つけられた最大のメルセンヌ素数になっていて，わかっている最大の素数として最長不倒記録を保ち続けました．

　１９９４年，アメリカのスーパーコンピュータ，クレイによって発見された２５８７１６桁の巨大な素数（２^859433−１）は３３番目のメルセンヌ素数ですが，リュカテストはメルセンヌ数が素数であるか否か判定する非常に能率的なアルゴリズムとなっていて，リュカテストの効率のよさのおかげで最近の素数の世界記録はすべてメルセンヌ素数が独占しています．

　なお，フェルマー数（２^2^n＋１）に対してはリュカテストと同じくらい能率的なペパンの素数判定法があり，コンピュータを使って６番目のフェルマー素数の探索が続けられているのですが，はたして本当に存在するのでしょうか．

　リュカやペパンの素数判定法によってある数が合成数とわかってもそれを素因数分解するのはとても大変な作業になります．現在，巨大な整数の素因数分解に楕円曲線法とか平方ふるい法とか能率のよい素因数分解法が考え出されています．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝