【１】リュカ数列と素数判定法

　　１，１，２，３，５，８，・・・

この数列にフィボナッチ（１３世紀のイタリアの数学者でピサのレオナルドとしても知られる）の名を冠したのはフランスの数学者リュカで，ハノイの塔の名で知られる２進法のパズルも１８８３年にリュカによって考案されたものです．

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

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

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

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

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

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

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

　　　　　ｍ　　Ｌn の周期　　　　　ｍ　　Ｌn の周期

　　　　　１　　　　１　　　　　　　９　　　２４

　　　　　２　　　　３　　　　　　１０　　　１２＊

　　　　　３　　　　８　　　　　　１１　　　１０

　　　　　４　　　　６　　　　　　１２　　　２４

　　　　　５　　　　４＊　　　　１００　　　６０＊

　　　　　６　　　２４　　　　１０００　　３００＊

　　　　　７　　　１６

　　　　　８　　　１２

　リュカ数にはフィボナッチ数とは別の周期性が現れます．フィボナッチ数と異なるところに＊印を付けておきました．とはいっても，リュカ数の周期とフィボナッチ数の周期は全部ではないにしても，ほとんどが一致します．

　両者の決定的な違いは，フィボナッチ数の循環節には必ず０が現れるのに対して，リュカ数のｍ＝５やｍ＝８の循環節には０が出てこないということです．これはリュカ数が５や８では決して割り切れないということを意味しています．もちろん５と８の倍数でも割れません．フィボナッチ数では任意の自然数ｍに対して，必ず割り切れるＦnが存在します．

　また，フィボナッチ数とリュカ数の性質は，整除性という点でも大分様子が違っています．２の倍数は３項ごとに現れる，３の倍数は４項ごとに現れるなどは似ていますが，５の倍数や８の倍数は出てきません．フィボナッチ数がきれいな規則性に従って並んでいるのに対し，リュカ数では１，３から始めて前の２項を加えるという規則を多少変えただけで，そうはならないのです．

　リュカ数の整除性をまとめると

(1)素数ｐに対して

　　Ｌp＝１　（ｍｏｄｐ）

(2)奇素数（ｐ≠５）に対して

　　ｐ＝±１（ｍｏｄ５）→Ｌp-1＝＋２（ｍｏｄｐ）

　　ｐ＝±２（ｍｏｄ５）→Ｌp+1＝−２（ｍｏｄｐ）

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

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

　添字に２^nをもつリュカ数列｛Ｌ2^n｝，すなわち，３，７，４７，２２０７，４８７０８４７，・・・では，漸化式Ｌ2^(n+1)＝（Ｌ2^n）^2−２が成り立ちますが，この漸化式とフェルマーの小定理（１６４０年）

　　「もしｐが素数であれば，任意の整数ａに関してａ^p−ａはｐの倍数である．」を応用した素数判定法がリュカテストです．

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

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