コラム「パスカルの三角形の概３等分（その２７）」では，リュカ数Ｌnに対して

　　（２^n＋２Ｌn）／５

　　（２^2^n＋２Ｌ2^n）／５

は整数になることを示している．

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

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

　添字に２^nをもつリュカ数列｛Ｌ2^n｝，すなわち，３，７，４７，２２０７，４８７０８４７，・・・では，漸化式

　　Ｌ2^(n+1)＝（Ｌ2^n）^2−２

が成り立ちますが，この漸化式とフェルマーの小定理（もしｐが素数であれば，任意の整数ａに関してａ^p−ａはｐの倍数である．１６４０年）を応用した素数判定法がリュカテストです．

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

　リュカテストはメルセンヌ数が素数であるか否か判定する非常に能率的なアルゴリズムとなっていて，リュカテストの効率のよさのおかげで最近の素数の世界記録はすべてメルセンヌ素数が独占しています．

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

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

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

【補】フェルマー数

　フェルマー数は簡単な漸化式Ｆn ＝（Ｆn-1 −１）^2＋１を満たしています．この式から

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

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

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