リュカ数列

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

リュカ数列(リュカすうれつ)またはルーカス数列(ルーカスすうれつ)(Lucas sequence)とは、二次の整係数方程式 G ( x ) = x 2 - P x + 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

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

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

用語[編集]

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)はペル数となる。

性質[編集]

次のような等式が成り立つ。

  • 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_mV_n+U_nV_m,
  • 2V_{m+n}=V_mV_n+DU_mU_n,
  • U_{2n}=U_nV_n,
  • V_{2n}=V_n^2-2Q^n,
  • U_{m+n}=U_mV_n-Q^nU_{m-n},
  • V_{m+n}=V_mV_n-Q^nV_{m-n}=DU_mU_n+Q^nV_{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.

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

  • m|nならば、U_m|U_n,
  • nm奇数倍ならば、V_m|V_n,
  • N が 2 Q互いに素な整数とする。N|U_rとなる最小の r が存在するとき、N|U_nとなる n 全体は r倍数全体と一致する。
  • P, Q偶数ならば、 Un, VnU 1を除いていつも偶数である。
  • P が偶数で、 Q奇数ならば、 Un の偶奇 は n の偶奇と一致し、 Vn はいつも偶数である。
  • P が奇数で、 Qが偶数ならば、 Un , Vn はいつも奇数である。
  • P, Q が奇数ならば、 Un , Vnn が3の倍数であるとき偶数で、そうでないとき奇数である。
  • p が奇素数ならば、U_p\equiv\left(\frac{D}{p}\right), V_p\equiv P\pmod{p}, \left(\frac{D}{p}\right)平方剰余の記号である。
  • p が奇素数で、 P , Q を割り切るならば、pU 1を除く全ての Un を割り切る。
  • p が奇素数で、 P を割り切り Q を割り切らないならば、pUn を割り切るのは n が偶数であることと同値である。
  • p が奇素数で、 P を割り切らず Q を割り切るならば、p は決して Un を割り切らない。
  • p が奇素数で、 PQ を割り切らず、 Dを割り切るならば、pUn を割り切るのは np の倍数であることと同値である。
  • pPQD を割り切らない奇素数としl=p-\left(\frac{D}{p}\right)とおくと、 pUl を割り切る。

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

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

リュカ数列の値は少数の例外を除いて原始約数を持つことが知られている。 n > 30ならば、 Un は原始約数を持つ。また、 n ≤ 30で、 Un が原始約数を持たないものは全て知られている[1]

  1. ^ Yuri Bilu, Guillaume Hanrot, Paul M. Voutier, Maurice Mignotte, Existence of primitive divisors of Lucas and Lehmer numbers, J. Reine Angew. Math. 539 (2001), 75--122. Guillaume Hanrot Publication list, 2001(preliminary version).