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}}$

• 上位記事: 数論>初等整数論>整数列>Lucas数列

本稿では、2次方程式 $$x^2-Px+Q=0$$ の解 $$\alpha=\frac{P+\sqrt{D}}{2}, \beta=\frac{P-\sqrt{D}}{2}$$ に対して $$u_n=\frac{\alpha^n-\beta^n}{\alpha-\beta}, v_n=\alpha^n+\beta^n (0.1)$$ により定義される、言い換えると漸化式 $$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)$$ により定まるLucas数列の整除性及び合同式について証明する。 関係式の証明は

• Lucas数列:関係式

の記事にある。また、式番号は上位記事と共通のものを使用する。

Lucas数列の整除性および合同

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

定理 1

$k, m\in\Z$ のとき、 $u_m\mid u_{km}$. $k, m\in\Z$ で $k$ が奇数のとき、$v_m\mid v_{km}$.

Proof.

$(2.6b)$ あるいは $(2.11)$ より $u_m\mid u_{km}$ がすぐにわかる。 また $(2.11)$ より $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}.$$

Proof.

$p$ が奇素数で $0<r<p$ ならば $\binom{p}{r}=p!/(r!(p-r)!)$ は $p$ で割り切れるので、 $(2.13)$ より $$v_p\equiv\sum_{r=0}^{(p-1)/2} \binom{p}{r}Q^r v_{p-2r}\equiv P^p\equiv P\mathmod{p}.$$ また $p=2$ のとき $$v_2=\alpha^2+\beta^2=P^2-2Q\equiv P^2\equiv P\mathmod{p}$$ となるから、$p$ が素数ならば $(3.1)$ が成り立つ。

再び $p$ が奇素数のとき、 $0<r<p$ ならば $\binom{p}{r}=p!/(r!(p-r)!)$ は $p$ で割り切れるので、$(2.9)$ より $$D^{(p-1)/2}u_k^p=\sum_{r=0}^{(p-1)/2} \binom{p}{r} (-1)^r Q^{kr} u_{k(p-2r)}\equiv u_{kp}\mathmod{p}$$ となるので、平方剰余:定理1.2より $D^{(p-1)/2}\equiv (D/p)\mathmod{p}$ だから $$u_{kp}\equiv\left(\frac{D}{p}\right)u_k^p\mathmod{p}$$ となる。とくに $$u_{p^e}\equiv \left(\frac{D}{p}\right)u_{p^{e-1}}\equiv\cdots\equiv\left(\frac{D}{p}\right)^e\mathmod{p}$$ となる。

□

つぎの定理はFermatの小定理の一般化となっている、重要な定理である。

定理 3

$p$ が $P, Q, D$ のいずれも割り切らない奇素数ならば $p$ は $u_{p-(D/p)}$ を割り切る。

Proof.

$p$ が奇素数で $(D/p)=-1$ ならば $(2.12)$ より $$2^p u_{p+1}=(p+1)P^p +\binom{p+1}{3}P^{p-2}D+\cdots+\binom{p+1}{p}PD^{(p-1)/2}$$ であるが、$2\leq r\leq p-1$ のとき $p$ は $\binom{p+1}{r}$ を割り切るので、 $$2^p u_{p+1}\equiv P^p+PD^{(p-1)/2}\equiv P+P\left(\frac{D}{p}\right)\equiv 0\mathmod{p}$$ となる。$p\neq 2$ なので $$p\mid u_{p+1}=u_{p-(D/p)}$$ となる。 $p$ が奇素数で $(D/p)=1$ とする。 $$\binom{p-1}{r}=\frac{(p-1)\cdots (p-r)}{r!}\equiv (-1)^r\mathmod{p}$$ となる。また $p$ は $P^2-D=4Q$ を割り切らないので、 $$\begin{split} 2^{p-2} u_{p-1}= & (p-1)P^{p-2}+\binom{p-1}{3}P^{p-4}D+\cdots+\binom{p-1}{p-2}PD^{(p-3)/2} \\ \equiv & -(P^{p-2}+P^{p-4}D+\cdots PD^{(p-3)/2}) \\ \equiv & -P\times \frac{P^{p-1}-D^{(p-1)/2}}{P^2-D}. \end{split}$$

