整除性および合同

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

前ページにあげた関係式を用いて、Lucas数列の整除性および合同に関する重要な性質が導かれる。
式番号は本章の前ページまでと共通のものを使用する。

&&&thm [th2]
$p$ が素数ならば
$$v_p\equiv P\Mod{p}. \label{eq31}\tag{3.1}$$
さらに $p$ が奇素数で $k\in\Z_{\geq 0}$ ならば
$$u_{kp}\equiv \left(\frac{D}{p}\right)u_k\Mod{p}.$$
とくに $e\in\Z_{\geq 1}$ ならば
$u_{p^e}\equiv \left(\frac{D}{p}\right)^e\Mod{p}.$$ &&& &&&prf $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](/textbooks/初等整数論/合同式/平方剰余#th2)より $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}$$ となる。 &&& つぎの定理はFermatの小定理の一般化となっている、重要な定理である。 &&&thm [th3] $p$ が $P, Q, D$ のいずれも割り切らない奇素数ならば $p$ は $u{p-(D/p)}$ を割り切る。 &&& &&&prf $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}$$ となる。 &&& $a\not\equiv 0, \pm 1\Mod{p}$ となる整数 $a$ について $P=a+1, Q=a$ のとき $D=(a-1)^2$ となるので、 $(D/p)=1$ となる。 [定義と例: 例3](/textbooks/初等整数論/Lucas数列/定義と例#ex3)にあるように $u_n(P, Q)=(a^n-1)/(a-1)$ なのでこの定理は、 $$\frac{a^{p-1}-1}{a-1}\equiv 0\Mod{p}$$ となり、通常のFermatの定理と一致する。 残るのは $p=2$ の場合と、$p$ が $P, Q, D$ のいずれかを割り切る場合だが、先につぎの合同式を示す。 &&&thm [th4] $n\geq 1$ のとき $$u_n\equiv v_{n-1}\Mod{Q}$$ かつ $$v_n\equiv P^n\Mod{Q}$$ が成り立つ。 &&& &&&prf $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}$$ となる。 &&& $u_n, v_n$ が $p=2$ で割れるかどうか、つまり $u_n, v_n$ の偶奇はつぎのようにしてわかる。 &&&thm [th5] - $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$ の倍数のとき偶数で、それ以外のとき奇数。 &&& &&&prf - 漸化式から、$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, D$ のいずれかの素因数の場合、$u_n, v_n$ が $p$ の倍数となる場合はつぎのようにしてわかる。 &&&thm [th6] - $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$ も割り切る。 &&& &&&prf - $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^{p-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](#th1)より $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$ で割り切れない。 &&& # 乗法的位数の一般化 $n\mid u_k$ となる正の整数 $k$ が存在するとき、$n\mid u_k$ となる最小の正の整数 $k$ を $\rho(n)$ とおく。 [定理3](#th3)および[定理6](#th6)より $p$ が $2Q$ を割り切らないとき $\rho(p)$ が存在することがわかる。 $\rho(n)$ は[乗法的位数](/textbooks/初等整数論/合同式/乗法的位数)と類似した性質をもっている。たとえば、次の定理が成り立つ。 &&&thm [th7] $n\mid u_k$ となる正の整数 $k$ が存在し、$\gcd(n, 2Q)=1$ かつ $m\geq 0$ のとき $$n\mid u_m\Longleftrightarrow \rho(n)\mid m.$$ &&& &&&prf [定理1](#th1)より $\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^{q\rho(n)}$ だから $p$ が $n$ の素因数で $v{q\rho(n)}$ を割り切るとき $p$ は $4Q^{q\rho(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](#th3)および[定理6](#th6)より、つぎのように結論できる。 &&&thm [th8] $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))$. &&&