数论13_中国剩余定理_CRT

吴老师

2026-08-23 15:02:53

发布于：广东

7阅读

0回复

0点赞

13 中国剩余定理 CRT

学习目标

学完这一节，你应该能够：

理解中国剩余定理解决什么问题；
理解经典 CRT 为什么要求模数两两互质；
理解“只对一个同余条件起作用的开关”怎样构造；
一步一步推出 CRT 的构造公式；
验证构造出的解确实满足所有同余条件；
理解为什么解在模所有模数乘积的意义下唯一；
看懂经典 CRT 的 C++ 实现。

1. CRT 要解决什么问题

有时一个整数需要同时满足多个余数条件。

例如求整数 $x$ ，满足：

$x\equiv2\pmod3$

$x\equiv3\pmod5$

$x\equiv2\pmod7$

也就是说：

$x$ 除以 3 余 2；
$x$ 除以 5 余 3；
$x$ 除以 7 余 2。

枚举可以发现：

$x=23$

因为：

$23\bmod3=2$

$23\bmod5=3$

$23\bmod7=2$

中国剩余定理就是用来系统解决这类问题的。

2. 经典中国剩余定理的条件

考虑：

$x\equiv a_1\pmod{m_1}$

$x\equiv a_2\pmod{m_2}$

一直到：

$x\equiv a_k\pmod{m_k}$

经典 CRT 要求：

$m_1,m_2,\dots,m_k$

两两互质。

“两两互质”表示任意两个不同模数都满足：

$\gcd(m_i,m_j)=1$

在这个条件下：

方程组一定有解；
所有解在模：

$M=m_1m_2\cdots m_k$

意义下属于同一个剩余类。

下面从“怎样构造一个解”开始。

3. 先构造一个只负责第一个条件的数

先看三个模数：

$m_1,m_2,m_3$

希望构造一个数 $E_1$ ，满足：

$E_1\equiv1\pmod{m_1}$

但是：

$E_1\equiv0\pmod{m_2}$

并且：

$E_1\equiv0\pmod{m_3}$

为什么这样构造有用？

因为把它乘上 $a_1$ 后：

模 $m_1$ ：

$a_1E_1\equiv a_1\pmod{m_1}$

模 $m_2$ ：

$a_1E_1\equiv0\pmod{m_2}$

模 $m_3$ ：

$a_1E_1\equiv0\pmod{m_3}$

所以：

$a_1E_1$ 只负责第一个余数条件，不会干扰另外两个条件。

可以把 $E_1$ 理解成“只打开第一个条件的开关”。

4. 怎样先让它在其他模数下都等于 0

为了让：

$E_1\equiv0\pmod{m_2}$

以及：

$E_1\equiv0\pmod{m_3}$

先取：

$M_1=m_2m_3$

因为 $M_1$ 含有因子 $m_2$ ：

$m_2\mid M_1$

所以：

$M_1\equiv0\pmod{m_2}$

同理：

$M_1\equiv0\pmod{m_3}$

这样，“在其他模数下等于 0”的要求已经满足。

5. 但是 $M_1$ 在模 $m_1$ 下未必等于 1

我们还希望：

$E_1\equiv1\pmod{m_1}$

但是：

$M_1=m_2m_3$

模 $m_1$ 后一般不一定等于 1。

所以再乘一个整数 $t_1$ ，希望：

$M_1t_1\equiv1\pmod{m_1}$

也就是说， $t_1$ 应该是 $M_1$ 在模 $m_1$ 下的逆元。

6. 为什么 $M_1$ 的逆元一定存在

因为：

$m_1,m_2,m_3$

两两互质。

假设 $M_1$ 和 $m_1$ 有一个大于 1 的公共质因子 $q$ 。

那么：

$q\mid M_1=m_2m_3$

因为 $q$ 是质数，所以 $q$ 必须整除 $m_2$ 或 $m_3$ 中至少一个。

同时又有：

$q\mid m_1$

这就说明 $m_1$ 与 $m_2$ 或 $m_3$ 有大于 1 的公共因子，与“两两互质”矛盾。

所以：

$\gcd(M_1,m_1)=1$

因此 $M_1$ 在模 $m_1$ 下存在逆元。

