リュカ数列

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 ⁿ-1, V_n (3, 2)=2 ⁿ+1で、それぞれメルセンヌ数, フェルマー数を含んでいる。

U_n (2, -1), V_n (2, -1)はペル数となる。

次のような等式が成り立つ^[1]。

• ${\displaystyle V_{n}^{2}-DU_{n}^{2}=4Q^{n}}$,
• ${\displaystyle U_{n}^{2}-U_{n-1}U_{n+1}=Q^{n-1}}$,
• ${\displaystyle DU_{n}=V_{n+1}-QV_{n-1}}$,
• ${\displaystyle V_{n}=U_{n+1}-QU_{n-1}}$,
• ${\displaystyle 2U_{m+n}=U_{m}V_{n}+U_{n}V_{m}}$,
• ${\displaystyle 2V_{m+n}=V_{m}V_{n}+DU_{m}U_{n}}$,
• ${\displaystyle U_{2n}=U_{n}V_{n}}$,
• ${\displaystyle V_{2n}=V_{n}^{2}-2Q^{n}}$,
• ${\displaystyle U_{m+n}=U_{m}V_{n}-Q^{n}U_{m-n}}$,
• ${\displaystyle V_{m+n}=V_{m}V_{n}-Q^{n}V_{m-n}=DU_{m}U_{n}+Q^{n}V_{m-n}}$,
• ${\displaystyle 2^{n-1}U_{n}={n \choose 1}P^{n-1}+{n \choose 3}P^{n-3}D+\cdots }$,
• ${\displaystyle 2^{n-1}V_{n}=P^{n}+{n \choose 2}P^{n-2}D+{n \choose 4}P^{n-4}D^{2}+\cdots }$.

また n が正のとき

${\displaystyle F_{n}=\prod _{d\mid n}U_{n/d}^{\mu (d)}={\frac {U_{n}\prod _{p\neq q,p,q\mid n}U_{n/pq}\cdots }{\prod _{p\mid n}U_{n/p}\cdots }}=\prod _{\gcd(k,n)=1}(\alpha -\zeta _{n}^{k}\beta )=\beta ^{\varphi (n)}\Phi _{n}(\alpha /\beta )}$

とおく（μ はメビウス関数、ζ_n は1の原始 n 乗根、φはオイラーの φ 関数、Φ_n は1の原始 n 乗根に関する円分多項式）と、 F_n も整数で

${\displaystyle U_{n}=\prod _{d\mid n}F_{d},V_{n}=\prod _{d\mid 2n,2\not \mid 2n/d}F_{d}}$

が成り立つ。特に F_n は U_n の約数で、 p が素数のとき F_p = U_p となる。

また、 リュカ数列の整除性について、次のような性質が成り立つ。

• ${\displaystyle m|n}$ならば、${\displaystyle U_{m}|U_{n}}$,
• n が m の奇数倍ならば、${\displaystyle V_{m}|V_{n}}$,
• N が 2 Q と互いに素な整数とする。${\displaystyle N|U_{r}}$となる最小の r が存在するとき、${\displaystyle N|U_{n}}$となる n 全体は r の倍数全体と一致する。

• P, Q が偶数ならば、 U_n, V_n は U ₁を除いていつも偶数である。
• P が偶数で、 Qが奇数ならば、 U_n の偶奇 は n の偶奇と一致し、 V_n はいつも偶数である。
• P が奇数で、 Qが偶数ならば、 U_n , V_n はいつも奇数である。
• P, Q が奇数ならば、 U_n , V_n は n が3の倍数であるとき偶数で、そうでないとき奇数である。

• p が奇素数ならば、${\displaystyle U_{p}\equiv \left({\frac {D}{p}}\right),V_{p}\equiv P{\pmod {p}},\left({\frac {D}{p}}\right)}$は平方剰余の記号である。
• p が奇素数で、 P , Q を割り切るならば、p は U ₁を除く全ての U_n を割り切る。
• p が奇素数で、 P を割り切り Q を割り切らないならば、p が U_n を割り切るのは n が偶数であることと同値である。
• p が奇素数で、 P を割り切らず Q を割り切るならば、p は決して U_n を割り切らない。
• p が奇素数で、 PQ を割り切らず、 Dを割り切るならば、p が U_n を割り切るのは n が p の倍数であることと同値である。
• p を PQD を割り切らない奇素数とし ${\displaystyle l=p-\left({\frac {D}{p}}\right)}$ とおくと、 p は U_l を割り切る。

最後の定理はフェルマーの小定理の一般化である。これと原始約数の定義から、次のことがわかる。

• p を PQD を割り切らない奇素数とする、 ${\displaystyle l=p-\left({\frac {D}{p}}\right)}$ とおく。 p が U_n の原始約数ならば n は l を割り切る。特に、${\displaystyle p\equiv \left({\frac {D}{p}}\right){\pmod {n}}}$ が成り立つ。

フェルマーの小定理の逆が成り立たないように、上の定理の逆も成り立たない。つまり D と互いに素な合成数 n が U_l （${\displaystyle l=n-\left({\frac {D}{n}}\right)}$）を割り切る場合が存在する。そのような n は リュカ擬素数 (Lucas pseudoprime) という。 非退化の数列に対応するリュカ擬素数は無数に存在する。さらに正確に、任意の与えられた非退化の数列と正整数 k, s に対し、 s 個の素因数をもち、それらがすべて等差数列 kx +1 に属するリュカ擬素数が無数に存在する^[2]。

P と Q が互いに素ならば、次の性質も成り立つ。

• U_n と Q は互いに素、また V_n と Q も互いに素である。
• U_n と V_n は互いに素であるか、最大公約数は2である。
• ${\displaystyle \gcd(U_{m},U_{n})=U_{\gcd(m,n)}.}$
• ${\displaystyle d=\gcd(m,n)}$ とする。 ${\displaystyle m/d,n/d}$ が共に奇数ならば ${\displaystyle \gcd(V_{m},V_{n})=V_{d}.}$

リュカ数列の値は少数の例外を除いて原始約数を持つことが知られている。D を割り切らない素数 p が F_n の原始約数であるための必要十分条件は p が n を割り切らないことである^[3]。

P, Q が互いに素かつ U_n が非退化とする。 D > 0のとき、 n ≠ 1, 2, 6ならば U_n は ${\displaystyle U_{3}(1,-2)=U_{3}(-1,-2)=3,U_{5}(1,-1)=U_{5}(-1,-1)=5,U_{12}(1,-1)=144,U_{12}(-1,-1)=-144}$を除いて原始約数を持つことは既にカーマイケルにより示されている^[4]。 D < 0のときは難しい問題であったが n > 30ならば、 U_n は原始約数を持つ^[5]。また、 n ≤ 30で、 U_n が原始約数を持たないものは先に全て知られている^[6]。${\displaystyle U_{n}(n=5,7\leq n\leq 30)}$ が原始約数を持たないもの（ P が正の場合のみ挙げる。 P が負の場合は (-1)ⁿ 倍する）は次の通り。