合成数を法とする合同式

$$f(x)=a_d x^d+a_{d-1} x^{d-1}+\cdots+a_0$$
とおく。
$$f(x_1)\equiv 0\Mod{p}, f^\prime(x_1)\not\equiv 0\Mod{p}$$
となる $x_1\Mod{p}$ をとり、正の整数 $t$ について
$$f(x_t)\equiv 0\Mod{p^t}, x_t\equiv x_1\Mod{p}$$
となる $x_t\Mod{p}$ が存在するとする。

$$f(x_t+p^t)=\sum_{k=0}^d a_k (x_t+p^t)^k=\sum_{k=0}^d a_k\left(x_t^k+kx_t^{k-1}p^t+\binom{k}{2}x_t^{k-2}p^{2t}+\cdots\right)$$
と展開することができ、$t\geq 1$ なので $f(x_t)=u_t p^t$ とおくと
$$f(x_t+p^t)\equiv a_0+\sum_{k=1}^d a_k(x_t^k+kx_t^{k-1}p^t)=f(x_t)+p^t f^\prime(x_t)=p^t(u_t+f^\prime(x_t)) \Mod{p^{t+1}}$$
となる。
$f^\prime(x_1)\not\equiv 0\Mod{p}$ であるから
$$u_t+y_t f^\prime(x_t)\equiv 0\Mod{p}$$
となる $y_t \Mod{p}$ が一意に定まる。つまり
$$f(x_t+y_t p^t)\equiv p^t(u_t+yf^\prime(x_t))\equiv 0\Mod{p^{t+1}}$$
となる $y_t \Mod{p}$ が一意に定まる。

乗法的位数:定理3 より
$$x^n\equiv 1\Mod{p}\Longleftrightarrow x^{\gcd(n, p-1)}\equiv 1\Mod{p}$$
となる。
$a$ を $p$ を法とする原始根とし、$x\equiv a^g\Mod{p}$ とおくと
$$a^{g\gcd(n, p-1)}\equiv 1\Mod{p}\Longleftrightarrow (p-1)\mid g\gcd(n, p-1)\Longleftrightarrow (p-1)/\gcd(n, p-1)\mid g$$
となるから
$$x^{\gcd(n, p-1)}\equiv 1\Mod{p}\Longleftrightarrow x\equiv a^{k(p-1)/\gcd(n, p-1)}\Mod{p} (k=0, 1, \ldots, \gcd(n, p-1)-1)$$
となる。よって
$$x^n\equiv 1\Mod{p}$$
は $\Z/p\Z$ にちょうど $\gcd(n, p-1)$ 個の解をもつ。
一方 $n$ は $p$ で割り切れないから $x^n\equiv 1\Mod{p}$ のとき
$$(x^n-1)^\prime=nx^{n-1}\not\equiv 0\Mod{p}$$
となる。よって 定理2 より
$$x^n\equiv 1\Mod{p^e}$$
も $\Z/(p^e)\Z$ にちょうど $\gcd(n, p-1)$ 個の解をもつ。

つぎに $f(x)$ が
$$x^n-1\equiv f(x)g(x)\Mod{p}$$
となる多項式 $g(x)$ が存在し、$p$ を法とする次数が $d$ 以下の多項式とする。 多項式の合同の基礎:定理3 より
$$f(x)\equiv 0\Mod{p}$$
は $\Z/p\Z$ に多くとも $d$ 個の解しかもたない。

$$f(a)\equiv f^\prime(a)\equiv 0\Mod{p}$$
となる $a\Mod{p}$ が存在するとすると、
多項式環の記事の定理15 より
$$f(x)\equiv g(x)(x-a)^2\Mod{p}$$
となる $g(x)$ が存在するので
$$x^n-1\equiv h(x)(x-a)^2\Mod{p}$$
となる $h(x)$ が存在する。よって 多項式環の記事の定理14 より
$$x^n-1\equiv (x^n-1)^\prime\equiv 0\Mod{p}$$
は $x\equiv a\Mod{p}$ を解にもつ。これは矛盾である。

よって
$$f(a)\equiv 0\Mod{p}$$
ならば $f^\prime(a)\not\equiv 0\Mod{p}$ となるので
定理2 より
$$f(x)\equiv 0\Mod{p^e}$$
の解の個数は $f(x)\equiv 0\Mod{p}$ の解の個数と一致する。

中国式剰余定理から $(x_1\Mod{p_1^{e_1}}, \ldots, x_k\Mod{p_k^{e_k}})$ の組と
$$x\equiv x_i\Mod{p_i^{e_i}} (i=1, \ldots, k)$$
となる $x\Mod{N}$ は$1$対$1$に対応する。
$$f(x)\equiv 0\Mod{N}\Longleftrightarrow f(x)\equiv 0\Mod{p_i^{e_i}} (i=1, \ldots, k)\Longleftrightarrow f(x_i)\equiv 0\Mod{p_i^{e_i}} (i=1, \ldots, k)$$
となるから、
\eqref{eq10} の解 $x\Mod{N}$ は
$$f(x_i)\equiv 0\Mod{p_i^{e_i}} (i=1, \ldots, k)$$
となる $(x_1\Mod{p_1^{e_1}}, \ldots, x_k\Mod{p_k^{e_k}})$ の組と対応するので
\eqref{eq10} の解の個数は $\prod_{i=1}^k m_i$ に等しい。

