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

P, Q, D を D = P 2 − 4 Q ≠ 0 {\displaystyle D=P^{2}-4Q\neq 0} となる整数とし、 α , β {\displaystyle \alpha ,\beta } を2次方程式 x 2 − P x + Q = 0 {\displaystyle x^{2}-Px+Q=0} の解とする(D ≠ 0 より この2次方程式は2つの相異なる解をもつ)。 このとき
が成り立つ。 線形回帰数列 で述べたように、数列 a n ( n = 0 , 1 , ... ) {\displaystyle a_{n}(n=0,1,\ldots )} について、 漸化式
を満足することと、一般項が
の形に表されることは同値である。
特に、線形回帰数列でも例にあげたフィボナッチ数のように、
により定まる数列 U n , V n {\displaystyle U_{n},V_{n}} はいずれも上記の漸化式を満足し、初項は
により与えられる。逆に、これらの初項と漸化式で与えられる数列の一般項は (*) であらわされる。
このようにして定まる数列 U n , V n {\displaystyle U_{n},V_{n}} を ( P , Q ) {\displaystyle (P,Q)} に関するルーカス数列と呼ぶ。 また、数列 U n {\displaystyle U_{n}} のみを単にルーカス数列といい、 V n {\displaystyle V_{n}} を同伴ルーカス数列と呼ぶこともある。

