中国剩余定理(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∑kai⋅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)
计算机可以帮我们快速计算任意模数两两互素的同余方程组。我们先用伪代码梳理步骤:
- 计算所有模数的乘积 MMM。
- 对每个 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 就是逆元)
- 累加 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++ 完整代码示例(带中文注释)
#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≡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不互素),会导致逆元不存在或解不唯一。这时候必须用扩展中国剩余定理。
- 逆元计算错误 用扩展欧几里得时,求出的 xxx 可能为负数,要加 mmm 取正。有些同学忘了这一步,结果得到负解。
- 整数溢出(C++) 当模数很大时,ai×Mia_i \times M_iai×Mi 可能超过
int范围,记得用long long并每一步取模。Python没有这个问题。 - 误把余数当模数 CRT公式里的 aia_iai 是余数,mim_imi 是模数,不要写反了。
完整示例:自定义测试
如果你想验证一个方程组,可以用下面的步骤手算或程序算:
问题:一个数除以4余0,除以5余3,除以9余1,求这个数的最小值。
- 模数:4, 5, 9(两两互素)
- 余数:0, 3, 1
- 用代码跑一下,结果应该是?
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加速。
- 高斯函数与同余:更深层的数论知识。
总结
中国剩余定理就像一把精密的“模数拼图钥匙”:每个模数是一块拼图,逆元是胶水,把每一块粘到正确的位置,最后拼出完整的数字。 它不仅是古人的智慧结晶,也是现代计算机科学和密码学里的重要工具。现在,你不仅能用公式手算,还能用代码自动计算——以后遇到“分糖果”或者“找周期”的问题,就可以轻松搞定啦!