コンテンツにスキップ

初等整数論/ルーカス数列

出典: フリー教科書『ウィキブックス(Wikibooks)』


P, Q, D となる整数とし、 を2次方程式 の解とする(D ≠ 0 より この2次方程式は2つの相異なる解をもつ)。 このとき

が成り立つ。 線形回帰数列 で述べたように、数列 について、 漸化式

を満足することと、一般項が

の形に表されることは同値である。

特に、線形回帰数列でも例にあげたフィボナッチ数のように、

により定まる数列 はいずれも上記の漸化式を満足し、初項は

により与えられる。逆に、これらの初項と漸化式で与えられる数列の一般項は (*) であらわされる。

このようにして定まる数列 に関するルーカス数列と呼ぶ。 また、数列 のみを単にルーカス数列といい、同伴ルーカス数列と呼ぶこともある。


[編集]

フィボナッチ数列 は (1, -1) に関するルーカス数列である。また、この同伴数列は により定まり、 2, 1, 3, 4, 7, 11, 18, 29, 47, ... で始まる。 そして、これらの数列の一般項は

により与えられる。 の要素をフィボナッチ数と呼ぶのに対し、の要素をルーカス数という。

(2, -1) に関するルーカス数列は 0, 1, 2, 5, 12, 29, 70, ... および 2, 2, 6, 14, 34, 82, 198, ... で始まる。一般項は

により与えられる。これらの数列はペル数列と呼ばれる(後に議論するが、ペル方程式と呼ばれる不定方程式の解としてあらわれる)。

基本的な関係式

[編集]

ルーカス数列には重要な関係式が多数存在するが、証明まで記載すると長大になるので、証明は別に記す

まず、次の関係式が成立する。

関係式 1

特に、 のとき、 はペル方程式の解となっていることがわかる。例えばペル数列に対し、 とおくとペル方程式 の解が得られる。

次に、添字の加法に関して、次のような、三角関数の加法定理に類似した関係式が成り立つ。

関係式 2

関係式 3

次のような関係式も成り立つ。

関係式 4

関係式 2, 3 の特殊な場合として、添字を2倍, 3倍したとき、次のような関係が成り立つ。

関係式 5

関係式 6


より一般的な、添字の乗法について考えたい。そのために、まず、次の等式が成り立つことを見る。 m が偶数のとき

m が奇数のとき

この等式を使って、次のような関係式が得られる。

関係式 7
m が奇数のとき

および

関係式 8
m が偶数で k が正の整数のとき

および

成り立つ。

また、添字を k 倍したときには、次のような関係式が成り立つ。

関係式 9
k が偶数のとき

k が奇数のとき

および

が成り立つ。

このほか、次のような展開もできる。

関係式 10

関係式 11
m が偶数のとき

m が奇数のとき


ルーカス数列の合同式

[編集]

上に挙げた関係式を用いて、ルーカス数列の整除性および合同に関する重要な性質が導かれる。

まず、関係式 9 から次のことがわかる。

定理 1
k が整数のとき、 を割り切る。 また k が奇数のとき、 を割り切る。


また、添字が素数のときは次の合同式が成り立つ。

定理 2
p が素数のとき

が成り立ち、さらに p が奇素数のとき

特に

が成り立つ。

証明
関係式 11 で、特に p が素数のとき

が成り立つ。また、p が奇素数のとき関係式 7 より

特に k =1 とおくと

となる。

このほか、次の合同式も成り立つ。

定理 3

証明
関係式 11 から はすぐわかる。 また、関係式 9 で m=1 とおくと

が成り立つ。


合同式における位数の類似概念として、 n の倍数となる が存在するとき、 そのような r の中で最小のものを とかく。 は合同式における位数と類似した性質をもっている。

定理 4
かつ n の倍数となる が存在するとき、 が成り立つ。

証明
定理 1 より r の倍数ならば n を割り切る。

n の倍数と仮定する。 とおくと、関係式 2 より

となるが、先の仮定より n の倍数で、定理 1 より n の倍数だから右辺は n の倍数、よって n の倍数である。定理の仮定より だから n の倍数。しかし だから s =0 つまり rm の倍数である。

重要な事実は、特殊な素数を除いて、フェルマーの小定理の類似の定理が成り立つことである。ただしフェルマーの小定理に比べ、幾分状況は複雑である。

定理 5
p を奇素数とする。 pP , Q , D のいずれも割り切らないとき

とおくと p を割り切る。


証明

のとき関係式 10 から、

であるが、

より

であるが、 とおくと、右辺は

となる。 より となる が存在する。 フェルマーの小定理より なので

となる。 p は奇素数なので

がわかる。

のとき再び関係式 10 から、

であるが、 のとき

の分母は p で割り切れないから、結局 p で割り切れなければならない。よって

となる。フェルマーの小定理より で、オイラーの規準より

だから

である。


の偶奇は次の定理から導かれる。

定理 6
n ≥ 0 とする。

  • P , Q が共に偶数ならば を除いてすべて偶数である。
  • P が偶数で Q が奇数ならば はつねに偶数で、 の偶奇は n の偶奇と一致する。
  • P が奇数で Q が偶数ならば はつねに奇数である。
  • P , Q が共に奇数ならば n が 3 の倍数のとき偶数、それ以外のとき奇数である。

証明
P, Q が共に偶数のとき漸化式

より はすべて偶数である。 より を除いて はすべて偶数である。

P が偶数で Q が奇数のとき

であるが、 より はつねに偶数で、 の偶奇は n の偶奇と一致する。

P が奇数で Q が偶数のとき

であるが、 より はつねに奇数である。

P , Q が共に奇数のとき

であるが、 より は共に となる。 つまり n が 3 の倍数のとき偶数、それ以外のとき奇数である。