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

P, Q, D を $D=P^{2}-4Q\neq 0$ となる整数とし、$\alpha ,\beta$ を2次方程式 $x^{2}-Px+Q=0$ の解とする（D ≠ 0 より この2次方程式は2つの相異なる解をもつ）。 このとき

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

が成り立つ。 線形回帰数列 で述べたように、数列 $a_{n}(n=0,1,\ldots )$ について、 漸化式

$a_{n+2}=Pa_{n+1}-Qa_{n}(n=0,1,\ldots )$

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

$a_{n}=\zeta \alpha ^{n}+\eta \beta ^{n}(n=0,1,\ldots )$

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

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

$U_{n}={\frac {\alpha ^{n}-\beta ^{n}}{\alpha -\beta }},V_{n}=\alpha ^{n}+\beta ^{n}(n=0,1,\ldots )\cdots (*)$

により定まる数列 $U_{n},V_{n}$ はいずれも上記の漸化式を満足し、初項は

$U_{0}=0,U_{1}=1,V_{0}=2,V_{1}=\alpha +\beta =P$

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

このようにして定まる数列 $U_{n},V_{n}$ を $(P,Q)$ に関するルーカス数列と呼ぶ。 また、数列 $U_{n}$ のみを単にルーカス数列といい、$V_{n}$ を同伴ルーカス数列と呼ぶこともある。

例

フィボナッチ数列 $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}$ により定まり、 2, 1, 3, 4, 7, 11, 18, 29, 47, ... で始まる。 そして、これらの数列の一般項は

$F_{n}={\frac {\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}-\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}}{\sqrt {5}}},L_{n}=\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}+\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}$

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

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

$U_{n}={\frac {(1+{\sqrt {2}})^{n}-(1-{\sqrt {2}})^{n}}{2{\sqrt {2}}}},V_{n}=(1+{\sqrt {2}})^{n}+(1-{\sqrt {2}})^{n}$

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

基本的な関係式

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

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

関係式 1

${\begin{aligned}V_{n}^{2}-DU_{n}^{2}=&4Q^{n},\\U_{n}^{2}-U_{n-1}U_{n+1}=&-Q^{n-1}.\end{aligned}}$

特に、$Q=\pm 1$ のとき、 $U_{n},V_{n}$ はペル方程式の解となっていることがわかる。例えばペル数列に対し、$X=V_{n}/2,Y=U_{n}$ とおくとペル方程式 $X^{2}-2Y^{2}=\pm 1$ の解が得られる。

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

関係式 2

${\begin{aligned}2U_{m+n}=&U_{m}V_{n}+U_{n}V_{m},\\2Q^{n}U_{m-n}=&U_{m}V_{n}-U_{n}V_{m},\\U_{m+n}=&U_{m}U_{n+1}-QU_{m-1}U_{n},\\2V_{m+n}=&V_{m}V_{n}+DU_{m}U_{n}.\end{aligned}}$

関係式 3

${\begin{aligned}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}.\end{aligned}}$

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

関係式 4

${\begin{aligned}DU_{n}=&V_{n+1}-QV_{n-1},\\V_{n}=&U_{n+1}-QU_{n-1}.\end{aligned}}$

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

関係式 5

${\begin{aligned}U_{2n}=&U_{n}V_{n},\\V_{2n}=&V_{n}^{2}-2Q^{n}.\end{aligned}}$

関係式 6

${\begin{aligned}U_{3n}=&U_{n}(V_{n}^{2}-Q^{n})=U_{n}(DU_{n}^{2}+3Q^{n}),\\V_{3n}=&V_{n}(V_{n}^{2}-3Q^{n}).\end{aligned}}$

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

${\begin{aligned}(X+Y)^{m}=&\sum _{r=0}^{m}{\binom {m}{r}}X^{r}Y^{m-r}\\=&\sum _{r=0}^{{\frac {m}{2}}-1}{\binom {m}{r}}(X^{r}Y^{m-r}+X^{m-r}Y^{r})+{\binom {m}{m/2}}(XY)^{\frac {m}{2}}\\=&\sum _{r=0}^{{\frac {m}{2}}-1}{\binom {m}{r}}(XY)^{r}(X^{m-2r}+Y^{m-2r})+{\binom {m}{m/2}}(XY)^{\frac {m}{2}},\end{aligned}}$