$(D/p)=1$ だから $$C^2\equiv D\mathmod{p}$$ となる $C\in\Z$ が存在する。$p$ は $D$ を割り切らないから $C$ も割り切らないので $$2^{p-2} u_{p-1}\equiv -P\times \frac{P^{p-1}-C^{p-1}}{P^2-C^2}\equiv 0\mathmod{p}$$ となる。

□

$a\not\equiv 0, \pm 1\mathmod{p}$ となる整数 $a$ について $P=a+1, Q=a$ のとき $D=(a-1)^2$ となるので、 $(D/p)=1$ となる。 例 にあるように $u_n(P, Q)=(a^n-1)/(a-1)$ なのでこの定理は、 $$\frac{a^{p-1}-1}{a-1}\equiv 0\mathmod{p}$$ となり、通常のFermatの定理と一致する。

残るのは $p=2$ の場合と、$p$ が $P, Q, D$ のいずれかを割り切る場合だが、先につぎの合同式を示す。

定理 4

$n\geq 1$ のとき $$u_n\equiv v_{n-1}\mathmod{Q}$$ かつ $$v_n\equiv P^n\mathmod{Q}$$ が成り立つ。

Proof.

$n\geq 1$ のとき $(2.11)$ より $$u_n=v_{n-1}+Q v_{n-3}+\cdots\equiv v_{n-1}|mathmod{Q}$$ となり、$n>0$ のとき $(2.13)$ より $$P^n\equiv v_n+nQv_{n-2}+\cdots\equiv v_n\mathmod{Q}$$ となる。

□

$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$ の倍数のとき偶数で、それ以外のとき奇数。

Proof.

• 漸化式から、$P, Q$ がともに偶数ならば $n\geq 2$ のとき $u_n=Pu_{n-1}-Qu_{n-2}$ は偶数、$v_n=Pv_{n-1}-Qv_{n-2}$ も偶数。さらに $v_0=2, v_1=P$ も偶数なので $n\geq 0$ のとき $v_n$ は偶数。
• $P$ が奇数で $Q$ が偶数のとき $$u_n\equiv Pu_{n-1}\equiv u_{n-1}\mathmod{2}$$ で $u_1=1$ は奇数だから $n\geq 1$ のとき $u_n$ は奇数。同様に $$v_n\equiv Pv_{n-1}\equiv v_{n-1}\mathmod{2}$$ で $v_1=P$ は奇数だから $n\geq 1$ のとき $v_n$ は奇数。
• $P$ が偶数で $Q$ が奇数ならば $$u_n\equiv Qu_{n-2}\equiv u_{n-2}\mathmod{2},$$ $u_0=0$ は偶数で $u_1=1$ は奇数だから $n\geq 0$ のとき $u_n$ の偶奇は $n$ の偶奇と一致する。同様に $$v_n\equiv Qv_{n-2}\equiv v_{n-2}\mathmod{2},$$ $v_0=2, v_1=P$ はともに偶数だから $n\geq 0$ のとき $v_n$ は偶数。
• $P, Q$ がともに奇数のとき $u_0=0$ は偶数で $u_1=1, u_2=P$ は奇数。$u_{3m}$ が偶数で $u_{3m+1}, u_{3m+2}$ が奇数のとき $$\begin{split}u_{3m+3}= & Pu_{3m+1}-Qu_{3m+2}\equiv u_{3m+1}+u_{3m+2}\equiv 0\mathmod{2}, u_{3m+4}\equiv & u_{3m+2}+u_{3m+3}\equiv 1\mathmod{2}, \\ u_{3m+5}\equiv & u_{3m+3}+u_{3m+4}\equiv 1\mathmod{2}\end{split}$$ より $u_{3(m+1)}$ は偶数で $u_{3(m+1)+1}, u_{3(m+1)+2}$ は奇数。よって数学的帰納法より $u_n$ は $n$ が $3$ の倍数のとき偶数で、それ以外のとき奇数。同様に、$v_0=2$ は偶数で $v_1=P, v_2=P^2-2$ は奇数なので、$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$ も割り切る。

