合成数を法とする合同式

解 $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} $$
が得られる。$a_0x\equiv b_0\pmod{m_0}$ の両辺と法に $d$ を掛けると $ax\equiv b\pmod m$ となるので、これは元の合同式の解である。法 $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$ の倍数であり、これらですべてである。$\blacksquare$

$c=gc_0$、$m=gm_0$ と書くと $\gcd(c_0,m_0)=1$ である。$ac\equiv bc\pmod m$ は $gm_0\mid gc_0(a-b)$、すなわち $m_0\mid c_0(a-b)$ と同値である。$\gcd(c_0,m_0)=1$ だから、Euclid の補題により $m_0\mid c_0(a-b)$ は $m_0\mid a-b$ と同値である。これは $a\equiv b\pmod{m/g}$ にほかならない。
後半：$g=1$ なら $m/g=m$ である。$g>1$ なら $a=0$、$b=m/g$ とおくと $ac=0$、$bc=(c/g)m\equiv0\pmod m$ で $ac\equiv bc\pmod m$ だが、$0< m/g< m$ なので $a\not\equiv b\pmod m$ である。$\blacksquare$

中国剰余定理による環同型
$$ \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$ であることと同値である。環同型の全単射性から解集合の全単射と個数の積公式が従う。$\blacksquare$

$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$ の持ち上げはすべてこの形なので一意性も従う。$\blacksquare$

まず $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)$ を得る。$\blacksquare$

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

奇素数冪：$x^2\equiv1\pmod{p^e}$ は $p^e\mid(x-1)(x+1)$ と同値である。$p$ が $x-1$ と $x+1$ の両方を割れば、差 $2$ も割るので $p$ が奇素数であることに反する。したがって $p$ はどちらか一方だけを割り、$p^e$ 全体がその一方を割る。すなわち $x\equiv1$ または $x\equiv-1\pmod{p^e}$ である。$p$ が奇数なので $1\not\equiv-1\pmod{p^e}$ であり、解はちょうど 2 個である。
$2$ の冪：$e=1$ では単数は $1$ だけ、$e=2$ では単数 $1,3$ がともに $x^2\equiv1\pmod4$ を満たす。$e\geq3$ とし、$x^2\equiv1\pmod{2^e}$ とする。$x$ は奇数なので $x-1$ と $x+1$ はともに偶数で、差が $2$ だから一方は $4$ で割れない。その一方の $2$ の指数はちょうど $1$ なので、$2^e\mid(x-1)(x+1)$ から他方が $2^{e-1}$ で割れる。よって $x\equiv\pm1\pmod{2^{e-1}}$ であり、法 $2^e$ では上の 4 つのどれかである。逆に、$(\pm1+2^{e-1})^2=1\pm2^e+2^{2e-2}$ で $2e-2\geq e$ なので、4 つとも解である。$e\geq3$ では $2^{e-1}\geq4$ だから $1,-1,1+2^{e-1},-1+2^{e-1}$ は法 $2^e$ で相異なる。
最後の主張は、thm-congruences-composite-crt により解の個数が素数冪ごとの個数の積になることから従う（$e_0=0$ の因子は $1$）。$\blacksquare$

$m\geq3$ なら $\varphi(m)$ は偶数である（$m$ が奇素数 $p$ で割れれば $p-1\mid\varphi(m)$、そうでなければ $m=2^e$ で $e\geq2$ なので $\varphi(m)=2^{e-1}$）。位数 $n$ の巡回群 $\langle g\rangle$ で $x^2=1$ となる元 $x=g^k$（$0\leq k< n$）は $n\mid2k$ を満たすものなので、$n$ が偶数なら $k=0,\,n/2$ のちょうど 2 個である。したがって原始根があれば、$(\mathbb Z/m\mathbb Z)^\times$ は位数 $\varphi(m)$ の巡回群であり、$x^2\equiv1\pmod m$ の解はちょうど 2 個になる。
一方、thm-congruences-composite-square-roots-of-one の個数 $2^r c(e_0)$ が $2$ 以下になるのは、$r=0$ かつ $e_0\leq2$（$m=1,2,4$）か、$r=1$ かつ $e_0\leq1$（$m=p^e,2p^e$）のときに限る。仮定の $m$ ではこの個数が $4$ 以上なので、原始根は存在しない。$\blacksquare$