フィボナッチ数列 F 0 = 0 , F 1 = 1 , F n + 2 = F n + 1 + F n {\displaystyle F_{0}=0,F_{1}=1,F_{n+2}=F_{n+1}+F_{n}} は (1, -1) に関するルーカス数列である。また、この同伴数列は L 0 = 2 , L 1 = 1 , L n + 2 = L n + 1 + L n {\displaystyle L_{0}=2,L_{1}=1,L_{n+2}=L_{n+1}+L_{n}} により定まり、 2, 1, 3, 4, 7, 11, 18, 29, 47, ... で始まる。 そして、これらの数列の一般項は
により与えられる。 F n {\displaystyle F_{n}} の要素をフィボナッチ数と呼ぶのに対し、 L n {\displaystyle L_{n}} の要素をルーカス数という。
(2, -1) に関するルーカス数列は 0, 1, 2, 5, 12, 29, 70, ... および 2, 2, 6, 14, 34, 82, 198, ... で始まる。一般項は
により与えられる。これらの数列はペル数列と呼ばれる(後に議論するが、ペル方程式と呼ばれる不定方程式の解としてあらわれる)。
ルーカス数列には重要な関係式が多数存在するが、証明まで記載すると長大になるので、証明は別に記す。
まず、次の関係式が成立する。
関係式 1
特に、 Q = ± 1 {\displaystyle Q=\pm 1} のとき、 U n , V n {\displaystyle U_{n},V_{n}} はペル方程式の解となっていることがわかる。例えばペル数列に対し、 X = V n / 2 , Y = U n {\displaystyle X=V_{n}/2,Y=U_{n}} とおくとペル方程式 X 2 − 2 Y 2 = ± 1 {\displaystyle X^{2}-2Y^{2}=\pm 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 が整数のとき、 U m {\displaystyle U_{m}} は U k m {\displaystyle U_{km}} を割り切る。 また k が奇数のとき、 V m {\displaystyle V_{m}} は V k m {\displaystyle V_{km}} を割り切る。
また、添字が素数のときは次の合同式が成り立つ。
定理 2 p が素数のとき
が成り立ち、さらに p が奇素数のとき
特に
が成り立つ。
証明 関係式 11 で、特に p が素数のとき
が成り立つ。また、p が奇素数のとき関係式 7 より
特に k =1 とおくと
となる。
このほか、次の合同式も成り立つ。
定理 3
証明 関係式 11 から V k ≡ P k ( mod Q ) {\displaystyle V_{k}\equiv P^{k}{\pmod {Q}}} はすぐわかる。 また、関係式 9 で m=1 とおくと
が成り立つ。
合同式における位数の類似概念として、 n の倍数となる U r ( r > 0 ) {\displaystyle U_{r}(r>0)} が存在するとき、 そのような r の中で最小のものを ρ ( n ) {\displaystyle \rho (n)} とかく。 ρ ( n ) {\displaystyle \rho (n)} は合同式における位数と類似した性質をもっている。
定理 4 gcd ( n , 2 Q ) = 1 {\displaystyle \gcd(n,2Q)=1} かつ n の倍数となる U r {\displaystyle U_{r}} が存在するとき、 n | U r ⟺ ρ ( n ) | r {\displaystyle n|U_{r}\iff \rho (n)|r} が成り立つ。
証明 定理 1 より r が m = ρ ( n ) {\displaystyle m=\rho (n)} の倍数ならば n は U r {\displaystyle U_{r}} を割り切る。
U r {\displaystyle U_{r}} が n の倍数と仮定する。 r = q m + s , 0 ≤ s ≤ m − 1 {\displaystyle r=qm+s,0\leq s\leq m-1} とおくと、関係式 2 より
となるが、先の仮定より U r {\displaystyle U_{r}} が n の倍数で、定理 1 より U q m {\displaystyle U_{qm}} も n の倍数だから右辺は n の倍数、よって 2 Q n U s {\displaystyle 2Q^{n}U_{s}} も n の倍数である。定理の仮定より gcd ( n , 2 Q ) = 1 {\displaystyle \gcd(n,2Q)=1} だから U s {\displaystyle U_{s}} も n の倍数。しかし 0 ≤ s ≤ m − 1 {\displaystyle 0\leq s\leq m-1} だから s =0 つまり r は m の倍数である。
重要な事実は、特殊な素数を除いて、フェルマーの小定理の類似の定理が成り立つことである。ただしフェルマーの小定理に比べ、幾分状況は複雑である。
定理 5 p を奇素数とする。 p が P , Q , D のいずれも割り切らないとき
とおくと p は U ψ ( p ) {\displaystyle U_{\psi (p)}} を割り切る。
証明
( D p ) = 1 {\displaystyle \left({\frac {D}{p}}\right)=1} のとき関係式 10 から、
であるが、
より
であるが、 G n ( X , Y ) = X n − 1 + X n − 2 Y + ⋯ + Y n − 1 = ( X n − Y n ) / ( X − Y ) {\displaystyle G_{n}(X,Y)=X^{n-1}+X^{n-2}Y+\cdots +Y^{n-1}=(X^{n}-Y^{n})/(X-Y)} とおくと、右辺は
となる。 ( D p ) = 1 {\displaystyle \left({\frac {D}{p}}\right)=1} より C 2 ≡ D ( mod p ) {\displaystyle C^{2}\equiv D{\pmod {p}}} となる C ( mod p ) {\displaystyle C{\pmod {p}}} が存在する。 フェルマーの小定理より P p − 1 ≡ C p − 1 ≡ 1 ( mod p ) {\displaystyle P^{p-1}\equiv C^{p-1}\equiv 1{\pmod {p}}} なので
となる。 p は奇素数なので
がわかる。
( D p ) = − 1 {\displaystyle \left({\frac {D}{p}}\right)=-1} のとき再び関係式 10 から、
であるが、 1 < k < p {\displaystyle 1<k<p} のとき
の分母は p で割り切れないから、結局 ( p + 1 k ) {\displaystyle {\binom {p+1}{k}}} は p で割り切れなければならない。よって
となる。フェルマーの小定理より P p ≡ P ( mod p ) {\displaystyle P^{p}\equiv P{\pmod {p}}} で、オイラーの規準より
だから
である。
U n {\displaystyle U_{n}} の偶奇は次の定理から導かれる。
定理 6 n ≥ 0 とする。
証明 P, Q が共に偶数のとき漸化式
より U 2 , U 3 , ... , V 2 , V 3 , ... {\displaystyle U_{2},U_{3},\ldots ,V_{2},V_{3},\ldots } はすべて偶数である。 U 0 = 0 , V 0 = 2 , V 1 = P {\displaystyle U_{0}=0,V_{0}=2,V_{1}=P} より U 1 = 1 {\displaystyle U_{1}=1} を除いて U n , V n {\displaystyle U_{n},V_{n}} はすべて偶数である。
P が偶数で Q が奇数のとき
であるが、 U 0 = 0 , U 1 = 1 , V 0 = 2 , V 1 = P ≡ 0 ( mod 2 ) {\displaystyle U_{0}=0,U_{1}=1,V_{0}=2,V_{1}=P\equiv 0{\pmod {2}}} より V n {\displaystyle V_{n}} はつねに偶数で、 U n {\displaystyle U_{n}} の偶奇は n の偶奇と一致する。
P が奇数で Q が偶数のとき
であるが、 U 0 = 0 , U 1 = 1 , V 0 = 2 , V 1 = P ≡ 1 ( mod 2 ) {\displaystyle U_{0}=0,U_{1}=1,V_{0}=2,V_{1}=P\equiv 1{\pmod {2}}} より U n , V n ( n ≥ 1 ) {\displaystyle U_{n},V_{n}(n\geq 1)} はつねに奇数である。
P , Q が共に奇数のとき
であるが、 U 0 = 0 , U 1 = 1 , V 0 = 2 , V 1 = P ≡ 1 ( mod 2 ) {\displaystyle U_{0}=0,U_{1}=1,V_{0}=2,V_{1}=P\equiv 1{\pmod {2}}} より U n , V n {\displaystyle U_{n},V_{n}} は共に ≡ 0 , 1 , 1 , 0 , 1 , 1 , ... ( mod 2 ) {\displaystyle \equiv 0,1,1,0,1,1,\ldots {\pmod {2}}} となる。 つまり U n , V n {\displaystyle U_{n},V_{n}} は n が 3 の倍数のとき偶数、それ以外のとき奇数である。