リュカ数列

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

に対し、

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


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

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

用語

Un , Vn を( P , Q )に伴うリュカ数列という。Vn を同伴リュカ数列と呼ぶこともある。 α/β が1の冪根であるとき Un , Vn退化(degenerate)、そうでないとき非退化(non-degenerate)という。

D を割り切らない素数 pUn を割り切るが、 Um ( m < n )を割り切らないとき、 pUn原始約数( 'primitive divisor' )という。

Un (1, -1)はフィボナッチ数, Vn (1, -1)は(通常の)リュカ数である。

Un (3, 2)=2 n-1, Vn (3, 2)=2 n+1で、それぞれメルセンヌ数, フェルマー数を含んでいる。

Un (2, -1), Vn (2, -1)はペル数となる。

性質

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

  • ,
  • ,
  • ,
  • ,
  • ,
  • ,
  • ,
  • ,
  • ,
  • ,
  • ,
  • .

また n が正のとき

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

が成り立つ。特に FnUn の約数で、 p が素数のとき Fp = Up となる。

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

  • ならば、,
  • nm奇数倍ならば、,
  • N が 2 Q互いに素な整数とする。となる最小の r が存在するとき、となる n 全体は r倍数全体と一致する。
  • P, Q偶数ならば、 Un, VnU 1を除いていつも偶数である。
  • P が偶数で、 Q奇数ならば、 Un の偶奇 は n の偶奇と一致し、 Vn はいつも偶数である。
  • P が奇数で、 Qが偶数ならば、 Un , Vn はいつも奇数である。
  • P, Q が奇数ならば、 Un , Vnn が3の倍数であるとき偶数で、そうでないとき奇数である。
  • p が奇素数ならば、平方剰余の記号である。
  • p が奇素数で、 P , Q を割り切るならば、pU 1を除く全ての Un を割り切る。
  • p が奇素数で、 P を割り切り Q を割り切らないならば、pUn を割り切るのは n が偶数であることと同値である。
  • p が奇素数で、 P を割り切らず Q を割り切るならば、p は決して Un を割り切らない。
  • p が奇素数で、 PQ を割り切らず、 Dを割り切るならば、pUn を割り切るのは np の倍数であることと同値である。
  • pPQD を割り切らない奇素数とし とおくと、 pUl を割り切る。

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

  • pPQD を割り切らない奇素数とする、 とおく。 pUn の原始約数ならば nl を割り切る。特に、 が成り立つ。

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

PQ互いに素ならば、次の性質も成り立つ。

  • UnQ は互いに素、また VnQ も互いに素である。
  • UnVn は互いに素であるか、最大公約数は2である。
  • とする。 が共に奇数ならば

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

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

n
5 U5(1, -1)=5, U5(1, 2)=-1, U5(2, 11)=5, U5(1, 3)=1, U5(1, 4)=7, U5(12, 55)=1, U5(12, -1364)=1
7 U7(1, 2)=1, U7(1, 5)=1
8 U8(2, 7)=-40, U8(1, 2)=-3
10 U10(2, 3)=-22, U10(5, 7)=-3725, U10(5, 18)=10025
12 U12(1, -1)=144, U12(1, 2)=-45, U12(1, 3)=160, U12(1, 4)=-231, U12(1, 5)=-3024, U12(2, 15)=-23452
13 U13(1, 2)=-1
18 U18(1, 2)=85
30 U30(1, 2)=-24475

参考文献

  1. ^ 以下の性質についてはCarmichael, R. D. (1913), “On the numerical factors of the arithmetic forms αn±βn, 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 αn±βn (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. MR1863855. 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).