Proof.

• $p$ が $P, Q$ をともに割り切る奇素数のとき $n\geq 2$ ならば $u_n=Pu_{n-1}-Qu_{n-2}$ は $p$ の倍数。
• $p$ が $P$ を割り切るが $Q$ を割り切らない奇素数のとき $u_1=1$ は $P$ の倍数ではなく、$u_2=P$ は $p$ の倍数。$$u_n=Pu_{n-1}-Qu_{n-2}\equiv Qu_{n-2}\mathmod{p}$$ より、$$p\mid u_n\Longleftrightarrow p\mid u_{n-2}$$ となるから、$$p\mid u_n \Longleftrightarrow 2\mid n$$ がわかる。
• $p$ が $P$ を割り切らないが $Q$ を割り切る奇素数のとき、$u_n$ が $p$ で割り切れなければ $$u_{n+1}\equiv Pu_n-Qu_{n-1}\equiv Pu_n\mathmod{p}$$ より $u_{n+1}$ も $p$ で割り切れない。$u_1=1$ は $p$ で割り切れないから、結局 $n\geq 1$ のとき $u_n$ は $p$ で割り切れない。
• $(2.12)$ より $$2^{p-1}u_p\equiv pP^{n-1}\mathmod{D}$$ だから、$p$ が $D$ を割り切る奇素数のとき、$$2^{p-1}u_p\equiv pP^{p-1}\equiv 0\mathmod{p}$$ となるので $p\mid 2^{p-1} u_p$、$p$ は奇数だから $p$ は $u_p$ を割り切るので定理 1より $p\mid n$ ならば $p$ は $u_n$ も割り切る。一方、$p$ が $n$ を割り切らないとき $(2.12)$ より $2^{n-1}u_n\equiv nP^{n-1}\mathmod{p}$ となるが $p$ は $n$ も $P$ も割り切らないので、$u_n$ も $p$ で割り切れない。

□

$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.$$

Proof.

定理 1より $\rho(n)\mid m$ かつ $m\geq 0$ ならば $u_m$ は $n$ で割り切れることはすぐにわかる。

$m\geq 0$ で $u_m$ が $n$ で割り切れるとし、 $$m=q\rho(n)+r, 0\leq r<\rho(n)$$ となる $q, r$ をとると $$u_m=\frac{u_{q\rho(n)} v_r+u_r v_{q\rho(n)}}{2}$$ より $u_r v_{q\rho(n)}$ は $n$ で割り切れる。

$(2.4)$ より $$v_{q\rho(n)}^2=Du_{q\rho(n)}^2+4Q^n$$ だから $p$ が $n$ の素因数で $v_{q\rho(n)}$ を割り切るとき $p$ は $4Q^n=v_{q\rho(n)}^2-Du_{q\rho(n)}^2$ を割り切る。しかし、これは $\gcd(n, 2Q)=1$ に矛盾する。 よって、$\gcd(v_{q\rho(n)}, n)=1$ なので $u_r$ も $n$ で割り切れるが、$0\leq r<\rho(n)$ より $r=0$ である。つまり $\rho(n)$ は $m$ を割り切る。

□

定理 3および定理 6より、つぎのことがわかる。

定理 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$.

Proof.

$(2.12)$ より $$2^{p-1} u_p=\binom{p}{1}P^{p-1}+\binom{p}{3}P^{p-3} D+\cdots +D^{(p-1)/2}$$ である。$p>3$ のとき、$p^2$ は $\binom{p}{3}D$ および $D^2$ を割り切るから $$2^{p-1} u_p\equiv pP^{p-1}\mathmod{p^2}$$ より $p\mid\mid 2^{p-1} u_p$ となるので $p\mid\mid u_p$ となる。 $p=3$ のとき $p^2\mid D$ だから $$2^{p-1} u_p=3P^2+D\equiv 3P^2\mathmod{3^2}$$ より、やはり$p\mid\mid 2^{p-1} u_p$ となるので $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}$$ となる。