可以找到 $t_1$ ，使：

$M_1t_1\equiv1\pmod{m_1}$

于是令：

$E_1=M_1t_1$

就有：

$E_1\equiv1\pmod{m_1}$

并且因为 $E_1$ 仍然含有因子 $M_1=m_2m_3$ ：

$E_1\equiv0\pmod{m_2}$

$E_1\equiv0\pmod{m_3}$

7. 同样构造其他“开关”

令：

$M=m_1m_2m_3$

定义：

$M_1=\frac{M}{m_1}$

$M_2=\frac{M}{m_2}$

$M_3=\frac{M}{m_3}$

分别寻找：

$M_1t_1\equiv1\pmod{m_1}$

$M_2t_2\equiv1\pmod{m_2}$

$M_3t_3\equiv1\pmod{m_3}$

再令：

$E_1=M_1t_1$

$E_2=M_2t_2$

$E_3=M_3t_3$

那么：

$E_1$ 只在模 $m_1$ 下等于 1，在另外两个模数下等于 0；
$E_2$ 只在模 $m_2$ 下等于 1，在另外两个模数下等于 0；
$E_3$ 只在模 $m_3$ 下等于 1，在另外两个模数下等于 0。

8. 把这些“开关”加起来

构造：

$x=a_1E_1+a_2E_2+a_3E_3$

模 $m_1$ ：

$x\equiv a_1\cdot1+a_2\cdot0+a_3\cdot0\pmod{m_1}$

所以：

$x\equiv a_1\pmod{m_1}$

模 $m_2$ ：

$x\equiv a_1\cdot0+a_2\cdot1+a_3\cdot0\pmod{m_2}$

所以：

$x\equiv a_2\pmod{m_2}$

模 $m_3$ ：

$x\equiv a_1\cdot0+a_2\cdot0+a_3\cdot1\pmod{m_3}$

所以：

$x\equiv a_3\pmod{m_3}$

因此这个 $x$ 同时满足三个同余条件。

9. 推广到 $k$ 个同余条件

令：

$M=m_1m_2\cdots m_k$

对每个 $i$ 定义：

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

因为所有模数两两互质，所以：

$\gcd(M_i,m_i)=1$

因此 $M_i$ 在模 $m_i$ 下存在逆元。

设 $t_i$ 满足：

$M_it_i\equiv1\pmod{m_i}$

那么：

$E_i=M_it_i$

满足：

$E_i\equiv1\pmod{m_i}$

对于任意 $j\ne i$ ，因为 $M_i$ 中仍然含有因子 $m_j$ ，所以：

$E_i\equiv0\pmod{m_j}$

因此构造：

$x=a_1M_1t_1+a_2M_2t_2+\cdots+a_kM_kt_k$

就能同时满足全部同余条件。

也可以用求和符号简写为：

$\boxed{x\equiv\sum_{i=1}^{k}a_iM_it_i\pmod M}$

这里的 $\sum$ 只是表示把从 $i=1$ 到 $i=k$ 的这些项全部加起来。

10. 用具体例子完整构造一次

求：

$x\equiv2\pmod3$

$x\equiv3\pmod5$

$x\equiv2\pmod7$

三个模数：

$3,5,7$

两两互质。

先算：

$M=3\times5\times7=105$

10.1 第一个条件

$M_1=\frac{105}{3}=35$

寻找 $t_1$ ，使：

$35t_1\equiv1\pmod3$

因为：

$35\equiv2\pmod3$

所以：

$2t_1\equiv1\pmod3$

取：

$t_1=2$

因为：

$2\times2=4\equiv1\pmod3$

所以：

$E_1=35\times2=70$

10.2 第二个条件

$M_2=\frac{105}{5}=21$

寻找 $t_2$ ，使：

$21t_2\equiv1\pmod5$

因为：

$21\equiv1\pmod5$

所以：

$t_2=1$

因此：

$E_2=21$

10.3 第三个条件

$M_3=\frac{105}{7}=15$

寻找 $t_3$ ，使：

$15t_3\equiv1\pmod7$

因为：

$15\equiv1\pmod7$

所以：

$t_3=1$

因此：

$E_3=15$

10.4 合并

构造：

