中国剩余定理的证明

· · 个人记录

定理：若 m_1,m_2,...,m_n 为 n 个两两互质的整数，则同余方程组

\begin{cases} x\equiv r_1(\mod m_1) \\ x \equiv r_2 (\mod m_2)\\ \quad\cdots \\ x \equiv r_n (\mod m_n)\end{cases}

有通解为 x \equiv r_1 t_1 M_1 + ... + r_k t_k M_k(mod\; M)

其中 M=m_1 m_2\, ... \,m_k ,\, M_i = \frac{M}{m_i}, \,t_i \equiv (M_i) ^{-1} (\,mod \; m_i),

即 t_i 为 M_i \times t_i \equiv 1(mod\; m_i) .

证明： 将 x \equiv r_1 t_1 M_1 + ... + r_k t_k M_k(mod\; M) 分别代入每个方程，易得这是孙子方程的解，考虑如何证明：方程组的所有解模 M 的余数相等。

对于方程 1 : \;x\equiv r_1(\mod m_1) , 有

x_1\equiv r_1(\mod m_1)\,,\; x_2 \equiv r_1(\mod m_1)

两式相减得，x_1 - x_2 \equiv 0\,(\mod m_1) , 即 \;m_1 \,| \,(x_1 - x_2) .

同理， 有 \;m_2 \,| \,(x_1 - x_2) .

由整除的性质 , 有 \;m_1 m_2 \,| \,(x_1 - x_2) .

同理还有， \;m_1 m_2 m_3 ... \,| \,(x_1 - x_2) \; ......

最终可得，M | (x_1 - x_2) , 即 x_1 \equiv x_2 (\mod M) .

所以，孙子方程解为

x \equiv r_1 t_1 M_1 + ... + r_k t_k M_k(mod\; M)