Lucas擬素数

$\alpha$ と $\beta$ はどちらも $t^2=Pt-Q$ を満たす。$\alpha$ は定義から、$\beta=P-\alpha$ は $\beta^2-P\beta+Q=(P-\alpha)^2-P(P-\alpha)+Q=\alpha^2-P\alpha+Q=0$ による。よって $s_k:=\alpha^k\pm\beta^k$ は $s_{k+2}=Ps_{k+1}-Qs_k$ を満たす。$k=0,1$ では $\alpha^0-\beta^0=0=(\alpha-\beta)U_0$、$\alpha-\beta=(\alpha-\beta)U_1$、$\alpha^0+\beta^0=2=V_0$、$\alpha+\beta=P=V_1$ である。$(\alpha-\beta)U_k$ と $V_k$ も同じ漸化式を満たすので、帰納法で一致する。$\square$

$p\nmid D$ なので $(\alpha-\beta)^2=D$ は $R$ で可逆であり、$\alpha-\beta$ も可逆である。$p\nmid Q$ なので $\alpha\beta=Q$ も可逆で、$\alpha,\beta$ は可逆である。lem-lpsp-binet により、$\alpha^m=\beta^m$ を示せば $U_m\equiv0\pmod p$ が従う。
$\varepsilon=-1$ の場合：$D$ は法 $p$ の平方剰余でない。$x^2-Px+Q$ が $\mathbb F_p$ に根 $c$ をもつと $(2c-P)^2=D$ となって矛盾するので（$p$ は奇数）、この 2 次式は $\mathbb F_p$ 上既約で、$R$ は $p^2$ 個の元からなる体である（有限体）。標数 $p$ の可換環では $(y+z)^p=y^p+z^p$ なので（二項係数 $\binom pj$、$0< j< p$ は $p$ の倍数）、$\phi(y):=y^p$ は $R$ の環準同型で、Fermat の小定理により $\mathbb F_p$ の元を動かさない。$\alpha^2-P\alpha+Q=0$ に $\phi$ を当てると、$\alpha^p$ も $t^2-Pt+Q$ の根である。体 $R$ でこの 2 次式の根は $\alpha,\beta$ だけである。また $y^p=y$ を満たす $y\in R$ は高々 $p$ 個で、$\mathbb F_p$ の $p$ 個の元がすでにそれを満たすので、$\alpha\notin\mathbb F_p$ から $\alpha^p\ne\alpha$ である。よって $\alpha^p=\beta$ であり、同様に $\beta^p=\phi(P-\alpha)=P-\beta=\alpha$ である。したがって
$$ \alpha^{p+1}=\alpha\beta=Q=\beta\alpha=\beta^{p+1} $$
となり、$U_{p+1}\equiv0$、$V_{p+1}=\alpha^{p+1}+\beta^{p+1}\equiv2Q\pmod p$ を得る。
$\varepsilon=1$ の場合：$D\equiv\delta^2\pmod p$（$\delta\not\equiv0$）と書け、$a:=(P+\delta)/2$、$b:=(P-\delta)/2$ は $\mathbb F_p$ の相異なる元で、$x^2-Px+Q=(x-a)(x-b)$ である。中国剰余定理により $R\cong\mathbb F_p\times\mathbb F_p$（$x\mapsto(a,b)$）であり、この対応で $\alpha\mapsto(a,b)$、$\beta=P-x\mapsto(b,a)$ である。$ab=Q\not\equiv0$ なので $a,b\ne0$ であり、Fermat の小定理により $\alpha^{p-1}\mapsto(1,1)$、$\beta^{p-1}\mapsto(1,1)$ となる。よって $\alpha^{p-1}=\beta^{p-1}=1$ であり、$U_{p-1}\equiv0$、$V_{p-1}\equiv2\pmod p$ を得る。
どちらの場合も、$V$ の値は $2Q^{(1-\varepsilon)/2}$ に一致する。$\square$

prf-lpsp-prime の記号を使い、$R$ の中で $\gamma:=\alpha\beta^{-1}$ とおく。$\alpha-\beta$ と $\beta$ は可逆なので、lem-lpsp-binet により、$U_k\equiv0\pmod p$ は $\alpha^k=\beta^k$、すなわち $\gamma^k=1$ と同値であり、$V_k\equiv0\pmod p$ は $\alpha^k=-\beta^k$、すなわち $\gamma^k=-1$ と同値である。prf-lpsp-prime で $\alpha^{p-\varepsilon}=\beta^{p-\varepsilon}$ を示したので $\gamma^{2^sd}=1$ である。
$c_r:=\gamma^{2^rd}$（$0\le r\le s$）とおくと $c_s=1$、$c_{r+1}=c_r^2$ である。$c_0=1$ なら $U_d\equiv0$ である。そうでなければ、$c_r\ne1$ となる最大の $r$（$0\le r< s$）をとると $c_r^2=1$ である。$c_r=-1$ を示せば $V_{2^rd}\equiv0$ となって証明が終わる。
$\varepsilon=-1$ のとき $R$ は体なので、$c_r^2=1$ から $c_r=\pm1$、よって $c_r=-1$ である。$\varepsilon=1$ のとき $R\cong\mathbb F_p\times\mathbb F_p$ で $\gamma\mapsto(t,t^{-1})$（$t:=a/b$）である。$N:=2^rd$ とすると $c_r\mapsto(t^N,t^{-N})$ で、$t^{2N}=1$ から体 $\mathbb F_p$ の中で $t^N=\pm1$、したがって $t^{-N}=t^N$ である。よって $c_r$ は $(1,1)$ か $(-1,-1)$ であり、$c_r\ne1$ なので $c_r=-1$ である。$\square$

Lucas数列の関係式 の定理「Lucas数列の基本恒等式」の加法公式で $m=n$ とすると $U_{2m}=U_mV_m$ である。これを $m=d,2d,\dots,2^{s-1}d$ に使って掛け合わせると
$$ U_{2^sd}=U_d\,V_d\,V_{2d}\cdots V_{2^{s-1}d} $$
を得る。右辺の因子のどれかが $n$ で割り切れれば、$U_{n-\left(\frac Dn\right)}=U_{2^sd}$ も $n$ で割り切れる。$\square$