環同型としてのCRTと$\varphi$の乗法性

第一に、$\psi$はwell-definedである:$x\equiv x'\pmod{m_1 m_2}$ならば$m_1 m_2\mid(x-x')$なので、$m_1$も$m_2$も$x-x'$を割り切り、$x\equiv x'\pmod{m_1}$かつ$x\equiv x'\pmod{m_2}$となる。

第二に、法$m_i$での簡約が加法と乗法を保つので(最初の合同式のトピックで証明済み)、$\psi$は各座標で加法と乗法を保ち、したがって$\psi$は環準同型である。

第三に、上の定理1はまさに、任意の組$(a_1,a_2)$に対してそこへ写る$x$が存在し($\psi$は全射)、その$x$が法$m_1 m_2$で一意である($\psi$は単射)ことを述べている。よって$\psi$は全単射であり、したがって環同型である。

最後に、直積環$R_1\times R_2$において、元$(u_1,u_2)$が乗法逆元$(v_1,v_2)$を持つのは、$R_1$で$u_1 v_1=1$かつ$R_2$で$u_2 v_2=1$となるとき、すなわち両方の座標が可逆であるとき、かつそのときに限る。環同型は可逆性を保つので、$\mathbb{Z}/(m_1 m_2)\mathbb{Z}$の可逆元($\varphi(m_1 m_2)$個ある)は、$(\mathbb{Z}/m_1\mathbb{Z})\times(\mathbb{Z}/m_2\mathbb{Z})$における可逆元の組($\varphi(m_1)\,\varphi(m_2)$個ある)と一対一に対応する。両辺を数えることで$\varphi(m_1 m_2)=\varphi(m_1)\,\varphi(m_2)$が得られる。素数べきに対する$\varphi(p^r)=p^r-p^{r-1}$(互いに素でない数は$p$の$p^{r-1}$個の倍数だけ)と組み合わせれば、前のトピックで使った$\varphi(n)$の一般の積公式が直ちに導かれる。$\blacksquare$