中国剩余定理(存在性与唯一性)

我们先证明两个模的情形($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$