中国式剰余定理

$N_i$ のどの2つも互に素だから 倍数と約数: 命題4 より
$N_s$ と $M_s=(N_1 N_2 \cdots N_r)/N_s=\prod_{1\leq i\leq r, i\neq s} N_i$ も互いに素である。
よって各 $s=1, 2, \ldots, r$ に対して
$$b_s M_s\equiv 1\Mod{N_s}$$
となる $b_s$ がとれる。

$$x\equiv a_1 b_1 M_1+a_2 b_2 M_2+\cdots a_r b_r M_r\Mod{N_1 N_2 \cdots N_r}$$
ならば $s=1, 2, \ldots, r$ に対して
$$x\equiv a_s b_s M_s\equiv a_s\Mod{N_s}$$
が成り立つ。よって \eqref{eq2} が成り立つ $t\Mod{N_1 N_2 \cdots N_r}$ が存在することが確かめられる。
逆に
$$x\equiv a_s\Mod{N_s} (s=1, 2, \ldots, r)$$
ならば
$$x\equiv a_s b_s M_s\equiv a_1 b_1 M_1+a_2 b_2 M_2+\cdots a_r b_r M_r\Mod{N_s} (s=1, 2, \ldots, r)$$
となるが $N_i$ のどの2つも互に素だから、 倍数と約数: 命題1 より
$\LCM[N_i, N_j]=N_i N_j$ が $1\leq i< j\leq r$ について成り立ち、 倍数と約数: 命題2 を繰り返し適用し、
$$x\equiv a_1 b_1 M_1+a_2 b_2 M_2+\cdots a_r b_r M_r\Mod{N_1 N_2 \cdots N_r}$$
が成り立つ。よって \eqref{eq2} が成り立つ $t\Mod{N_1 N_2 \cdots N_r}$ は一意的に定まる。

さらに $\gcd(a_1, N_1)=\gcd(a_2, N_2)=\cdots =\gcd(a_r, N_r)=1$ ならば
各 $i$ について $t\equiv a_i\Mod{N_i}$ かつ $\gcd(a_i, N_i)=1$ なので $\gcd(t, N_i)=1$ であるから
倍数と約数: 命題4 より $\gcd(t, N_1 N_2 \cdots N_r)=1$ となる。
一方 $d>1$ が $a_i, N_i$ をともに割り切るとき $t\equiv a_i\Mod{N_i}$ だから $d$ は $t_i$ も割り切るが、
$d$ は $N_i$ も割り切るので $d$ は $t, N_1 N_2 \cdots N_r$ をともに割り切る。
よって \eqref{eq3} も成り立つ。

$N=p^e$ かつ $p$ が素数のとき $N=p^e$ と互に素な整数全体は $p$ の倍数ではない整数全体と一致する。
よって $1, 2, \ldots, N-1$ のなかで $N$ と互に素なものは、$1, 2, \ldots, N$ のうち $p, 2p, \ldots, (N/p)p=N$ を除いたもの全体と一致するから
$$\varphi(p^e)=p^{e-1}(p-1)$$
が成り立つ。

一般の整数 $N>1$ について $N=p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k}$ と素因数分解する。
$1\leq t\leq N$ となる整数 $t$ に対して $t$ を $p_i^{e_i}$ で割った余りを $r_i(t)$ とおくと、
各 $i$ に対して $a_i\equiv t\Mod{p_i^{e_i}}$ が成り立つから、
中国式剰余定理 より
$$\gcd(t, N)=1\Longleftrightarrow \gcd(r_1(t), p_1^{e_1})=\gcd(r_2(t), p_2^{e_2})=\cdots =\gcd(r_k(t), p_k^{e_k})=1$$
となる。さらに $(a_1, a_2, \ldots, a_k)$ に対して $r_i(t)=a_i (1\leq i\leq k)$ となる $t$ が一意的に定まる。よって
$1\leq t\leq N, \gcd(t, N)=1$ となる整数 $t$ と
$0\leq a_i\leq p_i^{e_i}-1, \gcd(a_i, p_i^{e_i})=1 (1\leq i\leq k)$ となる整数の組 $(a_1, a_2, ldots, a_k)$ が
$1$対$1$に対応する。よって
$$\varphi(N)=\prod_{i=1}^k\varphi(p^e)=\prod_{i=1}^k p_i^{e_i-1}(p_i-1).$$
となる。