リュカ数列

リュカ数列（リュカすうれつ）またはルーカス数列（ルーカスすうれつ）("Lucas sequence")とは、二次の整係数方程式 "G"("x") = "x"2 − "Px" + "Q" = 0 の二つの解
に対し、
と定義される数列である。また同じことであるが、
という関係式を満たす数列として定義される数列である。
リュカ数列は二階線形回帰数列の一種で、フィボナッチ数、リュカ数、ペル数, メルセンヌ数など数論に現れる重要な数列がこれに属する。
用語.
"U""n" , "V""n" を( "P" , "Q" )に伴うリュカ数列という。"V""n" を同伴リュカ数列と呼ぶこともある。 α/β が1の冪根であるとき "U""n" , "V""n" を退化("degenerate")、そうでないとき非退化("non-degenerate")という。
"D" を割り切らない素数 "p" が "U""n" を割り切るが、 "U""m" ( "m" < "n" )を割り切らないとき、 "p" を "U""n" の原始約数( 'primitive divisor' )という。
例.
"U""n" (1, -1)はフィボナッチ数, "V""n" (1, -1)は（通常の）リュカ数である。
"U""n" (3, 2)=2 "n"-1, "V""n" (3, 2)=2 "n"+1で、それぞれメルセンヌ数, フェルマー数を含んでいる。
"U""n" (2, -1), "V""n" (2, -1)はペル数となる。
性質.
次のような等式が成り立つ。
また "n" が正のとき
とおく（μ はメビウス関数、ζ"n" は1の原始 "n" 乗根、はオイラーの 関数、Φ"n" は1の原始 "n" 乗根に関する円分多項式）と、 "F""n" も整数で
が成り立つ。特に "F""n" は "U""n" の約数で、 "p" が素数のとき "F""p" = "U""p" となる。
また、 リュカ数列の整除性について、次のような性質が成り立つ。
最後の定理はフェルマーの小定理の一般化である。これと原始約数の定義から、次のことがわかる。
フェルマーの小定理の逆が成り立たないように、上の定理の逆も成り立たない。つまり "D" と互いに素な合成数 "n" が "Ul" （formula_25）を割り切る場合が存在する。そのような "n" は リュカ擬素数 ("Lucas pseudoprime") という。
非退化の数列に対応するリュカ擬素数は無数に存在する。さらに正確に、任意の与えられた非退化の数列と正整数 "k", "s" に対し、 "s" 個の素因数をもち、それらがすべて等差数列 "kx" +1 に属するリュカ擬素数が無数に存在する。
"P" と "Q" が互いに素ならば、次の性質も成り立つ。
リュカ数列の値は少数の例外を除いて原始約数を持つことが知られている。"D" を割り切らない素数 "p" が "F""n" の原始約数であるための必要十分条件は "p" が "n" を割り切らないことである。
"P", "Q" が互いに素かつ "U""n" が非退化とする。 "D" > 0のとき、 "n" ≠ 1, 2, 6ならば "U""n" は formula_30を除いて原始約数を持つことは既にカーマイケルにより示されている。 "D" < 0のときは難しい問題であったが "n" > 30ならば、 "U""n" は原始約数を持つ。また、 "n" ≤ 30で、 "U""n" が原始約数を持たないものは先に全て知られている。formula_31 が原始約数を持たないもの（ "P" が正の場合のみ挙げる。 "P" が負の場合は (-1)"n" 倍する）は次の通り。