中国剩余定理（CRT）

从《孙子算经》的故事说起

你听说过“物不知数”这个问题吗？
《孙子算经》里有个经典问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”
翻译成数学语言就是：有一个整数 $x$ ，它除以3余2，除以5余3，除以7余2，求这个数的最小值。
这就是一个同余方程组：

\begin{cases} x \equiv 2 \pmod{3} \\ x \equiv 3 \pmod{5} \\ x \equiv 2 \pmod{7} \end{cases}

中国古人通过猜测和试算找到了答案：23。
一千多年后，这个解法被西方数学家称为中国剩余定理（Chinese Remainder Theorem, CRT），它给出了解决这类方程组的一般公式。

中国剩余定理的数学公式

假如你有 $k$ 个模数两两互素（即任意两个模数的最大公约数为1）的同余方程：

\begin{cases} x \equiv a_1 \pmod{m_1} \\ x \equiv a_2 \pmod{m_2} \\ \vdots \\ x \equiv a_k \pmod{m_k} \end{cases}

那么方程组一定有解，并且在模 $M = m_1 \times m_2 \times \cdots \times m_k$ 下解是唯一的。
解可以写成：

x = \sum_{i=1}^{k} a_i \cdot M_i \cdot \text{inv}_i \pmod{M}

其中：

$M = m_1 \cdot m_2 \cdots m_k$ （所有模数的乘积）
$M_i = M / m_i$ （去掉第 $i$ 个模数后，剩下所有模数的乘积）
$\text{inv}_i$ 是 $M_i$ 模 $m_i$ 的乘法逆元，即满足 $M_i \cdot \text{inv}_i \equiv 1 \pmod{m_i}$ 的那个整数。

如果你觉得符号太多，别着急，下面我们用生活中的例子帮你理解每个符号。

一步一步推导公式，就像拼乐高

1. 核心思想：每个余数只管自己的模数

我们希望构造一个 $x$ ，使得：

在模 $m_1$ 下，它等于 $a_1$ ；
在模 $m_2$ 下，它等于 $a_2$ ；
……
在模 $m_k$ 下，它等于 $a_k$ 。

一个巧妙的方法是把每个余数单独做成一项，然后加起来。
比如，第一项 $a_1 \cdot M_1 \cdot \text{inv}_1$ 要满足：

模 $m_1$ 时等于 $a_1$ （因为 $M_1 \cdot \text{inv}_1 \equiv 1 \pmod{m_1}$ ）；
模其他 $m_j (j\neq1)$ 时等于0（因为 $M_1$ 是 $m_j$ 的倍数，所以模 $m_j$ 为0）。

这样，所有项加起来，在模 $m_1$ 时只有第一项贡献 $a_1$ ，其他项都是0；在模 $m_2$ 时只有第二项贡献 $a_2$ ，其他项是0……完美分开。

2. 那“逆元”是什么？

逆元有点像“倒着走的路”。
比如在模7的世界里，3的逆元是5，因为 $3 \times 5 = 15 \equiv 1 \pmod{7}$ 。
你可以这样记：一个数乘上它的逆元，结果就变成了1（在模运算下）。
日常生活中，我们有时候也需要“逆”操作：比如你有3个苹果，想平均分给7个人，每个人分不到一个，但如果你想知道“分掉多少个苹果后剩下1个”，逆元能帮你算出来。

3. 唯一性：为什么解是唯一的？

假如有两个解 $x_1$ 和 $x_2$ ，它们都满足方程组。那么它们的差 $x_1 - x_2$ 可以被每一个 $m_i$ 整除，所以也能被它们的乘积 $M$ 整除。也就是说， $x_1 \equiv x_2 \pmod{M}$ ，所以在模 $M$ 下只有一个解。

生活中的“物不知数”问题

假设你有一袋糖果，每次分给3个小朋友会剩下2颗，分给5个小朋友会剩下3颗，分给7个小朋友会剩下2颗。糖果至少有多少颗？
这就是我们开头的那个问题。用公式算一遍：

