困难通用14 分钟4,898 字

中国剩余定理(CRT)

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

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

{x≡2(mod3)x≡3(mod5)x≡2(mod7)\begin{cases} x \equiv 2 \pmod{3} \ x \equiv 3 \pmod{5} \ x \equiv 2 \pmod{7} \end{cases}⎩⎨⎧​x≡2(mod3)x≡3(mod5)x≡2(mod7)​

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


中国剩余定理的数学公式

假如你有 kkk 个模数两两互素(即任意两个模数的最大公约数为1)的同余方程:

{x≡a1(modm1)x≡a2(modm2)⋮x≡ak(modmk)\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}⎩⎨⎧​x≡a1​(modm1​)x≡a2​(modm2​)⋮x≡ak​(modmk​)​

那么方程组一定有解,并且在模 M=m1×m2×⋯×mkM = m_1 \times m_2 \times \cdots \times m_kM=m1​×m2​×⋯×mk​ 下解是唯一的。 解可以写成:

x=∑i=1kai⋅Mi⋅invi(modM)x = \sum_{i=1}^{k} a_i \cdot M_i \cdot \text{inv}_i \pmod{M}x=i=1∑k​ai​⋅Mi​⋅invi​(modM)

其中:

  • M=m1⋅m2⋯mkM = m_1 \cdot m_2 \cdots m_kM=m1​⋅m2​⋯mk​(所有模数的乘积)
  • Mi=M/miM_i = M / m_iMi​=M/mi​(去掉第 iii 个模数后,剩下所有模数的乘积)
  • invi\text{inv}_iinvi​ 是 MiM_iMi​ 模 mim_imi​ 的乘法逆元​​,即满足 Mi⋅invi≡1(modmi)M_i \cdot \text{inv}_i \equiv 1 \pmod{m_i}Mi​⋅invi​≡1(modmi​) 的那个整数。

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


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

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

我们希望构造一个 xxx,使得:

  • 在模 m1m_1m1​ 下,它等于 a1a_1a1​;
  • 在模 m2m_2m2​ 下,它等于 a2a_2a2​;
  • ……
  • 在模 mkm_kmk​ 下,它等于 aka_kak​。

一个巧妙的方法是把每个余数单独做成一项​​,然后加起来。 比如,第一项 a1⋅M1⋅inv1a_1 \cdot M_1 \cdot \text{inv}_1a1​⋅M1​⋅inv1​ 要满足:

  • 模 m1m_1m1​ 时等于 a1a_1a1​(因为 M1⋅inv1≡1(modm1)M_1 \cdot \text{inv}_1 \equiv 1 \pmod{m_1}M1​⋅inv1​≡1(modm1​));
  • 模其他 mj(j≠1)m_j (j\neq1)mj​(j=1) 时等于0(因为 M1M_1M1​ 是 mjm_jmj​ 的倍数,所以模 mjm_jmj​ 为0)。

这样,所有项加起来,在模 m1m_1m1​ 时只有第一项贡献 a1a_1a1​,其他项都是0;在模 m2m_2m2​ 时只有第二项贡献 a2a_2a2​,其他项是0……完美分开。

2. 那“逆元”是什么?

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

3. 唯一性:为什么解是唯一的?

假如有两个解 x1x_1x1​ 和 x2x_2x2​,它们都满足方程组。那么它们的差 x1−x2x_1 - x_2x1​−x2​ 可以被每一个 mim_imi​ 整除,所以也能被它们的乘积 MMM 整除。也就是说,x1≡x2(modM)x_1 \equiv x_2 \pmod{M}x1​≡x2​(modM),所以在模 MMM 下只有一个解。


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

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

  • m1=3,a1=2;m2=5,a2=3;m3=7,a3=2m_1=3, a_1=2; m_2=5, a_2=3; m_3=7, a_3=2m1​=3,a1​=2;m2​=5,a2​=3;m3​=7,a3​=2
  • M=3×5×7=105M = 3\times5\times7 = 105M=3×5×7=105
  • M1=105/3=35M_1 = 105/3 = 35M1​=105/3=35,求35模3的逆元:35≡2(mod3)35 \equiv 2 \pmod{3}35≡2(mod3),2的逆元是2(因为 2×2=4≡12\times2=4\equiv12×2=4≡1),所以 inv1=2\text{inv}_1=2inv1​=2。
  • M2=105/5=21M_2 = 105/5 = 21M2​=105/5=21,21≡1(mod5)21\equiv1 \pmod{5}21≡1(mod5),逆元是1。
  • M3=105/7=15M_3 = 105/7 = 15M3​=105/7=15,15≡1(mod7)15\equiv1 \pmod{7}15≡1(mod7),逆元是1。
  • 总和:2×35×2+3×21×1+2×15×1=140+63+30=233≡233−2×105=23(mod105)2\times35\times2 + 3\times21\times1 + 2\times15\times1 = 140 + 63 + 30 = 233 \equiv 233 - 2\times105 = 23 \pmod{105}2×35×2+3×21×1+2×15×1=140+63+30=233≡233−2×105=23(mod105)

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


编程实现中国剩余定理(CRT)

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

  1. 计算所有模数的乘积 MMM。
  2. 对每个 iii:
  • 计算 Mi=M/miM_i = M / m_iMi​=M/mi​
  • 用扩展欧几里得算法求 MiM_iMi​ 模 mim_imi​ 的逆元(之所以要扩展欧几里得,是因为它能高效求解 ax+by=gcd⁡(a,b)ax + by = \gcd(a,b)ax+by=gcd(a,b) 的一组整数解,当 gcd⁡=1\gcd=1gcd=1 时,xxx 就是逆元)
  1. 累加 ai×Mi×invia_i \times M_i \times \text{inv}_iai​×Mi​×invi​,最后模 MMM,得到最小非负解。

注意事项(新手容易犯的错误)

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

C++ 完整代码示例(带中文注释)

cpp
#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 完整代码示例(带中文注释)

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)

