リュカ数列

リュカ数列（リュカすうれつ）またはルーカス数列（ルーカスすうれつ）(Lucas sequence)とは、二次の整係数方程式 G(x) = x² − Px + Q = 0 の二つの解

\alpha =(P+{\sqrt {D}})/2,\beta =(P-{\sqrt {D}})/2,D=P^{2}-4Q

に対し、

$U_{n}(P,Q)=(\alpha ^{n}-\beta ^{n})/(\alpha -\beta ),V_{n}(P,Q)=\alpha ^{n}+\beta ^{n}$

と定義される数列である。また同じことであるが、

$U_{0}(P,Q)=0,U_{1}(P,Q)=1,U_{n}(P,Q)=PU_{n-1}(P,Q)-QU_{n-2}(P,Q){\mbox{ for }}n>1,$
$V_{0}(P,Q)=2,V_{1}(P,Q)=P,V_{n}(P,Q)=PV_{n-1}(P,Q)-QV_{n-2}(P,Q){\mbox{ for }}n>1$

という関係式を満たす数列として定義される数列である。

リュカ数列は二階線形回帰数列の一種で、フィボナッチ数、リュカ数、ペル数, メルセンヌ数など数論に現れる重要な数列がこれに属する。

用語

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]。

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

また n が正のとき

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 も整数で

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 となる。

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

$m|n$ ならば、 $U_{m}|U_{n}$ ,
n が m の奇数倍ならば、 $V_{m}|V_{n}$ ,
N が 2 Q と互いに素な整数とする。 $N|U_{r}$ となる最小の r が存在するとき、 $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 が奇素数ならば、 $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 を割り切らない奇素数とし $l=p-\left({\frac {D}{p}}\right)$ とおくと、 p は U_l を割り切る。

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

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

フェルマーの小定理の逆が成り立たないように、上の定理の逆も成り立たない。つまり D と互いに素な合成数 n が U_l （ $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である。
$\gcd(U_{m},U_{n})=U_{\gcd(m,n)}.$
$d=\gcd(m,n)$ とする。 $m/d,n/d$ が共に奇数ならば $\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 は $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]。 $U_{n}(n=5,7\leq n\leq 30)$ が原始約数を持たないもの（ P が正の場合のみ挙げる。 P が負の場合は (-1)ⁿ 倍する）は次の通り。

n	$U_{n}(P,Q)$
5	U₅(1, -1)=5, U₅(1, 2)=-1, U₅(2, 11)=5, U₅(1, 3)=1, U₅(1, 4)=7, U₅(12, 55)=1, U₅(12, -1364)=1
7	U₇(1, 2)=1, U₇(1, 5)=1
8	U₈(2, 7)=-40, U₈(1, 2)=-3
10	U₁₀(2, 3)=-22, U₁₀(5, 7)=-3725, U₁₀(5, 18)=10025
12	U₁₂(1, -1)=144, U₁₂(1, 2)=-45, U₁₂(1, 3)=160, U₁₂(1, 4)=-231, U₁₂(1, 5)=-3024, U₁₂(2, 15)=-23452
13	U₁₃(1, 2)=-1
18	U₁₈(1, 2)=85
30	U₃₀(1, 2)=-24475

参考文献

^ 以下の性質についてはCarmichael, R. D. (1913), “On the numerical factors of the arithmetic forms αⁿ±βⁿ”, Annals of Mathematics 15 (1/4): 30–49, doi:10.2307/1967797, JSTOR 1967797, https://jstor.org/stable/1967797 , Carmichael, R. D. (1913), “On the numerical factors of the arithmetic forms αⁿ±βⁿ (continued)”, Annals of Mathematics 15 (1/4): 50–70, doi:10.2307/1967798, JSTOR 1967798, https://jstor.org/stable/1967798 , D. H., Lehmer (1930). “An Extended Theory of Lucas' Functions”. Ann. of Math. 31 (3): 419--448. doi:10.2307/1968235. JSTOR 1968235. および Ribenboim を参照
^ Peter Kiss, On Lucas pseudoprimes which are products of s primes, Fibonacci Numbers and Their Applications, 1986, 131--139.
^ Carmichael, 上記論文, 定理20
^ Carmichael, 上記論文, 定理21
^ Bilu, Yuri; Hanrot, Guillaume; Voutier, Paul M.; Mignotte, Maurice (2001). “Existence of primitive divisors of Lucas and Lehmer numbers”. J. Reine Angew. Math. 539: 75--122. doi:10.1515/crll.2001.080. MR 1863855. Guillaume Hanrot Publication list, 2001(preliminary version).
^ Voutier, Paul M. (1995). “Primitive divisors of Lucas and Lehmer sequences”. J. Reine Angew. Math. 64: 869--888. doi:10.1515/crll.2001.080. MR1284673. Guillaume Hanrot Publication list, 2001(preliminary version).

Ribenboim, Paulo (1996), The New Book of Prime Number Records (eBook ed.), Springer-Verlag, New York, doi:10.1007/978-1-4612-0759-7, ISBN 978-1-4612-0759-7

Philippou, Andreas; Bergum, G. E.; Horadam, Alwyn. F., eds. (2001) [1986], Fibonacci Numbers and Their Applications (Softcover reprint ed.), Kluwer Academic Publishers, Dordrecht, The Netherlands, ISBN 978-1402003271

[1] 以下の性質についてはCarmichael, R. D. (1913), “On the numerical factors of the arithmetic forms αⁿ±βⁿ”, Annals of Mathematics 15 (1/4): 30–49, doi:10.2307/1967797, JSTOR 1967797, https://jstor.org/stable/1967797 , Carmichael, R. D. (1913), “On the numerical factors of the arithmetic forms αⁿ±βⁿ (continued)”, Annals of Mathematics 15 (1/4): 50–70, doi:10.2307/1967798, JSTOR 1967798, https://jstor.org/stable/1967798 , D. H., Lehmer (1930). “An Extended Theory of Lucas' Functions”. Ann. of Math. 31 (3): 419--448. doi:10.2307/1968235. JSTOR 1968235. および Ribenboim を参照

[2] Peter Kiss, On Lucas pseudoprimes which are products of s primes, Fibonacci Numbers and Their Applications, 1986, 131--139.

[3] Carmichael, 上記論文, 定理20

[4] Carmichael, 上記論文, 定理21

[5] Bilu, Yuri; Hanrot, Guillaume; Voutier, Paul M.; Mignotte, Maurice (2001). “Existence of primitive divisors of Lucas and Lehmer numbers”. J. Reine Angew. Math. 539: 75--122. doi:10.1515/crll.2001.080. MR 1863855. Guillaume Hanrot Publication list, 2001(preliminary version).

[6] Voutier, Paul M. (1995). “Primitive divisors of Lucas and Lehmer sequences”. J. Reine Angew. Math. 64: 869--888. doi:10.1515/crll.2001.080. MR1284673. Guillaume Hanrot Publication list, 2001(preliminary version).

[1]

[2]

[3]

[4]

[5]

[6]