一、核心思想：分而治之 + 线性组合
CRT 的本质是：
如果我们知道一个数 \(x\) 除以两两互质的 \(m_1, m_2, \dots, m_n\) 的余数，那么我们可以唯一确定 \(x\) 除以 \(M = m_1 m_2 \cdots m_n\) 的余数。
原理的关键步骤是构造一组“基解”，每个基解只在一个模数下为 \(1\)，在其他模数下为 \(0\)，然后加权求和。
二、先从两个模数开始理解
假设我们想解：
且 \(\gcd(m_1, m_2) = 1\)。
原理思路
找两个数 \(e_1, e_2\) 使得：
- \(e_1 \equiv 1 \pmod{m_1}\)，且 \(e_1 \equiv 0 \pmod{m_2}\)；
- \(e_2 \equiv 0 \pmod{m_1}\)，且 \(e_2 \equiv 1 \pmod{m_2}\)。
那么令 \(x = a_1 e_1 + a_2 e_2\)，就能满足：
- 模 \(m_1\)：\(x \equiv a_1 \cdot 1 + a_2 \cdot 0 = a_1\)；
- 模 \(m_2\)：\(x \equiv a_1 \cdot 0 + a_2 \cdot 1 = a_2\)。
如何构造 \(e_1\)？
条件：\(e_1 \equiv 1 \pmod{m_1}\) 且 \(e_1 \equiv 0 \pmod{m_2}\)。
因为 \(e_1\) 是 \(m_2\) 的倍数，设 \(e_1 = m_2 \cdot t\)。
代入第一个条件：
由于 \(\gcd(m_2, m_1) = 1\)，\(m_2\) 在模 \(m_1\) 下有逆元，记作 \(m_2^{-1}\)，则：
取最小正整数 \(t_0\)，则 \(e_1 = m_2 \cdot t_0\) 满足要求。
同理，\(e_2 = m_1 \cdot (m_1^{-1} \bmod m_2)\)。
例子
\(m_1 = 3,\ m_2 = 5\)。
-
求 \(e_1\)：找 \(5t \equiv 1 \pmod{3}\)，\(5 \equiv 2\)，\(2t \equiv 1 \Rightarrow t \equiv 2\)，所以 \(e_1 = 5 \times 2 = 10\)。
（\(10 \bmod 3 = 1\)，\(10 \bmod 5 = 0\)，正确） -
求 \(e_2\)：找 \(3t \equiv 1 \pmod{5}\)，\(3 \times 2 = 6 \equiv 1\)，\(t = 2\)，\(e_2 = 3 \times 2 = 6\)。
（\(6 \bmod 3 = 0\)，\(6 \bmod 5 = 1\)，正确）
那么解为 \(x = a_1 \times 10 + a_2 \times 6\)，模 \(15\) 下唯一。
三、推广到 \(n\) 个模数
对于 \(m_1, m_2, \dots, m_n\) 两两互质。
定义：
- \(M = m_1 m_2 \cdots m_n\)
- \(M_i = M / m_i\)（即除了 \(m_i\) 之外其他所有模数的乘积）
我们构造第 \(i\) 个基解 \(e_i\)，使其满足：
因为 \(e_i\) 必须被所有 \(m_j\ (j \neq i)\) 整除，所以 \(e_i\) 是 \(M_i\) 的倍数，设 \(e_i = M_i \cdot t_i\)。
再代入模 \(m_i\) 的条件：
由于 \(M_i\) 与 \(m_i\) 互质（\(m_i\) 与所有 \(m_j\ (j \neq i)\) 互质，所以与它们的乘积也互质），因此 \(M_i\) 在模 \(m_i\) 下可逆。设 \(y_i\) 是 \(M_i\) 的逆元，即：
取 \(t_i = y_i\)，则 \(e_i = M_i y_i\) 就是我们要的基解。
最终解
四、为什么 \(x = \sum a_i M_i y_i\) 是一个特解？
1. 符号回顾
- 模数 \(m_1, m_2, \dots, m_n\) 两两互质
- \(M = m_1 m_2 \cdots m_n\)
- \(M_i = M / m_i\)（即除了 \(m_i\) 以外所有模数的乘积）
- \(y_i\) 是 \(M_i\) 在模 \(m_i\) 下的逆元：
构造：
2. 验证第 \(k\) 个同余式
考虑 \(x \bmod m_k\)：
-
当 \(i = k\) 时：\(a_k M_k y_k\)
因为 \(M_k y_k \equiv 1 \pmod{m_k}\)，所以这一项 \(\equiv a_k \cdot 1 = a_k \pmod{m_k}\)。 -
当 \(i \neq k\) 时：\(a_i M_i y_i\)
注意 \(M_i = M / m_i\)，由于 \(i \neq k\)，\(m_k\) 是 \(M_i\) 的一个因子（因为 \(M_i\) 包含了除了 \(m_i\) 以外的所有模数，其中包括 \(m_k\)）。
因此 \(M_i \equiv 0 \pmod{m_k}\)，所以整项 \(\equiv 0 \pmod{m_k}\)。
加起来：
✅ 对所有 \(k\) 成立，所以 \(x\) 确实是解。
3. 为什么叫“特解”？
因为：
- 这个 \(x\) 是一个具体的数（可能很大）
- 所有解可以写成 \(x + tM\)（\(t \in \mathbb{Z}\)）
- 所以 \(x\) 只是无穷多解中的一个，称为特解
五、总结
| 概念 | 说明 |
|---|---|
| 特解 | \(x = \sum a_i M_i y_i\) 满足所有同余方程 |
| 通解 | \(x + tM,\ t \in \mathbb{Z}\) |
| 最小正整数解 | \(x \bmod M\)（若为 \(0\) 则取 \(M\)） |