「初等整数論/ルーカス数列」の版間の差分

2022年7月7日 (木) 00:09時点における最新版

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

P = α + β, Q = α β, D = (α - β)^{2}

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

a_{n + 2} = P a_{n + 1} - Q a_{n} (n = 0, 1, \dots)

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

a_{n} = ζ α^{n} + η β^{n} (n = 0, 1, \dots)

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

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

U_{n} = \frac{α^{n} - β^{n}}{α - β}, V_{n} = α^{n} + β^{n} (n = 0, 1, \dots) \dots (*)

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

U_{0} = 0, U_{1} = 1, V_{0} = 2, V_{1} = α + β = 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{{(\frac{1 + \sqrt{5}}{2})}^{n} - {(\frac{1 - \sqrt{5}}{2})}^{n}}{\sqrt{5}}, L_{n} = {(\frac{1 + \sqrt{5}}{2})}^{n} + {(\frac{1 - \sqrt{5}}{2})}^{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{matrix} V_{n}^{2} - D U_{n}^{2} = & 4 Q^{n}, \\ U_{n}^{2} - U_{n - 1} U_{n + 1} = & - Q^{n - 1} . \end{matrix}

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

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

関係式 2

\begin{matrix} 2 U_{m + n} = & U_{m} V_{n} + U_{n} V_{m}, \\ 2 Q^{n} U_{m - n} = & U_{m} V_{n} - U_{n} V_{m}, \\ U_{m + n} = & U_{m} U_{n + 1} - Q U_{m - 1} U_{n}, \\ 2 V_{m + n} = & V_{m} V_{n} + D U_{m} U_{n} . \end{matrix}

関係式 3

\begin{matrix} U_{m + n} = & U_{m} V_{n} - Q^{n} U_{m - n}, \\ V_{m + n} = & V_{m} V_{n} - Q^{n} V_{m - n} = D U_{m} U_{n} + Q^{n} V_{m - n} . \end{matrix}

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

関係式 4

\begin{matrix} D U_{n} = & V_{n + 1} - Q V_{n - 1}, \\ V_{n} = & U_{n + 1} - Q U_{n - 1} . \end{matrix}

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

関係式 5

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

関係式 6

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

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

\begin{matrix} (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}) (X Y)^{\frac{m}{2}} \\ = & \sum_{r = 0}^{\frac{m}{2} - 1} (\binom{m}{r}) (X Y)^{r} (X^{m - 2 r} + Y^{m - 2 r}) + (\binom{m}{m / 2}) (X Y)^{\frac{m}{2}}, \end{matrix}

m が奇数のとき

\begin{matrix} (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}) (X Y)^{r} (X^{m - 2 r} + Y^{m - 2 r}) . \end{matrix}

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

関係式 7
m が奇数のとき

\begin{matrix} D^{\frac{m - 1}{2}} U_{k}^{m} = & \sum_{r = 0}^{\frac{m - 1}{2}} (\binom{m}{r}) (- 1)^{r} Q^{k r} U_{k (m - 2 r)} \\ = & U_{k m} - (\binom{m}{1}) Q^{k} U_{k (m - 2)} + (\binom{m}{2}) Q^{2 k} U_{k (m - 4)} - \dots + (- 1)^{\frac{m - 1}{2}} (\binom{m}{(m - 1) / 2}) Q^{\frac{m - 1}{2} k} U_{k} \end{matrix}

および

\begin{matrix} V_{k}^{m} = & \sum_{r = 0}^{\frac{m - 1}{2}} (\binom{m}{r}) Q^{k r} V_{k (m - 2 r)} \\ = & U_{k m} + (\binom{m}{1}) Q^{k} V_{k (m - 2)} + (\binom{m}{2}) Q^{2 k} V_{k (m - 4)} + \dots + (\binom{m}{(m - 1) / 2}) Q^{\frac{m - 1}{2} k} V_{k} . \end{matrix}

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

\begin{matrix} D^{\frac{m}{2}} U_{k}^{m} = & \sum_{r = 0}^{\frac{m}{2} - 1} (\binom{m}{r}) (- 1)^{r} Q^{k r} V_{k (m - 2 r)} + (- 1)^{\frac{m}{2}} (\binom{m}{m / 2}) Q^{\frac{m k}{2}} \\ = & V_{k m} - (\binom{m}{1}) Q^{k} V_{k (m - 2)} + (\binom{m}{2}) Q^{2 k} V_{k (m - 4)} - \dots + (- 1)^{\frac{m}{2} - 1} (\binom{m}{m / 2 - 1}) Q^{(\frac{m}{2} - 1) k} V_{2 k} + (- 1)^{\frac{m}{2}} (\binom{m}{m / 2}) Q^{\frac{m k}{2}}, \end{matrix}

および

\begin{matrix} V_{k}^{m} = & \sum_{r = 0}^{\frac{m}{2} - 1} (\binom{m}{r}) Q^{k r} V_{k (m - 2 r)} + (\binom{m}{m / 2}) Q^{\frac{m k}{2}} \\ = & V_{k m} + (\binom{m}{1}) Q^{k} V_{k (m - 2)} + (\binom{m}{2}) Q^{2 k} V_{k (m - 4)} + \dots + (\binom{m}{m / 2 - 1}) Q^{(\frac{m}{2} - 1) k} V_{2 k} + (\binom{m}{m / 2}) Q^{\frac{m k}{2}} . \end{matrix}