$x=2E_1+3E_2+2E_3$

代入：

$x=2\times70+3\times21+2\times15$

所以：

$x=140+63+30=233$

而：

$233=105\times2+23$

所以：

$233\equiv23\pmod{105}$

最小非负解是：

$\boxed{x=23}$

11. 为什么解在模 $M$ 下唯一

假设 $x_1$ 和 $x_2$ 都满足所有同余条件。

那么对于每个 $i$ ：

$x_1\equiv a_i\pmod{m_i}$

并且：

$x_2\equiv a_i\pmod{m_i}$

所以：

$x_1\equiv x_2\pmod{m_i}$

根据同余的定义：

$m_i\mid(x_1-x_2)$

也就是说，每一个：

$m_1,m_2,\dots,m_k$

都整除：

$x_1-x_2$

接下来需要说明：为什么它们的乘积也整除这个差。

12. 一个需要用到的小结论

如果：

$\gcd(u,v)=1$

并且：

$u\mid N$

$v\mid N$

那么：

$uv\mid N$

证明如下。

因为：

$u\mid N$

所以存在整数 $s$ ，使：

$N=us$

又因为：

$v\mid N$

所以：

$v\mid us$

由：

$\gcd(u,v)=1$

根据裴蜀定理，存在整数 $A,B$ ，使：

$Au+Bv=1$

两边乘 $s$ ：

$Aus+Bvs=s$

因为：

$v\mid us$

所以：

$v\mid Aus$

而：

$v\mid Bvs$

因此：

$v\mid s$

所以存在整数 $t$ ，使：

$s=vt$

于是：

$N=us=uvt$

因此：

$uv\mid N$

小结论得证。

13. 用这个结论证明 CRT 的唯一性

因为：

$m_1,m_2,\dots,m_k$

两两互质，而且每个 $m_i$ 都整除：

$x_1-x_2$

所以先由：

$m_1\mid(x_1-x_2)$

和：

$m_2\mid(x_1-x_2)$

再利用上一小节的小结论，得到：

$m_1m_2\mid(x_1-x_2)$

接下来还需要确认：

$\gcd(m_1m_2,m_3)=1$

为什么？

如果 $m_1m_2$ 和 $m_3$ 有一个公共质因子 $q$ ，那么 $q$ 整除 $m_1m_2$ ，所以 $q$ 至少整除 $m_1,m_2$ 中的一个。

同时 $q$ 又整除 $m_3$ 。

这就会导致 $m_3$ 与 $m_1$ 或 $m_2$ 不互质，与“两两互质”矛盾。

所以：

$\gcd(m_1m_2,m_3)=1$

于是再利用上一小节的小结论：

$m_1m_2m_3\mid(x_1-x_2)$

继续同样的过程，每加入一个新的 $m_i$ ，它都与前面已经相乘得到的模数乘积互质。

因此最终：

$m_1m_2\cdots m_k\mid(x_1-x_2)$

也就是：

$M\mid(x_1-x_2)$

根据同余的定义：

$\boxed{x_1\equiv x_2\pmod M}$

所以：

所有解在模 $M$ 的意义下属于同一个剩余类。

这就是“解在模 $M$ 下唯一”的含义。

14. C++ 中怎样求 $t_i$

$t_i$ 是 $M_i$ 在模 $m_i$ 下的逆元。

前面已经学过，可以使用扩展欧几里得算法求逆元：

long long exgcd(long long a, long long b,
                long long &x, long long &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }

    long long x1, y1;
    long long g = exgcd(b, a % b, x1, y1);

    x = y1;
    y = x1 - (a / b) * y1;

    return g;
}

long long inv(long long a, long long mod) {
    long long x, y;
    exgcd(a, mod, x, y);

    return (x % mod + mod) % mod;
}

15. 经典 CRT 模板

下面模板假设所有模数的乘积 $M$ 能够放进 long long。

long long CRT(const vector<long long>& a,
              const vector<long long>& m) {
    long long M = 1;

    for (long long x : m) {
        M *= x;
    }

    long long ans = 0;

    for (int i = 0; i < (int)a.size(); i++) {
        long long Mi = M / m[i];
        long long ti = inv(Mi, m[i]);
        long long ai = (a[i] % M + M) % M;

        long long add =
            (long long)((__int128)ai * Mi % M * ti % M);

        ans = (long long)(((__int128)ans + add) % M);
    }

    return ans;
}