$f(x)$ が各 $p_i$ を法とする次数が $d_i$ 以下の多項式ならば
$$f(x)\equiv 0\Mod{p_i}$$
の解の個数は $d_i$ 以下である。
$$f(a)\equiv f^\prime(a)\equiv 0\Mod{p_i}$$
となる $a\Mod{p_i}$ が存在しないので、 定理2 より
$$f(x)\equiv 0\Mod{p_i^{e_i}}$$
の解の個数も $d_i$ 以下である。つまり $m_i\leq d_i$ であるから \eqref{eq10} の解の個数は $\prod_{i=1}^k d_i$ 以下である。

$bc\equiv a\Mod{p}$ となる $c$ をとると $(bc)^n\equiv a^n\Mod{p}$ だから
$$a^n\equiv b^n\Mod{p}\Longleftrightarrow c^n\equiv 1\Mod{p}$$
となる。よって $g$ は $c^n\equiv 1\Mod{p}$ となる最小の正の整数でもあるから
$$a^n\equiv b^n\Mod{p}\Longleftrightarrow g\mid n\Mod{p}$$
となる。
$$p^f\mid\mid (a^g-b^g)$$

次に $e, k$ が
$$p^e\mid\mid k$$
となる正の整数とする。

$$bc\equiv a\Mod{p^{e+f+1}}$$
となる $c$ をとる。
$$(bc)^g\equiv a^g\equiv b^g\Mod{p}$$
から
$c^g\equiv 1\Mod{p}$
となる。$\ell=0, 1, \ldots, e-1$ に対し、
$$c^{p^\ell g}\equiv 1\Mod{p}$$
が明らかに成り立つ。そこで
$$c^{p^\ell g}=Ap+1$$
とおくと、$p$ は奇数なので
$$\begin{split} \frac{c^{p^{\ell +1}g}-1}{c^{p^\ell g}-1}= & \sum_{i=0}^{p-1} c^{i p^\ell g}=\sum_{i=0}^{p-1} (Ap+1)^i \\ = & p+\frac{p(p+1)}{2}Ap+(Ap^2)\sum_{i=2}^{p-1}\binom{i}{2}+\cdots \\ = & p+\frac{p+1}{2}Ap^2+(Ap^2)\sum_{i=2}^{p-1}\binom{i}{2}+\cdots \\ \end{split}$$
より、
$$\frac{c^{p^{\ell +1}g}-1}{c^{p^\ell g}-1}\equiv p\Mod{p^2}$$
となるから
$$p\mid\mid \frac{c^{p^{\ell +1}g}-1}{c^{p^\ell g}-1}$$
が成り立つ。よって
$$p^e\mid\mid \frac{c^{p^e g}-1}{c^g-1}$$
となるから
$$p^{f+e}\mid\mid (c^{p^e g}-1)$$
となる。
$k=p^e s$ とおくと $p\not\mid s$ だから
$$c^{p^e g(s-1)}+\cdots+c^{p^e g}+1\equiv s\not\equiv 0\Mod{p}$$
なので
$$p^{f+e}\mid\mid (c^{gk}-1)=(c^{p^e g}-1)(c^{p^e g(s-1)}+\cdots+c^{p^e g}+1)$$
となる。よって
$$p^{f+e}\mid\mid ((bc)^{gk}-b^{gk})$$
となるが、$bc\equiv a\Mod{p^{e+f+1}}$ より
$$a^{gk}\equiv (bc)^{gk}\Mod{p^{e+f+1}}$$
だから
$$p^{f+e}\mid\mid (a^{gk}-b^{gk})$$
である。

まず $a\equiv 3, 5\Mod{8}$ とする。
$$2\mid\mid (a-1), 2^3\mid\mid (a-1)(a+1)=(a^2-1)$$
である。また $t\geq 0$ に対して
$$a^{2^t}+1\equiv 2\Mod{4}$$
であるから $v\geq 2$ のとき
$$a^{2^v}-1=(a-1)(a+1)\prod_{i=1}^{v-1}(a^{2^i}+1)$$
より
$$2^{v+2}\mid\mid (a^{2^v}-1)$$
である。

次に $a\equiv 1, 7\Mod{8}$ とする。
$a\equiv 1\Mod{8}$ のとき $2^m\mid\mid (a-1)$,
$a\equiv 7\Mod{8}$ のとき $2\mid\mid (a-1)$ となる。また、いずれの場合も
$$2^{m+1}\mid (a-1)(a+1)=a^2-1$$
となる。上と同様に $v\geq 2$ のとき
$$a^{2^v}-1=(a-1)(a+1)\prod_{i=1}^{v-1}(a^{2^i}+1)$$
より
$$2^{v+m}\mid\mid (a^{2^v}-1)$$
である。

最後に
$$\frac{a^d-1}{a^{2^v}-1}=1+a^{2^v}+\cdots+a^{(u-1)2^v}\equiv u\equiv 1\Mod{2}$$
より $2$ が $a^d-1$ を割り切る回数と $a^{2^v}-1$ を割り切る回数は一致するので、定理がいえる。