$m_1=3, a_1=2; m_2=5, a_2=3; m_3=7, a_3=2$
$M = 3\times5\times7 = 105$
$M_1 = 105/3 = 35$ ，求35模3的逆元： $35 \equiv 2 \pmod{3}$ ，2的逆元是2（因为 $2\times2=4\equiv1$ ），所以 $\text{inv}_1=2$ 。
$M_2 = 105/5 = 21$ ， $21\equiv1 \pmod{5}$ ，逆元是1。
$M_3 = 105/7 = 15$ ， $15\equiv1 \pmod{7}$ ，逆元是1。
总和： $2\times35\times2 + 3\times21\times1 + 2\times15\times1 = 140 + 63 + 30 = 233 \equiv 233 - 2\times105 = 23 \pmod{105}$

最小非负解是23，所以糖果至少有23颗！验算一下：23 ÷ 3 = 7余2，23 ÷ 5 = 4余3，23 ÷ 7 = 3余2，完全正确。

编程实现中国剩余定理（CRT）

计算机可以帮我们快速计算任意模数两两互素的同余方程组。我们先用伪代码梳理步骤：

计算所有模数的乘积 $M$ 。
对每个 $i$ $i$ ：
- 计算 $M_i = M / m_i$
- 用扩展欧几里得算法求 $M_i$ 模 $m_i$ 的逆元（之所以要扩展欧几里得，是因为它能高效求解 $ax + by = \gcd(a,b)$ 的一组整数解，当 $\gcd=1$ 时， $x$ 就是逆元）
累加 $a_i \times M_i \times \text{inv}_i$ ，最后模 $M$ ，得到最小非负解。

注意事项（新手容易犯的错误）

模数必须两两互素：如果模数不互素，公式不成立，需要改用扩展中国剩余定理。
逆元可能为负数：扩展欧几里得求出的 $x$ 可能是负数，要取模归一化到 $[0, m-1]$ 之间。
乘法溢出：在C++中， $a_i \times M_i$ 可能很大，要用 long long 强制类型转换，每一步取模。
不要忘记取模：累加过程中可能超过 $M$ ，每一步都取模，最后结果才最小。

C++ 完整代码示例（带中文注释）

#include <iostream>
#include <vector>
using namespace std;

// 扩展欧几里得，返回 gcd，并设置 x, y 使得 ax + by = gcd(a,b)
int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}

// 求 a 模 m 的逆元（假设 a 和 m 互质）
int mod_inverse(int a, int m) {
    int x, y;
    exgcd(a, m, x, y);
    // 确保逆元是非负的
    return (x % m + m) % m;
}

// 中国剩余定理：输入余数数组 rem 和模数数组 mod，模数两两互素
// 返回最小非负解
int crt(const vector<int>& rem, const vector<int>& mod) {
    int M = 1;
    for (int m : mod) M *= m;           // 所有模数的乘积
    int result = 0;
    for (size_t i = 0; i < rem.size(); ++i) {
        int Mi = M / mod[i];            // 去掉当前模数后的乘积
        int inv = mod_inverse(Mi % mod[i], mod[i]);  // 逆元
        // 累加时注意用 long long 防止溢出，每一步取模
        result = (result + (long long)rem[i] * Mi % M * inv) % M;
    }
    return result;
}

int main() {
    // 例子1：物不知数（23颗糖）
    vector<int> rem = {2, 3, 2};
    vector<int> mod = {3, 5, 7};
    int x = crt(rem, mod);
    cout << "物不知数问题的解为: " << x << " (mod " << (3*5*7) << ")" << endl; // 23

    // 例子2：x ≡ 1 (mod 3), x ≡ 2 (mod 5), x ≡ 3 (mod 7)
    rem = {1, 2, 3};
    mod = {3, 5, 7};
    x = crt(rem, mod);
    cout << "第二个例子解为: " << x << " (mod " << (3*5*7) << ")" << endl; // 52

    return 0;
}