这里使用 __int128 计算中间乘积，是为了降低 a[i] * Mi * ti 在乘法过程中溢出的风险。

如果连所有模数的乘积 $M$ 本身都超过 long long，还需要进一步改写数据类型和算法实现。

16. 代码逐步对应公式

先计算：

long long M = 1;

for (long long x : m) {
    M *= x;
}

对应：

$M=m_1m_2\cdots m_k$

然后：

long long Mi = M / m[i];

对应：

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

接着：

long long ti = inv(Mi, m[i]);

对应：

$M_it_i\equiv1\pmod{m_i}$

最后：

ans = ans + a[i] * Mi * ti;

在数学上对应不断加入：

$a_iM_it_i$

最终得到：

$x\equiv\sum_{i=1}^{k}a_iM_it_i\pmod M$

17. 为什么经典 CRT 强调“两两互质”

构造中的关键一步是：

$M_i=\frac M{m_i}$

必须在模 $m_i$ 下存在逆元。

这要求：

$\gcd(M_i,m_i)=1$

当所有模数两两互质时，这个条件自动成立。

如果模数不两两互质，就不能直接使用这里的经典 CRT 构造。

那种情况需要另外判断各个同余条件是否相容，并使用更一般的方法处理，不属于本章的经典 CRT 范围。

18. 小练习

练习 1

为什么希望构造：

$E_i\equiv1\pmod{m_i}$

同时对于 $j\ne i$ ：

$E_i\equiv0\pmod{m_j}$

练习 2

为什么：

$M_i=\frac M{m_i}$

在模其他 $m_j$ 下自动等于 0？

练习 3

为什么 $M_i$ 在模 $m_i$ 下存在逆元？

练习 4

求最小非负整数 $x$ ：

$x\equiv1\pmod3$

$x\equiv2\pmod5$

19. 答案

练习 1

因为这样 $a_iE_i$ 只负责第 $i$ 个余数条件，不会影响其他条件。

练习 2

当 $j\ne i$ 时， $M_i$ 的乘积中仍然包含因子 $m_j$ ，所以：

$m_j\mid M_i$

因此：

$M_i\equiv0\pmod{m_j}$

练习 3

因为所有模数两两互质，所以：

$\gcd(M_i,m_i)=1$

根据逆元存在条件， $M_i$ 在模 $m_i$ 下存在逆元。

练习 4

满足：

$x\equiv1\pmod3$

的数有：

$1,4,7,10,\dots$

其中：

$7\equiv2\pmod5$

所以最小非负解是：

$\boxed{7}$

有帮助，赞一个

去预览

0/2000

这里空空如也

13 中国剩余定理 CRT

学习目标

1. CRT 要解决什么问题

2. 经典中国剩余定理的条件

3. 先构造一个只负责第一个条件的数

4. 怎样先让它在其他模数下都等于 0

5. 但是 M1M_1M1​ 在模 m1m_1m1​ 下未必等于 1

6. 为什么 M1M_1M1​ 的逆元一定存在

7. 同样构造其他“开关”

8. 把这些“开关”加起来

9. 推广到 kkk 个同余条件

10. 用具体例子完整构造一次

10.1 第一个条件

10.2 第二个条件

10.3 第三个条件

10.4 合并

11. 为什么解在模 MMM 下唯一

12. 一个需要用到的小结论

13. 用这个结论证明 CRT 的唯一性

14. C++ 中怎样求 tit_iti​

15. 经典 CRT 模板

16. 代码逐步对应公式

17. 为什么经典 CRT 强调“两两互质”

18. 小练习

练习 1

练习 2

练习 3

练习 4

19. 答案

练习 1

练习 2

练习 3

练习 4

热门讨论

5. 但是 $M_1$ 在模 $m_1$ 下未必等于 1

6. 为什么 $M_1$ 的逆元一定存在

9. 推广到 $k$ 个同余条件

11. 为什么解在模 $M$ 下唯一

14. C++ 中怎样求 $t_i$