Proof.

$g\geq 0$ について $u_r^{(g)}=u_{rm p^g}/u_{mp^g}$ とおくと $(2.6b)$ より $(u_r^{(g)})_r$ は $$u_r^{(g+1)}=\frac{u_{rmp^{g+1}}}{u_{mp^{g+1}}}=\frac{u_{rp}^{(g)}}{u_p^{(g)}}=u_r(P_{g+1}, Q_{g+1}), \ \ (3.2)$$ ただし $$(P_0, Q_0)=(v_m, Q^m), (P_{g+1}, Q_{g+1})=(v_p^{(g)}, Q_g^p)$$ で与えられるLucas数列で、 $(2.4)$ より判別式は $$D_0=v_m^2-4Q^m=Du_m^2, D_{g+1}=v_p^{(g) 2}-4Q_g^p=D_g u_p^{(g) 2} \ \ (3.3)$$ で与えられる。 $Q_g=Q^{m p^g}$ となることはすぐにわかる。

$p$ が $Q$ を割り切るとする。 このとき $p$ は $Du_m^2+4Q^m=v_m^2$ を割り切るから $p$ は $P_0=v_m$ も割り切る。定理 6より $p$ は $u_p^{(0)}=u_{pm}/u_m$ を割り切る。

$p$ が $u_p^{(g)}$ を割り切るとすると、 $Q_g=Q^{m p^g}$ も $p$ で割り切れるので、$p$ は $D_g u_p^{(g) 2}+4Q_g^m=v_p^{(g) 2}$ も割り切る。 したがって $p$ は $P_{g+1}=v_p^{(g)}$ も割り切るから、定理 6より $p$ は $u_p^{(g)}$ を割り切る。 帰納的に、任意の整数 $g\geq 0$ に対して、$p$ は $u_p^{(g)}=u_{m p^{g+1}}/u_{m p^g}$ を割り切る。

よって $p^f\mid k$ ならば $$p\mid u_{p^{g+1} m}/u_{p^g m}\ (g=0, 1, \ldots)$$ より $$p^{e+f}\mid u_{p^f m}\mid u_{km}$$ となる。

$p$ が $Q$ を割り切らないとする。 このとき $p$ は $Du_m^2+4Q^m=v_m^2$ を割り切らないから $p$ は $v_m$ も割り切らない。一方、$(3.3)$ より $p^2$ は $D_0=Du_m^2$ を割り切るので定理 6から $$p\mid u_r^{(0)}\Longleftrightarrow p\mid r$$ となる。さらに $(3.2)$ および補題 1から $$p\mid\mid u_p^{(0)}$$ となる。 $p$ が $u_p^{(g)}$ を割り切るとすると、$(3.3)$ より $p^2$ は $D_{g+1}=D_g u_p^{(g) 2}$ を割り切るので 定理 6から $$p\mid u_r^{(g+1)}\Longleftrightarrow p\mid r $$ となる。さらに $(3.2)$ および補題 1から $$p\mid\mid u_p^{(g+1)}$$ となる。

結局、帰納的に、任意の整数 $g\geq 0$ に対して、 $$p\mid\mid u_p^{(g)}=u_{p^{g+1} m}/u_{p^g m}\ (g=0, 1, \ldots)$$ となることがわかるから $k=p^f s$, $\gcd(s, p)=1$ とおくと $p^{e+f}\mid\mid u_{p^f m}$ となる。 やはり、帰納的に、 $$p\mid u_r^{(f)}\Longleftrightarrow p\mid r $$ となるから、$p\nmid u_s^{(f)}=u_{km}/u_{p^f m}$ より $$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$$ となる。

Proof.