成り立つ。

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

関係式 9
k が偶数のとき

U_{k m} = U_{m} \sum_{r = 0}^{\frac{k}{2} - 1} Q^{m r} V_{m (k - 1 - 2 r)} = U_{m} (V_{m (k - 1)} + Q^{m} V_{m (k - 3)} + \dots),

k が奇数のとき

U_{k m} = U_{m} (Q^{\frac{m (k - 1)}{2}} + \sum_{r = 0}^{\frac{k - 3}{2}} Q^{m r} V_{m (k - 1 - 2 r)})

および

V_{k m} = V_{m} ((- 1)^{\frac{k - 1}{2}} Q^{\frac{m (k - 1)}{2}} + \sum_{r = 0}^{\frac{k - 3}{2}} (- 1)^{r} Q^{m r} V_{m (k - 1 - 2 r)})

が成り立つ。

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

関係式 10

2^{n - 1} U_{n} = (\binom{n}{1}) P^{n - 1} + (\binom{n}{3}) P^{n - 3} D + \dots

2^{n - 1} V_{n} = P^{n} + (\binom{n}{2}) P^{n - 2} D + (\binom{n}{4}) P^{n - 4} D^{2} + \dots

関係式 11
m が偶数のとき

P^{m} = \sum_{r = 0}^{\frac{m}{2} - 1} (\binom{m}{r}) Q^{r} V_{m - 2 r} + (\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 - 2 r} = V_{m} + m Q V_{m - 2} + (\binom{m}{2}) Q^{2} V_{m - 4} + \dots .

ルーカス数列の合同式

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

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

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

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

定理 2
p が素数のとき

V_{p} \equiv P (\mod p)

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

U_{k p} \equiv (\frac{D}{p}) U_{k} (\mod p)

特に

U_{p} \equiv (\frac{D}{p}) (\mod p)

が成り立つ。

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

V_{p} \equiv P^{p} \equiv P (\mod p)

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

U_{k p} \equiv D^{\frac{p - 1}{2}} U_{k}^{p} \equiv (\frac{D}{p}) U_{k} (\mod p),

特に k =1 とおくと

U_{p} \equiv (\frac{D}{p}) (\mod p)

となる。

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

定理 3

V_{k} \equiv P^{k} (\mod Q),

U_{k} \equiv V_{k - 1} (\mod Q)

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

U_{k} = V_{k - 1} + Q V_{k - 3} + \dots \equiv V_{k - 1} (\mod Q)

が成り立つ。

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

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

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

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

2 Q^{n} U_{s} = 2 Q^{n} U_{r - q m} = U_{r} V_{q m} - U_{q m} V_{r}

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

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

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

ψ (p) = p - (\frac{D}{p})

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

証明

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

2^{p - 2} U_{p - 1} = (\binom{p - 1}{1}) P^{p - 2} + (\binom{p - 1}{3}) P^{p - 4} D + \dots + (\binom{p - 1}{p - 2}) P D^{\frac{p - 3}{2}}

であるが、

(\binom{p - 1}{k}) = \frac{(p - 1) (p - 2) \dots (p - k)}{1 \cdot 2 \dots k} \equiv (- 1)^{k} (\mod p)

より

2^{p - 2} U_{p} \equiv - (P^{p - 2} + P^{p - 4} D + \dots + P D^{\frac{p - 3}{2}}) (\mod p)

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

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

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

2^{p - 2} U_{p - 1} \equiv - P \cdot \frac{P^{p - 1} - C^{p - 1}}{P^{2} - C^{2}} \equiv 0 (\mod p)

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

U_{p - 1} \equiv 0 (\mod p)

がわかる。

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

2^{p} U_{p + 1} = (\binom{p + 1}{1}) P^{p} + (\binom{p + 1}{3}) P^{p - 2} D + \dots + (\binom{p + 1}{p}) P D^{\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} + P D^{\frac{p - 1}{2}}) \equiv P^{p} + P D^{\frac{p - 1}{2}}

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

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

だから

2^{p} U_{p + 1} \equiv P (1 + D^{\frac{p - 1}{2}}) \equiv 0 (\mod 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} = P U_{n + 1} - Q U_{n}, V_{n + 2} = P V_{n + 1} - Q V_{n}

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

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

U_{n + 2} = P U_{n + 1} - Q U_{n} \equiv U_{n}, V_{n + 2} = P V_{n + 1} - Q V_{n} \equiv V_{n} (\mod 2)

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

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

U_{n + 2} = P U_{n + 1} - Q U_{n} \equiv U_{n + 1}, V_{n + 2} = P V_{n + 1} - Q V_{n} \equiv V_{n + 1} (\mod 2)

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

P , Q が共に奇数のとき

U_{n + 2} = P U_{n + 1} - Q U_{n} \equiv U_{n + 1} + U_{n}, V_{n + 2} = P V_{n + 1} - Q V_{n} \equiv V_{n + 1} + V_{n} (\mod 2)

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

テンプレート:Nav

「初等整数論/ルーカス数列」の版間の差分

2022年7月7日 (木) 00:09時点における最新版

例

基本的な関係式

ルーカス数列の合同式

ナビゲーション メニュー

検索

ナビゲーションメニュー