新手常见错误

  1. 忘记两两互素的条件 试着用CRT解 x≡1(mod4),x≡3(mod6)x \equiv 1 \pmod{4}, x \equiv 3 \pmod{6}x≡1(mod4),x≡3(mod6),会发现 M1M_1M1​ 和 m1m_1m1​ 不互素(4和6不互素),会导致逆元不存在或解不唯一。这时候必须用​扩展中国剩余定理​。
  2. 逆元计算错误 用扩展欧几里得时,求出的 xxx 可能为负数,要加 mmm 取正。有些同学忘了这一步,结果得到负解。
  3. 整数溢出(C++)​ 当模数很大时,ai×Mia_i \times M_iai​×Mi​ 可能超过 int 范围,记得用 long long 并每一步取模。Python没有这个问题。
  4. 误把余数当模数 CRT公式里的 aia_iai​ 是余数,mim_imi​ 是模数,不要写反了。

完整示例:自定义测试

如果你想验证一个方程组,可以用下面的步骤手算或程序算:

问题​​:一个数除以4余0,除以5余3,除以9余1,求这个数的最小值。

  • 模数:4, 5, 9(两两互素)
  • 余数:0, 3, 1
  • 用代码跑一下,结果应该是?
python
rem = [0, 3, 1]
mod = [4, 5, 9]
print(crt(rem, mod))  # 输出 ?

程序输出:? (留给你自己运行看看,也可以手算验证)

手算提示​​:M=180M=180M=180,M1=45M_1=45M1​=45,逆元?45≡1(mod4)45\equiv1\pmod445≡1(mod4),inv=1 → 项=0;M2=36M_2=36M2​=36,逆元?36≡1(mod5)36\equiv1\pmod536≡1(mod5),inv=1 → 3×36=1083\times36=1083×36=108;M3=20M_3=20M3​=20,逆元?20≡2(mod9)20\equiv2\pmod920≡2(mod9),2的逆元是5(因为2×5=10≡12\times5=10\equiv12×5=10≡1)→ 1×20×5=1001\times20\times5=1001×20×5=100;总和 108+100=208≡28(mod180)108+100=208\equiv 28\pmod{180}108+100=208≡28(mod180)。所以答案是28。验算:28%4=0,28%5=3,28%9=1,正确。


中国剩余定理的用途

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

相关知识点链接

  • 扩展欧几里得算法​​:求逆元的基础,也是解决丢番图方程的工具。
  • 扩展中国剩余定理​​:当模数不互素时,如何求解同余方程组。
  • RSA算法​​:现代加密技术中用到CRT加速。
  • 高斯函数与同余​​:更深层的数论知识。

总结

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

同类知识点