初項１，第２項３のフィボナッチ数列

１，３，４，７，１１，１８，・・・

はフランスの数学者リュカにちなんでリュカ数列と呼ばれています（１８７７年）．リュカ数列の一般項Ｌn は，

Ｌn ＝｛（１＋√５）／２｝n ＋｛（１−√５）／２｝n

　　＝｛φn ＋（−１／φ）n ｝

（Ｌ0 ＝２：φ＝（１＋√５）／２）

で表され，Ｌn ＝Ｆn-1 ＋Ｆn+1 の関係があります．リュカ数列はフィボナッチ数列と同じ漸化式をもち，連続する２つの項の比は黄金比に近づきます．

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

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

【１】メルセンヌ数とリュカテスト

メルセンヌ数とは，ｐを素数とするとき

　　Ｍp＝２^p−１

Ｍp自身が素数のとき，メルセンヌ素数と呼ばれます．

　２^11−１＝２０４７＝２３・８９

のように，すべての素数ｐがメルセンヌ素数を与えるわけではないので，素数性を判定する方法が必要になります．

平方数から２を差し引くという生成則に従う数列

　　Sn＝（Sn-1）^2−２，S2＝４

Ｓ2＝４，Ｓ3＝１４，Ｓ4＝１９４，Ｓ5＝３７６３４，・・・

は，メルセンス数の素数性判定のために用いられる数列です．

リュカテストでは，素因数を見つけることなく，直接メルセンヌ素数であるかどうかを判定します．ｐが奇数の素数のとき，Mpが素数であるための必要十分条件：ＳpがＭpで割り切れる，かつ，そのときだけＭpは素数である．

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

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

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