数学基础 -- 中国剩余定理

中国剩余定理（Chinese Remainder Theorem, CRT）

定理描述

设有一组整数方程：

$$\{\begin{array}{l}x\equiv a_1(\text{mod}{m}_1)\\ x\equiv a_2(\text{mod}{m}_2)\\ ⋮\\ x\equiv a_n(\text{mod}{m}_n)\end{array}$$

其中，$m_1,m_2,\dots ,m_n$ 是两两互质的正整数（即任意两个 $m_i$ 和 $m_j$ 互质），$a_1,a_2,\dots ,a_n$ 是任意整数。

中国剩余定理指出，这组方程有解，并且在模 $M=m_1\times m_2\times \cdots \times m_n$ 的意义下，解是唯一的。

---

解的构造方法

1. 计算 $M$

$$M=m_1\times m_2\times \cdots \times m_n$$

2. 计算每个 $M_i$

$$M_i=\frac{M}{m_i}$$

3. 求 $M_i$ 关于 $m_i$ 的逆元 $t_i$

即找到一个整数 $t_i$，使得：

$$t_i\times M_i\equiv 1(\text{mod}{m}_i)$$

可以通过扩展欧几里得算法求得。

4. 构造解 $x$

$$x=\sum _{i=1}^n{a}_i\times t_i\times M_i$$

然后，取 $x$ 模 $M$ 的结果：

$$x\equiv \left(\sum _{i=1}^n{a}_i\times t_i\times M_i\right)(\text{mod}M)$$

这个 $x$ 即为满足原同余方程组的解。

---

示例

考虑以下同余方程组：

$$\{\begin{array}{l}x\equiv 2(\text{mod}3)\\ x\equiv 3(\text{mod}5)\\ x\equiv 2(\text{mod}7)\end{array}$$

解法

1. 计算 $M$：

$$M=3\times 5\times 7=105$$

2. 计算每个 $M_i$：

$$\begin{array}{rl}{M}_1& =\frac{105}{3}=35\\ M_2& =\frac{105}{5}=21\\ M_3& =\frac{105}{7}=15\end{array}$$

3. 求每个 $M_i$ 关于对应 $m_i$ 的逆元 $t_i$：

• 求 $t_1$：需要找到 $t_1$，使得：

  $$35\times t_1\equiv 1(\text{mod}3)$$

  因为 $35\equiv 2(\text{mod}3)$，所以：

  $$2\times t_1\equiv 1(\text{mod}3)$$

  通过尝试，得到 $t_1=2$，因为：

  $$2\times 2=4\equiv 1(\text{mod}3)$$

• 求 $t_2$：需要找到 $t_2$，使得：

  $$21\times t_2\equiv 1(\text{mod}5)$$

  因为 $21\equiv 1(\text{mod}5)$，所以 $t_2=1$。

• 求 $t_3$：需要找到 $t_3$，使得：

  $$15\times t_3\equiv 1(\text{mod}7)$$

  因为 $15\equiv 1(\text{mod}7)$，所以 $t_3=1$。

4. 构造解 $x$：

$$\begin{array}{rl}x& =(2\times 2\times 35)+(3\times 1\times 21)+(2\times 1\times 15)\\ & =140+63+30\\ & =233\end{array}$$

5. 求模结果：

$$x\equiv 233(\text{mod}105)=23$$

因此，方程组的解为 $x=23$。

---

总结

中国剩余定理在求解一组特定同余方程时非常高效，特别是在密码学、计算机科学等领域有广泛应用。其解的唯一性和构造方法，使得该定理成为数论中的重要工具。