作为环同构的CRT与$\varphi$的积性

第一,$\psi$是良定义的:若$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$