リュカ数列
次のような等式が成り立つ。
V n 2 − D U n 2 = 4 Q n {\displaystyle V_{n}^{2}-DU_{n}^{2}=4Q^{n}} ,
U n 2 − U n − 1 U n + 1 = Q n − 1 {\displaystyle U_{n}^{2}-U_{n-1}U_{n+1}=Q^{n-1}} ,
D U n = V n + 1 − Q V n − 1 {\displaystyle DU_{n}=V_{n+1}-QV_{n-1}} ,
V n = U n + 1 − Q U n − 1 {\displaystyle V_{n}=U_{n+1}-QU_{n-1}} ,
2 U m + n = U m V n + U n V m {\displaystyle 2U_{m+n}=U_{m}V_{n}+U_{n}V_{m}} ,
2 V m + n = V m V n + D U m U n {\displaystyle 2V_{m+n}=V_{m}V_{n}+DU_{m}U_{n}} ,
U 2 n = U n V n {\displaystyle U_{2n}=U_{n}V_{n}} ,
V 2 n = V n 2 − 2 Q n {\displaystyle V_{2n}=V_{n}^{2}-2Q^{n}} ,
U m + n = U m V n − Q n U m − n {\displaystyle U_{m+n}=U_{m}V_{n}-Q^{n}U_{m-n}} ,
p が Un の原始約数ならば n は l を割り切る。特に、 p ≡ ( D p ) ( mod n ) {\displaystyle p\equiv \left({\frac {D}{p}}\right){\pmod {n}}} が成り立つ。
フェルマーの小定理の逆が成り立たないように、上の定理の逆も成り立たない。つまり D と互いに素な合成数 n が Ul ( l = n − ( D n ) {\displaystyle l=n-\left({\frac {D}{n}}\right)} )を割り切る場合が存在する。そのような n は リュカ擬素数 (Lucas pseudoprime) という。 非退化の数列に対応するリュカ擬素数は無数に存在する。さらに正確に、任意の与えられた非退化の数列と正整数 k, s に対し、 s 個の素因数をもち、それらがすべて等差数列 kx +1 に属するリュカ擬素数が無数に存在する。
P と Q が互いに素ならば、次の性質も成り立つ。
Un と Q は互いに素、また Vn と Q も互いに素である。
Un と Vn は互いに素であるか、最大公約数は2である。
gcd ( U m , U n ) = U gcd ( m , n ) . {\displaystyle \gcd(U_{m},U_{n})=U_{\gcd(m,n)}.}
d = gcd ( m , n ) {\displaystyle d=\gcd(m,n)} とする。
とおく(μ はメビウス関数、ζn は1の原始 n 乗根、φはオイラーの φ 関数、Φn は1の原始 n 乗根に関する円分多項式)と、 Fn も整数で
U n = ∏ d ∣ n F d , V n = ∏ d ∣ 2 n , 2 ∤ 2 n / d F d {\displaystyle U_{n}=\prod _{d\mid n}F_{d},V_{n}=\prod _{d\mid 2n,2\not \mid 2n/d}F_{d}}
が成り立つ。特に Fn は Un の約数で、 p が素数のとき Fp = Up となる。
また、 リュカ数列の整除性について、次のような性質が成り立つ。
m | n {\displaystyle m|n} ならば、 U m | U n {\displaystyle U_{m}|U_{n}} ,
n が m の奇数倍ならば、 V m | V n {\displaystyle V_{m}|V_{n}} ,
N が 2 Q と互いに素な整数とする。 N | U r {\displaystyle N|U_{r}} となる最小の r が存在するとき、 N | U n {\displaystyle N|U_{n}} となる n 全体は r の倍数全体と一致する。
P, Q が偶数ならば、 Un, Vn は U 1を除いていつも偶数である。
P が偶数で、 Qが奇数ならば、 Un の偶奇 は n の偶奇と一致し、 Vn はいつも偶数である。