中国剩余定理

1. 定理表述

设 $m_1,m_2,\dots ,m_k$ 是 两两互素 的正整数，即 $\gcd (m_i,m_j)=1$ ($i\ne j$)。 则同余方程组：

$$\{\begin{array}{l}x\equiv b_1(\mathrm{mod}{m}_1)\\ x\equiv b_2(\mathrm{mod}{m}_2)\\ ⋮\\ x\equiv b_k(\mathrm{mod}{m}_k)\end{array}$$

在模 $m=m_1{m}_2\dots m_k$ 意义下有 唯一解。

特殊情况：

• 若 mi 不互素：将 mi 分解为互素的素数幂次，如 12 = 4*3
• 若 x 前有系数，需要先用乘法逆元将系数去掉
• 最后的 mi 必须是互素的，需要删去条件较弱的等式JHJK 2. 构造性通解公式 方程组的解为： $x\equiv {\sum }_{i=1}^k{M}_i{M}_i^{-1}{b}_i(\mathrm{mod}m)$ 其中： * $m={\prod }_{j=1}^k{m}_j$ * $M_i=\frac{m}{m_i}$ （即除去 $m_i$ 外所有模数的乘积） * $M_i^{-1}$ 是 $M_i$ 模 $m_i$ 的 逆元，满足 $M_i{M}_i^{-1}\equiv 1(\mathrm{mod}{m}_i)$。

将同余式转换为同余式组求解：

• 根据同余的基本性质，如果 $m=m_1{m}_2\dots m_k$ 且 $\gcd (m_i,m_j)=1$，则同余式 $x\equiv a(\mathrm{mod}m)$ 等价于以下同余式组：

$\{\begin{array}{l}x\equiv a(\mathrm{mod}{p}_1^{e_1})\\ x\equiv a(\mathrm{mod}{p}_2^{e_2})\\ \dots \\ x\equiv a(\mathrm{mod}{p}_k^{e_k})\end{array}$

3. 标准求解步骤 (Algorithm)

1. 计算总模数：$m=m_1\times m_2\times \cdots \times m_k$。
2. 计算分量参数：对于每一个方程 $i$：
   • 计算 $M_i=m/m_i$。
   • 利用 扩展欧几里得算法 计算 $y_i$ 使得 $M_i{y}_i\equiv 1(\mathrm{mod}{m}_i)$，这里 $y_i$ 即为公式中的 $M_i^{-1}$。
3. 加权求和：计算 $X=\sum (M_i\cdot y_i\cdot b_i)$。
4. 取模规范化：$x=X\mathrm{mod}m$。

其他解法-代入合并：

依次把同余式翻译成**等式，然后像解普通方程组（比如 $y=2x+1$ 代入 $z=y+3$）一样去解它。

第一步：翻译（同余 $\to$ 等式）**

当我们说 $x\equiv 2(\mathrm{mod}3)$ 时，数学上的意思是：

“$x$ 除以 3 余 2”。

把它翻译成等式就是：$x$ 等于 3 的某个倍数加上 2。

写出来就是：

$x=3k+2$

(这里 $k$ 是一个未知的整数)

第二步：代入（核心操作）

现在我们有了 $x$ 的具体表达式（$3k+2$），我们把它代入到第二个条件里去看看。

假设第二个条件是 $x\equiv 3(\mathrm{mod}5)$。

把 $x$ 换掉：

$(3k+2)\equiv 3(\mathrm{mod}5)$

第三步：求解未知数 $k$

现在任务变了：我们要找到 $k$ 是多少。

1. 移项（把 2 减过去）：

   $3k\equiv 1(\mathrm{mod}5)$

2. 解这个关于 $k$ 的方程（求逆元）：

   $3$ 模 $5$ 的逆元是 $2$（因为 $2\times 3=6\equiv 1$）。

   所以：

   $k\equiv 1\times 2=2(\mathrm{mod}5)$

   翻译回等式：$k=5t+2$

第四步：回带（合并完成）

把算出来的 $k$（$5t+2$）带回第一步 $x$ 的表达式里：

$x=3\times (5t+2)+2$

$x=15t+6+2$

$x=15t+8$

4. 经典例题

题目：解同余方程组

$$\{\begin{array}{l}x\equiv 1(\mathrm{mod}5)\\ x\equiv 5(\mathrm{mod}6)\\ x\equiv 4(\mathrm{mod}7)\\ x\equiv 10(\mathrm{mod}11)\end{array}$$

解：

1. 总模数：$m=5\times 6\times 7\times 11=2310$。
2. 分量计算：
   • $i=1$: $m_1=5,b_1=1$。$M_1=2310/5=462$。求 $462(\mathrm{mod}5)$ 的逆元。 $462\equiv 2(\mathrm{mod}5)$，即求 $2y\equiv 1(\mathrm{mod}5)⟹y_1=3$。
   • $i=2$: $m_2=6,b_2=5$。$M_2=2310/6=385$。 $385\equiv 1(\mathrm{mod}6)$，即求 $1y\equiv 1(\mathrm{mod}6)⟹y_2=1$。
   • $i=3$: $m_3=7,b_3=4$。$M_3=2310/7=330$。 $330\equiv 1(\mathrm{mod}7)⟹y_3=1$。
   • $i=4$: $m_4=11,b_4=10$。$M_4=2310/11=210$。 $210\equiv 1(\mathrm{mod}11)⟹y_4=1$。
3. 求和： $$\begin{array}{rl}x& \equiv 462\times 3\times 1+385\times 1\times 5+330\times 1\times 4+210\times 1\times 10\\ x& \equiv 1386+1925+1320+2100\\ x& \equiv 6731(\mathrm{mod}2310)\end{array}$$
4. 结果： $x\equiv 6731\mathrm{mod}2310=2111$。

5. 理论应用

当 $m_1,\dots ,m_k$ 两两互素时，大模数同余式 $a\equiv b(\mathrm{mod}{m}_1\dots m_k)$ 等价于同余方程组：

$$\{\begin{array}{l}a\equiv b(\mathrm{mod}{m}_1)\\ ⋮\\ a\equiv b(\mathrm{mod}{m}_k)\end{array}$$

这允许我们将大数运算分解为多个小数运算，提高计算效率（如 RSA 解密中的优化）。