Lucas数列
$\newcommand{\N}{\mathbb{N}}$ $\newcommand{\Z}{\mathbb{Z}}$ $\newcommand{\Q}{\mathbb{Q}}$ $\newcommand{\R}{\mathbb{R}}$ $\newcommand{\C}{\mathbb{C}}$ $\newcommand{\K}{\mathbb{K}}$ $\newcommand{\abs}[1]{\left\lvert#1\right\rvert}$ $\newcommand{\wenvert}[1]{\left\lvert\left\lvert#1\right\rvert\right\rvert}$ $\newcommand{\floor}[1]{\left\lfloor#1\right\rfloor}$ $\newcommand{\mathmod}[1]{\ \left(\mathrm{mod}\ #1\right)}$ $\newcommand{\LCM}{\mathrm{LCM}}$
証明については、下位記事
を参照。
本稿では、2階の線形回帰数列の中でも、特別なものについて取り扱う。2次方程式 $$x^2-Px+Q=0$$ の解を $$\alpha=\frac{P+\sqrt{D}}{2}, \beta=\frac{P-\sqrt{D}}{2}$$ とおいて、$n\in\Z$ に対して $u_n=u_n(P, Q), v_n=v_n(P, Q)$ を $$u_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}, v_n=\alpha^n+\beta^n (0.1)$$ と定義すると、直接計算あるいは線形回帰数列:定理2より $$u_0=0, u_1=1, v_0=2, v_1=P (0.2)$$ かつ $$u_{n+2}=Pu_{n+1}-Qu_n, v_{n+2}=Pv_{n+1}-Qv_n (0.3)$$ となることが容易に確かめられる。これによって定まる数列 $(u_n)_{n\in\Z}=(u_n(P, Q))_{n\in\Z}$, $(v_n)_{n\in\Z}=(v_n(P, Q))_{n\in\Z}$ を $(P, Q)$ に関するLucas数列という。 また $(v_n)_{n\in\Z}=(v_n(P, Q))_{n\in\Z}$ を $(P, Q)$ に関する同伴Lucas数列ともいう。
例
例 1
Fibonacci数列 Fibonacci数列 (OEIS:A000045) $$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, \ldots$$ は漸化式 $$F_0=0, F_1=1, F_{n+2}=F_{n+1}+F_n\ (n=0, 1, \ldots)$$ により定義され、 $$\alpha=\frac{1+\sqrt{5}}{2}, \beta=\frac{1-\sqrt{5}}{2}$$ を方程式 $$x^2-x-1=0$$ の解とすると、 $$F_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}$$ とあらわされる。よって $F_n=u_n(1, -1)$ となる。 この同伴Lucas数列 $$2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, 322, \ldots$$ は漸化式 $$L_0=2, L_1=1, L_{n+2}=L_{n+1}+L_n\ (n=0, 1, \ldots)$$ を満足し、 $$L_n=v_n(1, -1)=\alpha^n+\beta^n$$ で与えられる。 Fibonacci数列の同伴数列に属する数をLucas数という（数列自体をLucas数列と呼ぶことは一般的なLucas数列と混同を招く）。
例 2
$(P, Q)=(2, -1)$ に関するLucas数列 $$\begin{split} P_n= & \frac{(1+\sqrt{2})^n-(1-\sqrt{2})^n}{2\sqrt{2}}, \\ Q_n= & (1+\sqrt{2})^n+(1-\sqrt{2})^n \end{split}$$ は漸化式 $$\begin{split} P_0= & 0, P_1=1, P_{n+2}=2P_{n+1}+P_n\ (n=0, 1, \ldots) \\ Q_0=& 2, Q_1=2, Q_{n+2}=2Q_{n+1}+Q_n\ (n=0, 1, \ldots) \end{split}$$ を満足し、最初の数項は $$\begin{split} P_n=u_n(2, -1): & 0, 1, 2, 5, 12, 29, 70, 169, 408, \ldots, \\ Q_n=v_n(2, -1): & 2, 2, 6, 14, 34, 82, 198, 478, 1154, \ldots \end{split}$$ で与えられる。 さらに $(x, y)=(P_n, Q_n/2)$ はPell方程式 $$y^2-2x^2=(-1)^n$$ の自然数解である（さらに、このPell方程式の自然数解はすべて $(P_n, Q_n/2)$ で与えられることが知られている）。 それで、これらの数列をそれぞれPell数列(OEIS:A000129)、同伴Pell数列 (OEIS: A002203)という。
例 3
$a>b$ で $(P, Q)=(a+b, ab)$ のとき $\alpha=a, \beta=b$ となるので、 $(P, Q)=(a+b, ab)$ に関するLucas数列は $$u_n=\frac{a^n-b^n}{a-b}, v_n=a^n+b^n$$ で与えられる。とくに $a\neq 1$ のとき、$(P, Q)=(a+1, a)$ に関するLucas数列は $$u_n=\frac{a^n-1}{a-1}, v_n=a^n+1$$ で与えられる。$a$ が $2$ 以上の整数のとき、この $u_n$ は $a$ を基数とするrepunitとなる。とくに $a=2$ のとき $u_n=2^n-1$ はMersenne数 (OEIS: A000225) を、 $v_n=2^n+1$ は $n=2^m$ のときFermat数 (OEIS: A000215) を与える。
関係式
以下、とくに明記しない限り、$m, n, r\in\Z$ は任意の整数とする。
$$\begin{split} u_{-n}= & -\frac{u_n}{Q^n}, \\ v_{-n}= & \frac{v_n}{Q^n}. \end{split} \ \ (2.1)$$
$(2.2)$ $P, Q$ が実数で $P>0, D=P^2-4Q>0$ のとき、 $$\begin{split} \lim_{n\rightarrow\infty} \frac{u_n}{\alpha^n}= & \frac{1}{\alpha-\beta}, \\ \lim_{n\rightarrow\infty} \frac{v_n}{\alpha^n}= & 1 \\ \end{split}$$
$$\begin{split} \frac{v_n+u_n\sqrt{D}}{2}= & \left(\frac{v_1+u_1\sqrt{D}}{2}\right)^n, \\ \frac{v_n-u_n\sqrt{D}}{2}= & \left(\frac{v_1-u_1\sqrt{D}}{2}\right)^n. \end{split}\ \ (2.3)$$ とくに $D$ が平方数ではないとき、 $$\alpha^n=\frac{x+y\sqrt{D}}{2} \Longleftrightarrow (x, y)=(u_n, v_n)$$ が成り立つ。
$$v_n^2-Du_n^2=4Q^n.\ \ (2.4)$$
$$\begin{split} u_{m+n}= & \frac{u_m v_n+u_n v_m}{2}, \\ v_{m+n}= & \frac{v_m v_n+Du_m u_n}{2}. \end{split}\ \ (2.5)$$ とくに $$u_{2n}=u_n v_n, v_{2n}=v_n^2-2Q^n (2.5a).$$
$$\begin{split} 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{split} \ \ (2.5b)$$
また、$u_{-n}=-u_n/Q^n, v_{-n}=v_n/Q^n$ だから $$\begin{split} u_{m-n}= & \frac{u_m v_n-u_n v_m}{2Q^n}, \\ v_{m-n}= & \frac{v_m v_n-Du_m u_n}{2Q^n}. \end{split} \ \ (2.5c)$$
$$\begin{split} u_{rn}= & \frac{(u_r+v_r\sqrt{D})^n-(u_r-v_r\sqrt{D})^n}{2\sqrt{D}}, \\ v_{rn}= & (u_r+v_r\sqrt{D})^n+(u_r-v_r\sqrt{D})^n. \end{split} \ \ (2.6a)$$
$$\begin{split} \frac{u_{rn}(P, Q)}{u_r(P, Q)}= & u_n(v_r, Q^r), \\ v_{rn}(P, Q)= & v_n(v_r, Q^r). \end{split} \ \ (2.6b)$$ とくに、$P, Q$ が整数のとき $u_{rn}$ は $u_r$ で割り切れる。
$$\begin{split} u_{n+2r}= & v_r u_{n+r}-Q^r u_n, \\ v_{n+2r}= & v_r v_{n+r}-Q^r v_n=Du_r u_{n+r}+Q^r v_n. \end{split} \ \ (2.7)$$
より一般的な、添字の $k$倍公式を示すために、次の等式を用いる。
$(2.8)$ $m$ が偶数のとき $$\begin{split} (X+Y)^m= & \sum_{r=0}^m \binom{m}{r}X^r Y^{m-r} \\ = & \sum_{r=0}^{(m/2)-1} \binom{m}{r}(X^r Y^{m-r}+X^{m-r}Y^r) + \binom{m}{m/2}(XY)^{m/2} \\ = & \sum_{r=0}^{(m/2)-1} \binom{m}{r}(XY)^r(X^{m-2r}+Y^{m-2r}) + \binom{m}{m/2}(XY)^{m/2}, \end{split}$$ $m$ が奇数のとき $$\begin{split} (X+Y)^m= & \sum_{r=0}^m \binom{m}{r}X^r Y^{m-r} \\ = & \sum_{r=0}^{(m-1)/2} \binom{m}{r}(X^r Y^{m-r}+X^{m-r}Y^r) \\ = & \sum_{r=0}^{(m-1)/2} \binom{m}{r}(XY)^r(X^{m-2r}+Y^{m-2r}). \end{split}$$
$(2.9)$ $m$ が奇数で $k$ が正の整数のとき $$\begin{split} D^{(m-1)/2}u_k^m= & \sum_{r=0}^{(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)^{(m-1)/2} \binom{m}{(m-1)/2}Q^{k(m-1)/2}u_k \end{split}$$ かつ $$\begin{split} v_k^m= & \sum_{r=0}^{(m-1)/2} \binom{m}{r} Q^{kr} v_{k(m-2r)} \\ = & v_{km}+\binom{m}{1}Q^k v_{k(m-2)}+\cdots +\binom{m}{(m-1)/2}Q^{k(m-1)/2}v_k. \end{split}$$
$(2.10)$ $m$ が偶数で $k$ が正の整数のとき $$\begin{split} D^{m/2}u_k^m = & \sum_{r=0}^{(m/2)-1} \binom{m}{r}(-1)^r Q^{kr} v_{k(m-2r)} + (-1)^{m/2} \binom{m}{m/2}Q^{km/2} \\ = & V_{km}-\binom{m}{1}Q^k v_{k(m-2)}+\binom{m}{2}Q^{2k} v_{k(m-4)}-\cdots +(-1)^{(m/2)-1} \binom{m}{m/2-1}Q^{\left(\frac{m}{2}-1\right)k} v_{2k} +(-1)^{m/2} \binom{m}{m/2}Q^{km/2}, \end{split}$$ および $$\begin{split} v_k^m= & \sum_{r=0}^{(m/2)-1} \binom{m}{r}Q^{kr} v_{k(m-2r)} + \binom{m}{m/2}Q^{km/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^{km/2}. \end{split}$$ が成り立つ。
$(2.11)$ $k$ が偶数のとき $$\frac{u_{km}}{u_m}=\sum_{r=0}^{(k/2)-1}Q^{mr} v_{m(k-1-2r)}=v_{m(k-1)}+Q^m v_{m(k-3)}+\cdots +Q^{m\left(\frac{m}{2}-1\right)}v_m,$$ $k$ が奇数のとき $$\begin{split} \frac{u_{km}}{u_m}= & Q^{m(k-1)/2}+\sum_{r=0}^{(k-3)/2}Q^{mr} v_{m(k-1-2r)} \\ = & v_{m(k-1)}+Q^m v_{m(k-3)}+\cdots +Q^{m(k-1)/2} \end{split}$$ および $$\frac{v_{km}}{v_m}=(-1)^{(k-1)/2} Q^{m(k-1)/2}+\sum_{r=0}^{(k-3)/2}(-1)^r Q^{mr} v_{m(k-1-2r)}$$ が成り立つ。
$(2.12)$ $$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.$$
$(2.13)$ $m$ が偶数のとき $$P^m=\sum_{r=0}^{(m/2)-1} \binom{m}{r}Q^r v_{m-2r} + \binom{m}{m/2}Q^{m/2},$$ $m$ が奇数のとき $$P^m=\sum_{r=0}^{(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.$$
そのほか、以下のような関係式も成り立つ。
$$\begin{split} u_{nr}^2-u_{(n-1)r}u_{(n+1)r}= & Q^{(n-1)r}u_r^2, \\ v_{nr}^2-v_{(n-1)r}v_{(n+1)r}= & -Q^{(n-1)r}Du_r^2. \end{split} \ \ (2.14)$$
$$\begin{split} Du_n= & v_{n+1}-Qv_{n-1}, \\ v_n= & u_{n+1}-Qu_{n-1}. \end{split} \ \ (2.15)$$
$$\begin{split} u_{n+r}^2-Q^r u_n^2=u_n u_{2n+r}, \\ v_{n+r}~2-Q^r v_n^2=Du_r u_{2n+r}. \end{split} \ \ (2.16)$$
$$\begin{split} u_{m+n}+Q^n u_{m-n}= & u_m v_n, \\ u_{m+n}-Q^n u_{m-n}= & u_n v_m \end{split} \ \ (2.17a)$$ および $$\begin{split} v_{m+n}+Q^n v_{m-n}= & 2v_m v_n, \\ v_{m+n}-Q^n v_{m-n}= & Du_m u_n \end{split} \ \ (2.17b)$$ が成り立つ。
Lucas数列の整除性および合同
上に挙げた関係式を用いて、Lucas数列の整除性および合同に関する重要な性質が導かれる。
定理 1
$k, m\in\Z$ のとき、 $u_m\mid u_{km}$. $k, m\in\Z$ で $k$ が奇数のとき、$v_m\mid v_{km}$.
定理 2
$p$ が素数ならば $$v_p\equiv P\mathmod{p}. \ \ (3.1)$$ さらに $p$ が奇素数ならば $$u_{kp}\equiv \left(\frac{D}{p}\right)u_k\mathmod{p}.$$ とくに $$u_{p^e}\equiv \left(\frac{D}{p}\right)^e\mathmod{p}.$$
つぎの定理はFermatの小定理の一般化となっている、重要な定理である。
定理 3
$p$ が $P, Q, D$ のいずれも割り切らない奇素数ならば $p$ は $u_{p-(D/p)}$ を割り切る。
$a\not\equiv 0, \pm 1\mathmod{p}$ となる整数 $a$ について $P=a+1, Q=a$ のとき $D=(a-1)^2$ となるので、 $(D/p)=1$ となる。 例 3にあるように $u_n(P, Q)=(a^n-1)/(a-1)$ なのでこの定理は、 $$\frac{a^{p-1}-1}{a-1}\equiv 0\mathmod{p}$$ となり、通常のFermatの定理と一致する。
なお、つぎの合同式も成り立つ。
定理 4
$n\geq 1$ のとき $$u_n\equiv v_{n-1}\mathmod{Q}$$ かつ $$v_n\equiv P^n\mathmod{Q}$$ が成り立つ。
残るのは $p=2$ の場合と、$p$ が $P, Q, D$ のいずれかを割り切る場合だが、$u_n, v_n$ が $p=2$ で割れるかどうか、つまり $u_n, v_n$ の偶奇はつぎのようにしてわかる。
定理 5
- $P, Q$ がともに偶数のとき $n\geq 2$ に対して $u_n$ は偶数で、$n\geq 0$ のとき $v_n$ は偶数。
- $P$ が奇数で $Q$ が偶数ならば $n\geq 1$ のとき $u_n, v_n$ は奇数。
- $P$ が偶数で $Q$ が奇数ならば $n\geq 0$ のとき $u_n$ の偶奇は $n$ の偶奇と一致し、$v_n$ はつねに偶数。
- $P, Q$ がともに奇数のとき $u_n, v_n$ は $n$ が $3$ の倍数のとき偶数で、それ以外のとき奇数。
$p$ が $P, Q, D$ のいずれかの素因数の場合、$u_n, v_n$ が $p$ の倍数となる場合はつぎのようにしてわかる。
定理 6
- $p$ が $P, Q$ をともに割り切る奇素数のとき $n\geq 2$ ならば $p$ は $u_n$ を割り切る。
- $p$ が $P$ を割り切るが $Q$ を割り切らない奇素数のとき $n\geq 0$ が偶数のとき $p$ は $u_n$ を割り切り、$n\geq 0$ が奇数のとき $p$ は $u_n$ を割り切らない。
- $p$ が $P$ を割り切らないが $Q$ を割り切る奇素数のとき $n\geq 1$ に対して、 $p$ は $u_n$ を割り切らない。
- $p$ が $P, Q$ をいずれも割り切らないが $D$ を割り切る奇素数のとき、ちょうど $p$ が $n$ を割り切るときに $p$ が $u_n$ も割り切る。
$n\mid u_k$ となる正の整数 $k$ が存在するとき、$n\mid u_k$ となる最小の正の整数 $k$ を $\rho(n)$ とおく。 定理 3および定理 6より $p$ が $2Q$ を割り切らないとき $\rho(p)$ が存在することがわかる。 $\rho(n)$ は乗法的位数と類似した性質をもっている。たとえば、次の定理が成り立つ。
定理 7
$n\mid u_k$ となる正の整数 $k$ が存在し、$\gcd(n, 2Q)=1$ かつ $m\geq 0$ のとき $$n\mid u_m\Longleftrightarrow \rho(n)\mid m.$$
定理 8
$p$ が $2Q$ を割り切らない素数とすると、
- $p\mid P$ のとき $\rho(p)=2$.
- $p\nmid P$ かつ $p\mid D$ のとき $\rho(p)=p$.
- $p\nmid PD$ のとき、$\rho(p)\mid (p-(D/p))$.
さらに、LTEの補題の一般化が成り立つ。
まず、次の補題が成り立つ。
補題 1
$p$ が $P$ を割り切らないが $D$ を割り切る奇素数で、$p=3$ のときはさらに $p^2$ が $D$ を割り切るならば $p\mid\mid u_p$.
定理 9
$p$ は奇素数、$e, m$ は正の整数で $f$ は $0$ 以上の整数とする。 $p^e\mid\mid u_m, p^f\mid\mid k$ のとき $p^{e+f}$ は $u_{km}$ を割り切る。さらに $p$ が $Q$ を割り切らないとき $$p^{e+f}\mid\mid u_{km}$$ となる。
$p=2$ で割り切れる回数については、つぎのことがいえる。
定理 10
$P$ が偶数で $Q$ が奇数のとき、$2^h\mid\mid P$ とおくと、 $2^f\mid\mid k$ ならば $$2^{f+h-1}\mid\mid u_k$$ となる。
$P, Q$ がともに奇数のとき、$k$ を $3$ の倍数とし（定理 5 より $u_k$ が偶数ならば $k$ は $3$ の倍数である）、 $2^f\mid\mid k$ となる整数 $k\geq 0$ をとる。 $P^2-Q$ が $4$ の倍数の場合は $2^h\mid\mid (P^2-Q)$ となる $h\geq 2$ をとると、 $$2^{f+h}\mid\mid u_k$$ となる。 $P, Q$ がともに奇数で $2\mid\mid (P^2-Q)$ のときは $2^h\mid\mid (P^2-3Q)$ となる $h\geq 2$ をとると $k$ が $3$ の奇数倍のときは $2\mid\mid u_k$, $k$ が $3$ の偶数倍で $2^f\mid\mid k$ ならば $f\geq 1$ のとき $$2^{f+h}\mid\mid u_k$$ となる。
このことから、$2$ で割り切れる階数について、つぎのようなLTEの補題の一般化が成り立つ。
定理 11
$e, m$ は正の整数で $f, k$ は $0$ 以上の整数で、 $$2^e\mid\mid u_m, 2^f\mid\mid k$$ となるとする。このとき $2^{e+f}$ は $u_{km}$ を割り切る。
さらに $Q$ が奇数のとき、
- $P$ が奇数、かつ $e>1$,
- $P$ が偶数
のいずれかの場合、 $$2^{e+f}\mid\mid u_{km}$$ となる。
結局、つぎのことがいえる。
定理 12
$p$ が素数、$e, m$ は正の整数で $f$ は $0$ 以上の整数とする。 $p^e\mid\mid u_m, p^f\mid\mid k$ のとき $p^{e+f}$ は $u_{km}$ を割り切る。 さらに $p$ が $Q$ を割り切らないとき、$p^e=2$ で $P$ が奇数の場合を除き $$p^{e+f}\mid\mid u_{km}$$ となる。
整数 $P, Q$ に対して、数論的関数 $\psi(n)=\psi_{P, Q}(n)$ を $$\psi(2)=\left\{\begin{array}{cl}1 & \ (2\mid Q), \\ 2 & \ (2\nmid Q, 2\mid P), \\ 3 & \ (2\nmid PQ), \end{array}\right.$$ $p$ が奇素数のとき $$\psi(p)=p-\left(\frac{D}{p}\right),$$ $p$ が素数で $e$ が正の整数のときは $$\psi(p^e)=p^{e-1}\psi(p)$$ により定め、一般の正の整数 $n=p_1^{e_1} \cdots p_r^{e_r}$ については $$\psi(n)=\prod_{k=1}^r \psi(p_k^{e_k})$$ により定める。 さらに数論的関数 $\lambda(n)=\lambda_{P, Q}(n)$ を $p$ が素数で $e$ が正の整数のときは $\lambda(p^e)=\psi(p^e)$ とし 一般の正の整数 $n=p_1^{e_1} \cdots p_r^{e_r}$ については $$\lambda(n)=\LCM[\psi(p_1^{e_1}), \psi(p_2^{e_2}), \ldots, \psi(p_r^{e_r})]$$ により定める。
$\lambda(n)$ は $\psi(n)$ を割り切る。さらにEulerの定理の類似である、次の定理が成り立つ。
定理 13
$n$ が $Q$ と互いに素な素数のとき $n\mid u_{\lambda(n)}$.
定理 7 より $$\rho(n)\mid \lambda(n)\mid \psi(n)$$ となることがわかる。
Lucas数列は、 円分多項式で定義した多項式 $$\Phi_n(X, Y)=(X^n-Y^n)/\prod_{d<n, d\mid n}\Phi_d(X, Y)=Y^{\varphi(n)}\Phi_n(X/Y, 1)$$ を用いて $$u_n=\prod_{d\mid n, d>1}\Phi_d(\alpha, \beta)$$ とあらわされる。
$\Phi_d(\alpha, \beta)$ の整除性については、つぎの定理が成り立つ。
定理 14
$q_d=\Phi_d(\alpha, \beta)$ と定めると、 $p$ が $2Q$ を割り切らない素数で $q_n$ を割り切るとき $n=\rho(p) p^k$ となる。
参考文献
Edouard Lucas, Theorie des Fonctions Numeriques Simplement Periodiques I, II, III, Amer. J. Math. 1 (1878), 184--196, 197--240, 289--321, doi:10.2307/2369308 (JSTOR), doi:10.2307/2369311 (JSTOR), doi:10.2307/2369373 (JSTOR) はLucas数列についての最初の体系的な研究である。
関係式や合同式、素数判定への応用については P. Ribenboim, The New Book of Prime Number Records, 3rd edition, Springer, 1996 のSection 2, IV で詳しく解説されている。
