整除性および合同

$(2.6b)$ あるいは $(2.11)$ より $u_m\mid u_{km}$ がすぐにわかる。
また $(2.11)$ より $k$ が奇数ならば $v_m\mid v_{km}$ となる。

$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\Mod{p}.$$
また $p=2$ のとき
$$v_2=\alpha^2+\beta^2=P^2-2Q\equiv P^2\equiv P\Mod{p}$$
となるから、$p$ が素数ならば \eqref{eq31} が成り立つ。

再び $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}\Mod{p}$$
となるので、 平方剰余:定理2 より $D^{(p-1)/2}\equiv (D/p)\Mod{p}$ だから
$$u_{kp}\equiv\left(\frac{D}{p}\right)u_k^p\Mod{p}$$
となる。とくに
$$u_{p^e}\equiv \left(\frac{D}{p}\right)u_{p^{e-1}}\equiv\cdots\equiv\left(\frac{D}{p}\right)^e\Mod{p}$$
となる。

$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\Mod{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\Mod{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\Mod{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\Mod{p}$$
となる。

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

• 漸化式から、$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}\Mod{2}$$ で $u_1=1$ は奇数だから $n\geq 1$ のとき $u_n$ は奇数。同様に $$v_n\equiv Pv_{n-1}\equiv v_{n-1}\Mod{2}$$ で $v_1=P$ は奇数だから $n\geq 1$ のとき $v_n$ は奇数。
• $P$ が偶数で $Q$ が奇数ならば $$u_n\equiv Qu_{n-2}\equiv u_{n-2}\Mod{2},$$ $u_0=0$ は偶数で $u_1=1$ は奇数だから $n\geq 0$ のとき $u_n$ の偶奇は $n$ の偶奇と一致する。同様に $$v_n\equiv Qv_{n-2}\equiv v_{n-2}\Mod{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\Mod{2}, u_{3m+4}\equiv & u_{3m+2}+u_{3m+3}\equiv 1\Mod{2}, \\ u_{3m+5}\equiv & u_{3m+3}+u_{3m+4}\equiv 1\Mod{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$ をともに割り切る奇素数のとき $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}\Mod{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\Mod{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}\Mod{D}$$ だから、$p$ が $D$ を割り切る奇素数のとき、$$2^{p-1}u_p\equiv pP^{p-1}\equiv 0\Mod{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}\Mod{p}$ となるが $p$ は $n$ も $P$ も割り切らないので、$u_n$ も $p$ で割り切れない。

定理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$ を割り切る。