$P$ が偶数で $2^h\mid\mid P$ とする。 $g\geq 1$ で $v_{2^{g-1}}$ が偶数のとき $(2.5a)$ より $$v_{2^g}=v_{2^{g-1}}^2-2Q^{2^{g-1}}\equiv 2\mathmod{4}$$ となるので、$2\mid\mid v_{2^g}$ となる。 $v_1=P$ は偶数だから、結局 $g\geq 1$ ならば $2\mid\mid v_{2^g}$ となる。よって $(2.5a)$ より $$2^{h+g-1}\mid\mid P\prod_{i=1}^{g-1} v_{2^i}=v_1 v_2 v_4 \cdots v_{2^{g-1}}=u_{2^g}$$ となる。$(2.6b)$ より $$\frac{u_{n\times 2^g}}{u_{2^g}}=u(v_{2^g}, Q^{2^g})$$ となるが、さきに述べたように $v_{2^g}$ は偶数で、$Q^{2^g}$ は明らかに奇数だから 定理 5より$u_{n\times 2^g}/u_{2^g}$ の偶奇は $n$ の偶奇と一致する。 $2^f\mid\mid k$ だから $u_k/u_{2^f}=u_{k/2^f}^{(f)}$ は奇数となるので $$2^{f+h-1}\mid\mid u_k$$ となる。

つぎに $P, Q$ がともに奇数で $k$ は $3$ の倍数とする。 $g$ を $0$ 以上の整数とする。 $$v_{3\times 2^{g+1}}=v_{3\times 2^g}^2-2Q^{3\times 2^g}$$ だから、$v_{3\times 2^g}$ が偶数ならば $2\mid\mid v_{3\times 2^{g+1}}$ となる。 $P, Q$ は奇数だから、$v_3$ は偶数なので $g\geq 1$ のとき $2\mid\mid v_{3\times 2^g}$ となる。 $(2.6b)$ より $$\frac{u_{3n\times 2^g}}{u_{3\times 2^g}}=u(v_{3\times 2^g}, Q^{3\times 2^g})$$ となるが、さきに述べたように $v_{3\times 2^g}$ は偶数で、$Q^{3\times 2^g}$ は明らかに奇数だから 定理 5より$u_{3n\times 2^g}/u_{3\times 2^g}$ の偶奇は $n$ の偶奇と一致する。 $2^f\mid\mid k$ だから $u_k$ は偶数で $u_k/u_{3\times 2^f}$ は奇数となる。

$2^h\mid P^2-Q=u_3$ のとき $$v_3=P(P^2-3Q)=P(u_3-2Q)\equiv 2\mathmod{4}$$ より、$2\mid\mid v_3$ となるから、 $$2^f\mid\mid v_3 v_6 \cdots v_{3\times 2^{f-1}}=\frac{u_{3\times 2^f}}{u_3}$$ となる。よって $2^f\mid\mid k$ ならば $$2^{f+h}\mid\mid u_k$$ となる。

$u_3=P^2-Q\equiv 2\mathmod{4}$ のとき $P^2-3Q=(P^2-Q)-2Q$ は $4$ の倍数である。よって $2^h\mid\mid P^2-3Q$ となる整数 $h\geq 2$ がとれる。 $P$ は奇数なので $2^h\mid\mid P(P^2-3Q)=v_3$ となるから、$f\geq 1$ のとき $$2^{f+h-1}\mid\mid v_3 v_6 \cdots v_{3\times 2^{f-1}}\frac{u_{3\times 2^f}}{u_3}$$ より、 $$2^{f+h}\mid\mid u_{3\times 2^f}$$ となる。よって $2^f\mid\mid k, f\geq 1$ ならば $$2^{f+h}\mid\mid u_k$$ となる。また、さきに述べたことから $u_{3n}/u_3$ の偶奇は $n$ の偶奇と一致するから $k$ が奇数ならば $$2\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}$$ となる。

Proof.

$(2.4)$ より $$v_m^2=Du_m^2+4Q^m$$ だから $u_m$ が偶数なので $v_m=u_{2m}/u_m$ も偶数である。同様にして $u_{2^{g+1} m}/u_{2^g m} (g=0, 1, \ldots)$ も偶数だから、$2^f\mid\mid k$ ならば $2^{e+f}$ は $u_{km}$ を割り切る。

