中国剩余定理（Chinese Remainder Theorem, CRT），也叫孙子定理，是解决线性同余方程组的定理和算法。

线性同余方程组

设 a_1, \dots, a_n, m_1, \dots, m_n 是已知的 2n 个整数，x 是未知整数，则形如

\begin{cases} x \equiv a_1 \pmod{m_1}; \\ \cdots \quad \cdots \quad \cdots \\ x \equiv a_n \pmod{m_n}; \\ \end{cases}

的方程组称为线性同余方程组。

转化

当方程不是标准形式，例如由 ax \equiv b \pmod{m} 给出时，可以由线性同余方程解得 x \equiv x_0 \pmod{m'}，转化为标准形式。

中国剩余定理

定理

若线性同余方程组中的模数 m_1, \dots, m_n 两两互质，令 M = m_1 \cdots m_n，M_i = M / m_i，令 M_i^{-1} 为模 m_i 意义下 M_i 的逆元，则

x_0 = \sum_{i = 1}^n a_i M_i M_i^{-1}

为原线性同余方程组的一个特解。方程组的通解则为

x \equiv x_0 \pmod{M}.

换句话说，在同构的意义下，x_0 是原方程组的唯一解。

上述定理被称为中国剩余定理（Chinese remainder theorem, CRT），得名于《孙子算经》中的一道例题。

证明

坐标与环同构

CRT 揭示了一种深层的坐标思想，我们可以把一个数 x 分别对 m_1, \dots, m_n 取模得到的余数 a_1, \dots, a_n 看作是它的坐标。令 M = m_1 \cdots m_n，则模 M 意义下任何一个数都可以分解出一个坐标：

x \mapsto (x \bmod m_1, \dots, x \bmod m_n).

并且，x 和它的坐标 (a_1, \dots, a_n) 是一个一一对应，因为两个集合的大小都是 M = m_1 \cdots m_n，而不同的数一定对应不同的坐标。

在 CRT 的计算过程中，我们构造了 M_i M_i^{-1}，实际上，这就是一个标准单位向量。因为 M_i 是其他模数的乘积，所以对 m_j 取模一定为 0；而根据逆元的定义，M_i M_i^{-1} 在模 m_i 的意义下一定等于 1，所以我们得到了单位向量：

e_i = (0, \dots, \underbrace{1}_{\text{第 } i \text{ 个元素}}, \dots, 0).

扩展中国剩余定理

扩展中国剩余定理（extended Chinese remainder theorem, exCRT）是用于解决模数不两两互质的情形的定理。严格来说，这同时是一个算法。

两两合并

首先讨论

\begin{cases} x \equiv a_1 \pmod{m_1}; \\ x \equiv a_2 \pmod{m_2}; \\ \end{cases}

的解。两个方程可以分别改写为 x = a_1 + k m_1 和 x + l m_2 = a_2，其中 k, l 是任意的整数。将 x 消掉，得到

km_1 + lm_2 = a_2 - a_1.

这是一个关于 k, l 的二元一次不定方程。若 (m_1, m_2) \nmid a_2 - a_1，则不定方程无解，原方程组也无解。若 (m_1, m_2) \mid a_2 - a_1，则可以找到不定方程的一个特解 k_0, l_0，此时令 x_0 = a_1 + k_0 m_1，就可以得到原方程组的一个特解 x_0。

找到特解后，当 x' = x_0 + k [m_1, m_2] 时，显然两个同余方程都能满足。而因为 [m_1, m_2] 是 m_1 和 m_2 的最小公倍数，当 x_0 < x' < x_0 + [m_1, m_2] 时，至少有一个同余方程无法满足，否则 x' 将是一个更小的公倍数，矛盾。因此，方程组的通解就是 x \equiv x_0 \pmod{[m_1, m_2]}。

利用这种方法可以将两个线性同余方程合并为一个。有 n 个线性同余方程时，只要两两进行合并，合并 n - 1 次就得到了通解。

质因数分解法

见 https://www.luogu.com.cn/article/vm4q9cek

思想：先把形如 x \equiv a \pmod{m} 的方程中的 m 做质因数分解，得到若干个形如

x \equiv p_i^{l_i} \pmod{m}

的方程。将所有方程按模数的质因数分解后，将同个质数幂模数的方程合并。具体而言，对形如 x \equiv a \pmod{p^k} 和 x \equiv b \pmod{p^l} 的方程，设 k < l，若 a \equiv b \pmod{p^{k}}，则两个方程不矛盾，取幂次较大的一个数 l 保留即可，剩下一个方程 x \equiv b \pmod{p^l}；若 a \not\equiv b \pmod{p^{k}}，则方程矛盾，原方程组无解。

最后剩下的方程满足中国剩余定理，直接得到答案即可。

有解判别

判别方程组

\begin{cases} x \equiv a_1 \pmod{m_1}; \\ \cdots \quad \cdots \quad \cdots \\ x \equiv a_n \pmod{m_n}; \\ \end{cases}

是否有解，可以使用 exCRT 两两合并，若其中一步合并的过程无解，则方程组无解。

也可以直接通过两两比较，判定方程解的存在性：当且仅当从 n 个方程中任选两个都可以合并时，方程组可以合并。也就是当且仅当对任意的 1 \le i, j \le n（i \ne j）都有 (m_i, m_j) \mid a_i - a_j 时，方程组有解。这种方法的复杂度是 O(n^2)。