初等数论：中国剩余定理

陈一男学习网站[ ChenYinan.com ] - 中国数学学会 - 中国院士 - GeoGebra - 数学基础

1. 中国剩余定理内容

设\(m_1,m_2,\cdots,m_n\)是两两互质的正整数，\(a_1,a_2,\cdots,a_n\)是任意整数，则同余方程组

\(\begin{cases}x\equiv a_1\pmod{m_1}\\x\equiv a_2\pmod{m_2}\\\cdots\\x\equiv a_n\pmod{m_n}\end{cases}\)在模\(M = m_1m_2\cdots m_n\)下有唯一解。

2. 中国剩余定理解法示例

以一个简单的例子来说明，对于同余方程组\(\begin{cases}x\equiv2\pmod{3}\\x\equiv3\pmod{5}\\x\equiv2\pmod{7}\end{cases}\)。

首先，计算\(M = 3\times5\times7 = 105\)。

然后，分别计算\(M_1=\frac{M}{m_1}=\frac{105}{3}=35\)，\(M_2=\frac{M}{m_2}=\frac{105}{5}=21\)，\(M_3=\frac{M}{m_3}=\frac{105}{7}=15\)。

接着，求\(M_1\)关于\(m_1\)的逆元\(y_1\)，即找到满足\(35y_1\equiv1\pmod{3}\)的\(y_1\)，通过计算可知\(y_1 = 2\)；求\(M_2\)关于\(m_2\)的逆元\(y_2\)，满足\(21y_2\equiv1\pmod{5}\)，可得\(y_2 = 1\)；求\(M_3\)关于\(m_3\)的逆元\(y_3\)，满足\(15y_3\equiv1\pmod{7}\)，可得\(y_3 = 1\)。

最后，根据公式\(x=(a_1M_1y_1 + a_2M_2y_2+\cdots+a_nM_ny_n)\bmod M\)，可得\(x=(2\times35\times2 + 3\times21\times1+2\times15\times1)\bmod105 = 23\)，所以该同余方程组的解为\(x\equiv23\pmod{105}\)。

3. 中国剩余定理证明思路

令\(M = m_1m_2\cdots m_n\)，对于每个\(i = 1,2,\cdots,n\)，定义\(M_i=\frac{M}{m_i}\)。由于\(m_i\)两两互质，所以\(M_i\)与\(m_i\)互质，根据裴蜀定理，存在整数\(y_i\)使得\(M_iy_i\equiv1\pmod{m_i}\)。

构造一个解\(x=a_1M_1y_1 + a_2M_2y_2+\cdots+a_nM_ny_n\)。对于任意的\(j = 1,2,\cdots,n\)，当\(i\neq j\)时，\(m_j\mid M_i\)，所以\(a_iM_iy_i\equiv0\pmod{m_j}\)。而对于\(i = j\)，\(a_iM_iy_i\equiv a_i\pmod{m_i}\)。

所以\(x\)满足同余方程组中的每一个方程，即\(x\)是同余方程组的一个解。再证明解的唯一性，假设\(x_1\)和\(x_2\)是同余方程组的两个解，那么对于每个\(i\)，\(x_1 - x_2\equiv0\pmod{m_i}\)，因为\(m_i\)两两互质，所以\(x_1 - x_2\equiv0\pmod{M}\)，即\(x_1\equiv x_2\pmod{M}\)，所以在模\(M\)下解是唯一的。