m が奇数のとき

${\begin{aligned}(X+Y)^{m}=&\sum _{r=0}^{m}{\binom {m}{r}}X^{r}Y^{m-r}\\=&\sum _{r=0}^{\frac {m-1}{2}}{\binom {m}{r}}(X^{r}Y^{m-r}+X^{m-r}Y^{r})\\=&\sum _{r=0}^{\frac {m-1}{2}}{\binom {m}{r}}(XY)^{r}(X^{m-2r}+Y^{m-2r}).\end{aligned}}$

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

関係式 7
m が奇数のとき

${\begin{aligned}D^{\frac {m-1}{2}}U_{k}^{m}=&\sum _{r=0}^{\frac {m-1}{2}}{\binom {m}{r}}(-1)^{r}Q^{kr}U_{k(m-2r)}\\=&U_{km}-{\binom {m}{1}}Q^{k}U_{k(m-2)}+{\binom {m}{2}}Q^{2k}U_{k(m-4)}-\cdots +(-1)^{\frac {m-1}{2}}{\binom {m}{(m-1)/2}}Q^{{\frac {m-1}{2}}k}U_{k}\end{aligned}}$

および

${\begin{aligned}V_{k}^{m}=&\sum _{r=0}^{\frac {m-1}{2}}{\binom {m}{r}}Q^{kr}V_{k(m-2r)}\\=&U_{km}+{\binom {m}{1}}Q^{k}V_{k(m-2)}+{\binom {m}{2}}Q^{2k}V_{k(m-4)}+\cdots +{\binom {m}{(m-1)/2}}Q^{{\frac {m-1}{2}}k}V_{k}.\end{aligned}}$

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

${\begin{aligned}D^{\frac {m}{2}}U_{k}^{m}=&\sum _{r=0}^{{\frac {m}{2}}-1}{\binom {m}{r}}(-1)^{r}Q^{kr}V_{k(m-2r)}+(-1)^{\frac {m}{2}}{\binom {m}{m/2}}Q^{\frac {mk}{2}}\\=&V_{km}-{\binom {m}{1}}Q^{k}V_{k(m-2)}+{\binom {m}{2}}Q^{2k}V_{k(m-4)}-\cdots +(-1)^{{\frac {m}{2}}-1}{\binom {m}{m/2-1}}Q^{\left({\frac {m}{2}}-1\right)k}V_{2k}+(-1)^{\frac {m}{2}}{\binom {m}{m/2}}Q^{\frac {mk}{2}},\end{aligned}}$

および

${\begin{aligned}V_{k}^{m}=&\sum _{r=0}^{{\frac {m}{2}}-1}{\binom {m}{r}}Q^{kr}V_{k(m-2r)}+{\binom {m}{m/2}}Q^{\frac {mk}{2}}\\=&V_{km}+{\binom {m}{1}}Q^{k}V_{k(m-2)}+{\binom {m}{2}}Q^{2k}V_{k(m-4)}+\cdots +{\binom {m}{m/2-1}}Q^{\left({\frac {m}{2}}-1\right)k}V_{2k}+{\binom {m}{m/2}}Q^{\frac {mk}{2}}.\end{aligned}}$

成り立つ。

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

関係式 9
k が偶数のとき

$U_{km}=U_{m}\sum _{r=0}^{{\frac {k}{2}}-1}Q^{mr}V_{m(k-1-2r)}=U_{m}(V_{m(k-1)}+Q^{m}V_{m(k-3)}+\cdots ),$

k が奇数のとき

$U_{km}=U_{m}\left(Q^{\frac {m(k-1)}{2}}+\sum _{r=0}^{\frac {k-3}{2}}Q^{mr}V_{m(k-1-2r)}\right)$

および

$V_{km}=V_{m}\left((-1)^{\frac {k-1}{2}}Q^{\frac {m(k-1)}{2}}+\sum _{r=0}^{\frac {k-3}{2}}(-1)^{r}Q^{mr}V_{m(k-1-2r)}\right)$

が成り立つ。

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

関係式 10

$2^{n-1}U_{n}={\binom {n}{1}}P^{n-1}+{\binom {n}{3}}P^{n-3}D+\cdots$