$P$ が偶数で $Q$ が奇数のとき $$2^g\mid\mid m, 2^h\mid\mid P$$ となる $g, h$ をとると $2^{f+g}\mid\mid km$ なので定理 10より $$2^{g+h-1}\mid\mid u_m, 2^{f+g+h-1}\mid\mid u_{km}$$ となるから $e=g+h-1$ より $2^{e+f-1}\mid\mid u_{km}$ となる。

$P, Q$ がともに奇数で $2^h\mid P^2-Q=u_3, h\geq 2$ のとき $2^g\mid\mid m$ となる $g$ をとると $2^{f+g}\mid\mid mk$ なので定理 10より $$2^{g+h-1}\mid\mid u_m, 2^{f+g+h-1}\mid\mid u_{km}$$ となるから $2^{e+f-1}\mid\mid u_{km}$ となる。

$P, Q$ がともに奇数で $2^h\mid P^2-3Q$ のとき $2^2\mid u_m$ ならば 定理 10より $m$ は偶数である。 $2^g\mid\mid m$ となる $g$ をとると $g\geq 1$ かつ $2^{f+g}\mid\mid mk$ なので定理 10より $$2^{g+h-1}\mid\mid u_m, 2^{f+g+h-1}\mid\mid u_{km}$$ となるから $2^{e+f-1}\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})]$$ により定める。

定理 13

$n$ が $Q$ と互いに素な素数のとき $n\mid u_{\lambda(n)}$.

Proof.

まず $n=2^e$ が $2$ の累乗とする。仮定より $Q$ は奇数である。 $P$ が偶数のとき、定理 5より $u_2$ は偶数、 $P$ が奇数のとき、定理 5より $u_3$ は偶数である。 いずれの場合も $u_{\psi(2)}$ は偶数で、 $$\psi(n)=2^{e-1}\psi(2)$$ なので定理 12より $$2^e\mid u_{2^{e-1}\psi(2)}=u_{\psi(n)}$$ となる。

つぎに $p$ が奇素数で $n=p^e$ が $p$ の累乗とする。 $p\mid D$ ならば $\psi(p)=p$ で定理 5より $p\mid u_p$, $p\nmid D$ ならば $\psi(p)=p-(D/p)$ で定理 5より $p\mid u_{p-(D/p)}$ だから いずれの場合も $$p\mid u_{\psi(p)}$$ かつ $$\psi(n)=p^{e-1}\psi(p)$$ なので定理 12より $$p^e\mid u_{p^{e-1}\psi(p)}=u_{\psi(n)}$$ となる。

よって、$n$ が素数の累乗ならば $n\mid u_{\psi(n)}=u_{\lambda(n)}$ となる。 一般の正の整数 $n$ に対しては、 $n=p_1^{e_1} \cdots p_r^{e_r}$ と素因数分解すると、 各 $k=1, 2, \ldots, r$ に対して定理 1より $$p_k^{e_k}\mid u_{\lambda(p_k^{e_k})}\mid u_{\lambda(n)}$$ となるから、$n$ は $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$ となる。

Proof.

$m=\rho(p)$ とおく。$p$ が $q_n$ を割り切るから $u_n$ も割り切るので $m\mid n$ である。

$m<n$ と仮定し、$s$ を $m\mid (n/s)\mid n$ となる素数とする。 $q_n$ は $$\prod_{d\mid n, (n/s)\nmid d}q_d=\frac{u_n}{u_{n/s}}$$ を割り切るので $p$ は $u_n/u_{n/s}$ を割り切る。 定理 9 より $$p^e\mid\mid u_m, p^f\mid\mid \frac{n}{sm}$$ となる整数 $e, f$ をとると $$p^{e+f}\mid\mid u_{n/s}$$ かつ $$p^{e+f+1}\mid u_n$$ となるが、定理 9 より $$p^{f+1}\mid \frac{n}{m}$$ となるから、 $f$ のとり方より $s=p$ である。よって $n/m$ は $p$ の冪でなければならない。

□

参考文献

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) および P. Ribenboim, The New Book of Prime Number Records, 3rd edition, Springer, 1996 のSection 2, IV を参照。上位記事Lucas数列も参照。