运行结果：

物不知数问题的解为: 23 (mod 105)
第二个例子解为: 52 (mod 105)

Python 完整代码示例（带中文注释）

def exgcd(a, b):
    """扩展欧几里得，返回 (g, x, y) 使得 ax + by = g"""
    if b == 0:
        return (a, 1, 0)
    g, x1, y1 = exgcd(b, a % b)
    x = y1
    y = x1 - (a // b) * y1
    return (g, x, y)

def mod_inverse(a, m):
    """求 a 模 m 的逆元（a 与 m 互质）"""
    g, x, y = exgcd(a, m)
    # g 应该为 1，因为互质
    return x % m

def crt(rem, mod):
    """中国剩余定理，模数两两互素，返回最小非负解"""
    M = 1
    for m in mod:
        M *= m                     # 所有模数的乘积
    result = 0
    for i in range(len(rem)):
        Mi = M // mod[i]           # 去掉当前模数后的乘积
        inv = mod_inverse(Mi % mod[i], mod[i])  # 逆元
        result = (result + rem[i] * Mi * inv) % M
    return result

if __name__ == "__main__":
    # 例子1：物不知数（23颗糖）
    rem = [2, 3, 2]
    mod = [3, 5, 7]
    x = crt(rem, mod)
    print(f"物不知数问题的解为: {x} (mod {3*5*7})")  # 23

    # 例子2：x ≡ 1 (mod 3), x ≡ 2 (mod 5), x ≡ 3 (mod 7)
    rem = [1, 2, 3]
    mod = [3, 5, 7]
    x = crt(rem, mod)
    print(f"第二个例子解为: {x} (mod {3*5*7})")    # 52

运行结果：

物不知数问题的解为: 23 (mod 105)
第二个例子解为: 52 (mod 105)

新手常见错误

忘记两两互素的条件
试着用CRT解 $x \equiv 1 \pmod{4}, x \equiv 3 \pmod{6}$ ，会发现 $M_1$ 和 $m_1$ 不互素（4和6不互素），会导致逆元不存在或解不唯一。这时候必须用扩展中国剩余定理。
逆元计算错误
用扩展欧几里得时，求出的 $x$ 可能为负数，要加 $m$ 取正。有些同学忘了这一步，结果得到负解。
整数溢出（C++）
当模数很大时， $a_i \times M_i$ 可能超过 int 范围，记得用 long long 并每一步取模。Python没有这个问题。
误把余数当模数
CRT公式里的 $a_i$ 是余数， $m_i$ 是模数，不要写反了。

手算提示： $M=180$ ， $M_1=45$ ，逆元？ $45\equiv1\pmod4$ ，inv=1 → 项=0； $M_2=36$ ，逆元？ $36\equiv1\pmod5$ ，inv=1 → $3\times36=108$ ； $M_3=20$ ，逆元？ $20\equiv2\pmod9$ ，2的逆元是5（因为 $2\times5=10\equiv1$ ）→ $1\times20\times5=100$ ；总和 $108+100=208\equiv 28\pmod{180}$ 。所以答案是28。验算：28%4=0，28%5=3，28%9=1，正确。

中国剩余定理的用途

密码学：RSA解密时，用CRT可以加快计算速度（分成几个小模数）。
数论：证明某些整数解的存在性。
竞赛数学：很多数学竞赛题会出“求最小正整数，满足一堆同余条件”。

总结

中国剩余定理就像一把精密的“模数拼图钥匙”：每个模数是一块拼图，逆元是胶水，把每一块粘到正确的位置，最后拼出完整的数字。
它不仅是古人的智慧结晶，也是现代计算机科学和密码学里的重要工具。现在，你不仅能用公式手算，还能用代码自动计算——以后遇到“分糖果”或者“找周期”的问题，就可以轻松搞定啦！