$2^{n-1}V_{n}=P^{n}+{\binom {n}{2}}P^{n-2}D+{\binom {n}{4}}P^{n-4}D^{2}+\cdots$

関係式 11
m が偶数のとき

$P^{m}=\sum _{r=0}^{{\frac {m}{2}}-1}{\binom {m}{r}}Q^{r}V_{m-2r}+{\binom {m}{m/2}}Q^{\frac {m}{2}},$

m が奇数のとき

$P^{m}=\sum _{r=0}^{\frac {m-1}{2}}{\binom {m}{r}}Q^{r}V_{m-2r}=V_{m}+mQV_{m-2}+{\binom {m}{2}}Q^{2}V_{m-4}+\cdots .$

ルーカス数列の合同式

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

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

定理 1
k が整数のとき、 $U_{m}$ は $U_{km}$ を割り切る。 また k が奇数のとき、 $V_{m}$ は $V_{km}$ を割り切る。

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

定理 2
p が素数のとき

$V_{p}\equiv P{\pmod {p}}$

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

$U_{kp}\equiv \left({\frac {D}{p}}\right)U_{k}{\pmod {p}}$

特に

$U_{p}\equiv \left({\frac {D}{p}}\right){\pmod {p}}$

が成り立つ。

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

$V_{p}\equiv P^{p}\equiv P{\pmod {p}}$

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

$U_{kp}\equiv D^{\frac {p-1}{2}}U_{k}^{p}\equiv \left({\frac {D}{p}}\right)U_{k}{\pmod {p}},$

特に k =1 とおくと

$U_{p}\equiv \left({\frac {D}{p}}\right){\pmod {p}}$

となる。

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

定理 3

$V_{k}\equiv P^{k}{\pmod {Q}},$

$U_{k}\equiv V_{k-1}{\pmod {Q}}$

証明
関係式 11 から $V_{k}\equiv P^{k}{\pmod {Q}}$ はすぐわかる。 また、関係式 9 で m=1 とおくと

$U_{k}=V_{k-1}+QV_{k-3}+\cdots \equiv V_{k-1}{\pmod {Q}}$

が成り立つ。

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

定理 4
$\gcd(n,2Q)=1$ かつ n の倍数となる $U_{r}$ が存在するとき、 $n|U_{r}\iff \rho (n)|r$ が成り立つ。

証明
定理 1 より r が $m=\rho (n)$ の倍数ならば n は $U_{r}$ を割り切る。

$U_{r}$ が n の倍数と仮定する。 $r=qm+s,0\leq s\leq m-1$ とおくと、関係式 2 より

$2Q^{n}U_{s}=2Q^{n}U_{r-qm}=U_{r}V_{qm}-U_{qm}V_{r}$

となるが、先の仮定より $U_{r}$ が n の倍数で、定理 1 より $U_{qm}$ も n の倍数だから右辺は n の倍数、よって $2Q^{n}U_{s}$ も n の倍数である。定理の仮定より $\gcd(n,2Q)=1$ だから $U_{s}$ も n の倍数。しかし $0\leq s\leq m-1$ だから s =0 つまり r は m の倍数である。

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

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

$\psi (p)=p-\left({\frac {D}{p}}\right)$

とおくと p は $U_{\psi (p)}$ を割り切る。

証明

$\left({\frac {D}{p}}\right)=1$ のとき関係式 10 から、

$2^{p-2}U_{p-1}={\binom {p-1}{1}}P^{p-2}+{\binom {p-1}{3}}P^{p-4}D+\cdots +{\binom {p-1}{p-2}}PD^{\frac {p-3}{2}}$

であるが、

${\binom {p-1}{k}}={\frac {(p-1)(p-2)\cdots (p-k)}{1\cdot 2\cdots k}}\equiv (-1)^{k}{\pmod {p}}$

より

$2^{p-2}U_{p}\equiv -(P^{p-2}+P^{p-4}D+\cdots +PD^{\frac {p-3}{2}}){\pmod {p}}$

であるが、$G_{n}(X,Y)=X^{n-1}+X^{n-2}Y+\cdots +Y^{n-1}=(X^{n}-Y^{n})/(X-Y)$ とおくと、右辺は

$-PG_{(p-1)/2}(P^{2},D)=-P\cdot {\frac {P^{p-1}-D^{\frac {p-1}{2}}}{P^{2}-D}}$

