中国剩余定理

由于各模数没有公共素因子,模$m_1$余$a_1$与模$m_2$余$a_2$是完全独立的约束——就像分别指定一个点的$x$坐标与$y$坐标一样。贝祖等式为我们提供了在某一个模下为$1$、在其余所有模下为$0$的"基向量",使我们能把解直接写成线性组合。

我们先证明两个模的情形($k=2$),再通过归纳法推广。由$\gcd(m_1,m_2)=1$,贝祖等式给出整数$u,v$满足$m_1 u + m_2 v = 1$。令$x_0 = a_1 m_2 v + a_2 m_1 u$。

在模$m_1$下检验:由$m_1 u + m_2 v = 1$得$m_2 v = 1 - m_1 u \equiv 1 \pmod{m_1}$,而$m_1 u \equiv 0 \pmod{m_1}$,故$x_0 \equiv a_1\cdot 1 + a_2\cdot 0 = a_1 \pmod{m_1}$。

对称地,在模$m_2$下:$m_1 u = 1-m_2 v \equiv 1 \pmod{m_2}$且$m_2 v \equiv 0 \pmod{m_2}$,故$x_0 \equiv a_1\cdot 0 + a_2\cdot 1 = a_2 \pmod{m_2}$。这证明了$k=2$时的存在性。

当$k=2$时的唯一性:若$x$与$x'$都是方程组的解,则$x-x'\equiv0\pmod{m_1}$且$x-x'\equiv0\pmod{m_2}$,即$m_1$与$m_2$都整除$d=x-x'$。把贝祖等式$m_1 u+m_2 v=1$两边乘以$d$:得$d = d m_1 u + d m_2 v$。因$m_2\mid d$,第一项$d m_1 u$是$m_1 m_2$的倍数;因$m_1\mid d$,第二项$d m_2 v$也是$m_1 m_2$的倍数。因此$m_1 m_2 \mid d$,即$x\equiv x'\pmod{m_1 m_2}$。

对一般的$k>2$,用归纳法:前两个同余式(由$k=2$情形)等价于模$m_1 m_2$的一个同余式;由于$m_3$与$m_1$、$m_2$都互素,它与乘积$m_1 m_2$也互素,因此可以继续合并,直至$k$。同时注意显式和式$x \equiv \sum_{i=1}^{k} a_i M_i y_i \pmod{M}$按完全相同的推理对任意$k$直接成立:$M_i = M/m_i$与$m_i$互素故逆元$y_i$存在,而每个$j\neq i$的项都在$M_j$中含有因子$m_i$。$\blacksquare$

这就是CRT的结构意义:模$m_1 m_2$的算术从字面上看就是两个相互独立的模算术副本(一个模$m_1$,一个模$m_2$)并排运行。这既是欧拉函数$\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$