合成数を法とする合同式

解 $x$ があれば $d$ は $a$ と $m$ を割るので $b=ax-mq$ も割る。逆に $d\mid b$ とし、$a=da_0$、$b=db_0$、$m=dm_0$ と書く。$\gcd(a_0,m_0)=1$ だから、Bézoutの等式より $a_0$ は法 $m_0$ で逆元をもち、
$$ x\equiv a_0^{-1}b_0\pmod {m_0} $$
が得られる。法 $m$ では $x,x+m_0,\ldots,x+(d-1)m_0$ が相異なる解であり、任意の二解 $x,x'$ について $a_0(x-x')\equiv0\pmod{m_0}$ で $\gcd(a_0,m_0)=1$ だから差は $m_0$ の倍数であり、これらですべてである。

中国剰余定理による環同型
$$ \mathbb Z/m\mathbb Z\cong\prod_{i=1}^r\mathbb Z/p_i^{e_i}\mathbb Z $$
は加法と乗法を保つので、多項式評価も保つ。したがって法 $m$ で $f(x)=0$ であることは、すべての成分で $f(x_i)=0$ であることと同値である。環同型の全単射性から解集合の全単射と個数の積公式が従う。

$f(x_t)=p^t u_t$ と書く。$y\in\{0,1,\ldots,p-1\}$ に対し、整数係数多項式のTaylor展開から
$$ f(x_t+yp^t)\equiv f(x_t)+yp^t f'(x_t) \equiv p^t\bigl(u_t+yf'(x_t)\bigr)\pmod {p^{t+1}} $$
を得る。$f'(x_t)$ は法 $p$ で可逆なので、
$$ u_t+yf'(x_t)\equiv0\pmod p $$
を満たす $y\bmod p$ は一意に存在する。その $y$ に対して $x_{t+1}=x_t+yp^t$ とすればよい。$x_t$ の法 $p^t$ の持ち上げはすべてこの形なので一意性も従う。

まず $p\nmid m$ のとき、
$$ \frac{a^m-b^m}{a-b}=a^{m-1}+a^{m-2}b+\cdots+b^{m-1}\equiv mb^{m-1}\not\equiv0\pmod p $$
なので $v_p(a^m-b^m)=v_p(a-b)$ である。
次に $c,d$ を $c\neq d$、$p\mid c-d$ かつ $p\nmid d$ を満たす整数とし、$t=v_p(c-d)\geq1$ とおく。二項展開により
$$ c^p-d^p=\sum_{k=1}^{p}\binom pk d^{p-k}(c-d)^k =p d^{p-1}(c-d)+\sum_{k=2}^{p-1}\binom pk d^{p-k}(c-d)^k+(c-d)^p. $$
$p\nmid d$ だから第1項 $pd^{p-1}(c-d)$ の付値はちょうど $t+1$ である。$2\leq k\leq p-1$ の項は、二項係数 $\binom pk$ が $p$ で割れるので付値が $1+kt\geq 1+2t>t+1$ である。最終項 $(c-d)^p$ の付値は $pt$ であり、$p$ が奇素数なので $pt\geq3t>t+1$ である。付値が最小の項が第1項だけなので
$$ v_p(c^p-d^p)=v_p(c-d)+1 $$
となる。$n=p^s m$、$p\nmid m$ と書く。$0\leq i\leq s$ に対して $c=a^{p^i}$、$d=b^{p^i}$ は、$p\nmid ab$ より $p\nmid d$ を満たし、$p\mid a-b$ から $c-d=(a-b)(a^{p^i-1}+\cdots+b^{p^i-1})$ より $p\mid c-d$ を満たす。また奇数 $p^i$ 乗は整数上で単射なので $a\neq b$ から $c\neq d$ である。よってこの等式を $s$ 回適用して $v_p(a^{p^s}-b^{p^s})=v_p(a-b)+s$ を得、最初の結果を $a^{p^s},b^{p^s}$ と $m$ に適用して $v_p(a^n-b^n)=v_p(a-b)+s=v_p(a-b)+v_p(n)$ を得る。

中国剰余定理の環同型は、元が可逆であることと逆元を成分ごとに取る操作を保つ。よって両辺の単数群を制限して群同型を得る。直積群の元 $(g_i)$ の位数は各 $g_i$ の位数の最小公倍数であるから後半も従う。