となる。 $\left({\frac {D}{p}}\right)=1$ より $C^{2}\equiv D{\pmod {p}}$ となる $C{\pmod {p}}$ が存在する。 フェルマーの小定理より $P^{p-1}\equiv C^{p-1}\equiv 1{\pmod {p}}$ なので

$2^{p-2}U_{p-1}\equiv -P\cdot {\frac {P^{p-1}-C^{p-1}}{P^{2}-C^{2}}}\equiv 0{\pmod {p}}$

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

$U_{p-1}\equiv 0{\pmod {p}}$

がわかる。

$\left({\frac {D}{p}}\right)=-1$ のとき再び関係式 10 から、

$2^{p}U_{p+1}={\binom {p+1}{1}}P^{p}+{\binom {p+1}{3}}P^{p-2}D+\cdots +{\binom {p+1}{p}}PD^{\frac {p-1}{2}}$

であるが、$1<k<p$ のとき

${\binom {p+1}{k}}={\frac {(p+1)!}{k!(p+1-k)!}}$

の分母は p で割り切れないから、結局 ${\binom {p+1}{k}}$ は p で割り切れなければならない。よって

$2^{p}U_{p+1}\equiv (p+1)(P^{p}+PD^{\frac {p-1}{2}})\equiv P^{p}+PD^{\frac {p-1}{2}}$

となる。フェルマーの小定理より $P^{p}\equiv P{\pmod {p}}$ で、オイラーの規準より

$D^{\frac {p-1}{2}}\equiv \left({\frac {D}{p}}\right)=-1$

だから

$2^{p}U_{p+1}\equiv P(1+D^{\frac {p-1}{2}})\equiv 0{\pmod {p}}$

である。

$U_{n}$ の偶奇は次の定理から導かれる。

定理 6
n ≥ 0 とする。

• P , Q が共に偶数ならば $U_{n},V_{n}$ は $U_{1}=1$ を除いてすべて偶数である。
• P が偶数で Q が奇数ならば $V_{n}$ はつねに偶数で、 $U_{n}$ の偶奇は n の偶奇と一致する。
• P が奇数で Q が偶数ならば $U_{n},V_{n}(n\geq 1)$ はつねに奇数である。
• P , Q が共に奇数ならば $U_{n},V_{n}$ は n が 3 の倍数のとき偶数、それ以外のとき奇数である。

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

$U_{n+2}=PU_{n+1}-QU_{n},V_{n+2}=PV_{n+1}-QV_{n}$

より $U_{2},U_{3},\ldots ,V_{2},V_{3},\ldots$ はすべて偶数である。 $U_{0}=0,V_{0}=2,V_{1}=P$ より $U_{1}=1$ を除いて $U_{n},V_{n}$ はすべて偶数である。

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

$U_{n+2}=PU_{n+1}-QU_{n}\equiv U_{n},V_{n+2}=PV_{n+1}-QV_{n}\equiv V_{n}{\pmod {2}}$

であるが、$U_{0}=0,U_{1}=1,V_{0}=2,V_{1}=P\equiv 0{\pmod {2}}$ より $V_{n}$ はつねに偶数で、 $U_{n}$ の偶奇は n の偶奇と一致する。

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

$U_{n+2}=PU_{n+1}-QU_{n}\equiv U_{n+1},V_{n+2}=PV_{n+1}-QV_{n}\equiv V_{n+1}{\pmod {2}}$

であるが、$U_{0}=0,U_{1}=1,V_{0}=2,V_{1}=P\equiv 1{\pmod {2}}$ より $U_{n},V_{n}(n\geq 1)$ はつねに奇数である。

P , Q が共に奇数のとき

$U_{n+2}=PU_{n+1}-QU_{n}\equiv U_{n+1}+U_{n},V_{n+2}=PV_{n+1}-QV_{n}\equiv V_{n+1}+V_{n}{\pmod {2}}$

であるが、$U_{0}=0,U_{1}=1,V_{0}=2,V_{1}=P\equiv 1{\pmod {2}}$ より $U_{n},V_{n}$ は共に $\equiv 0,1,1,0,1,1,\ldots {\pmod {2}}$ となる。 つまり $U_{n},V_{n}$ は n が 3 の倍数のとき偶数、それ以外のとき奇数である。