中国剩余定理
引入
「物不知数」问题：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二．问物几何？
即求满足以下条件的整数：除以 33
余 22，除以 55 余 33，除以 77 余 22．
该问题最早见于《孙子算经》中，并有该问题的具体解法．宋朝数学家秦九韶于 1247 年《数书九章》卷一、二《大衍类》对「物不知数」问题做出了完整系统的解答．上面具体问题的解答口诀由明朝数学家程大位在《算法统宗》中给出：
三人同行七十希，五树梅花廿一支，七子团圆正半月，除百零五便得知．
2 ×70 +3 ×21 +2 ×15 =233 =2 ×105 +232×70+3×21+2×15=233=2×105+23，故答案为 2323．
定义
中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组（其中 𝑛1,𝑛2,⋯,𝑛𝑘n1,n2,⋯,nk 两两互质）：
⎧{ { {⎨{ { {⎩𝑥≡𝑎1(mod𝑛1)𝑥≡𝑎2(mod𝑛2)⋮𝑥≡𝑎𝑘(mod𝑛𝑘){x≡a1(modn1)x≡a2(modn2)⋮x≡ak(modnk)
上面的「物不知数」问题就是一元线性同余方程组的一个实例．
过程
- 计算所有模数的积 𝑛n；
- 对于第 𝑖i 个方程：
- 计算 𝑚𝑖 =𝑛𝑛𝑖mi=nni；
- 计算 𝑚𝑖mi 在模 𝑛𝑖ni 意义下的 逆元 𝑚−1𝑖mi−1；
- 计算 𝑐𝑖 =𝑚𝑖𝑚−1𝑖ci=mimi−1（不要对 𝑛𝑖ni 取模）．
- 方程组在模 𝑛n 意义下的唯一解为：𝑥 =∑𝑘𝑖=1𝑎𝑖𝑐𝑖(mod𝑛)x=∑i=1kaici(modn)．
实现
C++Python
---|---
---|---
证明
我们需要证明上面算法计算所得的 𝑥x 对于任意 𝑖 =1,2,⋯,𝑘i=1,2,⋯,k 满足 𝑥 ≡𝑎𝑖(mod𝑛𝑖)x≡ai(modni)．
当 𝑖 ≠𝑗i≠j 时，有 𝑚𝑗 ≡0(mod𝑛𝑖)mj≡0(modni)，故 𝑐𝑗 ≡𝑚𝑗 ≡0(mod𝑛𝑖)cj≡mj≡0(modni)．又有 𝑐𝑖 ≡𝑚𝑖 ⋅(𝑚−1𝑖mod𝑛𝑖) ≡1(mod𝑛𝑖)ci≡mi⋅(mi−1modni)≡1(modni)，所以我们有：
𝑥≡𝑘∑𝑗=1𝑎𝑗𝑐𝑗(mod𝑛𝑖)≡𝑎𝑖𝑐𝑖(mod𝑛𝑖)≡𝑎𝑖⋅𝑚𝑖⋅(𝑚−1𝑖mod𝑛𝑖)(mod𝑛𝑖)≡𝑎𝑖(mod𝑛𝑖)x≡∑j=1kajcj(modni)≡aici(modni)≡ai⋅mi⋅(mi−1modni)(modni)≡ai(modni)
即对于任意 𝑖 =1,2,⋯,𝑘i=1,2,⋯,k，上面算法得到的 𝑥x 总是满足 𝑥 ≡𝑎𝑖(mod𝑛𝑖)x≡ai(modni)，即证明了解同余方程组的算法的正确性．
因为我们没有对输入的 𝑎𝑖ai 作特殊限制，所以任何一组输入 {𝑎𝑖}{ai} 都对应一个解 𝑥x．另外，若 𝑥 ≠𝑦x≠y，则总存在 𝑖i 使得 𝑥x 和 𝑦y 在模 𝑛𝑖ni 下不同余．故系数列表 {𝑎𝑖}{ai} 与解 𝑥x 之间是一一映射关系，方程组总是有唯一解．
解释
下面演示 CRT 如何解「物不知数」问题．
- 𝑛 =3 ×5 ×7 =105n=3×5×7=105；
- 三人同行 七十 希：𝑛1 =3,𝑚1 =𝑛/𝑛1 =35,𝑚−11 ≡2(mod3)n1=3,m1=n/n1=35,m1−1≡2(mod3)，故 𝑐1 =35 ×2 =70c1=35×2=70；
- 五树梅花 廿一 支：𝑛2 =5,𝑚2 =𝑛/𝑛2 =21,𝑚−12 ≡1(mod5)n2=5,m2=n/n2=21,m2−1≡1(mod5)，故 𝑐2 =21 ×1 =21c2=21×1=21；
- 七子团圆正 半月 ：𝑛3 =7,𝑚3 =𝑛/𝑛3 =15,𝑚−13 ≡1(mod7)n3=7,m3=n/n3=15,m3−1≡1(mod7)，故 𝑐3 =15 ×1 =15c3=15×1=15；
- 所以方程组的唯一解为 𝑥 ≡2 ×70 +3 ×21 +2 ×15 ≡233 ≡23(mod105)x≡2×70+3×21+2×15≡233≡23(mod105)．（除 百零五 便得知）
Garner 算法
CRT 的另一个用途是用一组比较小的质数表示一个大的整数．
例如，若 𝑎a 满足如下线性方程组，且 𝑎 <∏𝑘𝑖=1𝑝𝑖a<∏i=1kpi（其中 𝑝𝑖pi 为质数）：
⎧{ { {⎨{ { {⎩𝑎≡𝑎1(mod𝑝1)𝑎≡𝑎2(mod𝑝2)⋮𝑎≡𝑎𝑘(mod𝑝𝑘){a≡a1(modp1)a≡a2(modp2)⋮a≡ak(modpk)
我们可以用以下形式的式子（称作 𝑎a 的混合基数表示）表示 𝑎a：
𝑎=𝑥1+𝑥2𝑝1+𝑥3𝑝1𝑝2+…+𝑥𝑘𝑝1…𝑝𝑘−1a=x1+x2p1+x3p1p2+…+xkp1…pk−1
Garner 算法 将用来计算系数 𝑥1,…,𝑥𝑘x1,…,xk．
令 𝑟𝑖𝑗rij 为 𝑝𝑖pi 在模 𝑝𝑗pj 意义下的 逆：
𝑝𝑖⋅𝑟𝑖,𝑗≡1(mod𝑝𝑗)pi⋅ri,j≡1(modpj)
把 𝑎a 代入我们得到的第一个方程：
𝑎1≡𝑥1(mod𝑝1)a1≡x1(modp1)
代入第二个方程得出：
𝑎2≡𝑥1+𝑥2𝑝1(mod𝑝2)a2≡x1+x2p1(modp2)
方程两边减 𝑥1x1，除 𝑝1p1 后得
𝑎2−𝑥1≡𝑥2𝑝1(mod𝑝2)(𝑎2−𝑥1)𝑟1,2≡𝑥2(mod𝑝2)𝑥2≡(𝑎2−𝑥1)𝑟1,2(mod𝑝2)a2−x1≡x2p1(modp2)(a2−x1)r1,2≡x2(modp2)x2≡(a2−x1)r1,2(modp2)
类似地，我们可以得到：
𝑥𝑘=(…((𝑎𝑘−𝑥1)𝑟1,𝑘−𝑥2)𝑟2,𝑘)−…)𝑟𝑘−1,𝑘mod𝑝𝑘xk=(…((ak−x1)r1,k−x2)r2,k)−…)rk−1,kmodpk实现
C++Python
---|---
---|---
该算法的时间复杂度为 𝑂(𝑘2)O(k2)．实际上 Garner 算法并不要求模数为质数，只要求模数两两互质，我们有如下伪代码：
𝐂𝐡𝐢𝐧𝐞𝐬𝐞 𝐑𝐞𝐦𝐚𝐢𝐧𝐝𝐞𝐫 𝐀𝐥𝐠𝐨𝐫𝐢𝐭𝐡𝐦 cra(𝐯,𝐦):𝐈𝐧𝐩𝐮𝐭: 𝐦=(𝑚0,𝑚1,…,𝑚𝑛−1), 𝑚𝑖∈ℤ+∧gcd(𝑚𝑖,𝑚𝑗)=1 for all 𝑖≠𝑗,𝐯=(𝑣0,…,𝑣𝑛−1) where 𝑣𝑖=𝑥mod𝑚𝑖.𝐎𝐮𝐭𝐩𝐮𝐭: 𝑥mod∏𝑛−1𝑖=0𝑚𝑖.1𝐟𝐨𝐫 𝑖 from 1 to (𝑛−1) 𝐝𝐨2𝐶𝑖←(∏𝑖−1𝑗=0𝑚𝑗)−1mod𝑚𝑖3𝑥←𝑣04𝐟𝐨𝐫 𝑖 from 1 to (𝑛−1) 𝐝𝐨5𝑢←(𝑣𝑖−𝑥)⋅𝐶𝑖mod𝑚𝑖6𝑥←𝑥+𝑢∏𝑖−1𝑗=0𝑚𝑗7𝐫𝐞𝐭𝐮𝐫𝐧 (𝑥)Chinese Remainder Algorithm cra(v,m):Input: m=(m0,m1,…,mn−1), mi∈Z+∧gcd(mi,mj)=1 for all i≠j,v=(v0,…,vn−1) where vi=xmodmi.Output: xmod∏i=0n−1mi.1for i from 1 to (n−1) do2Ci←(∏j=0i−1mj)−1modmi3x←v04for i from 1 to (n−1) do5u←(vi−x)⋅Cimodmi6x←x+u∏j=0i−1mj7return (x)
可以发现在第六行中的计算过程对应上述混合基数的表示．
应用
某些计数问题或数论问题出于加长代码、增加难度、或者是一些其他原因，给出的模数：不是质数 ！
但是对其质因数分解会发现它没有平方因子，也就是该模数是由一些不重复的质数相乘得到．
那么我们可以分别对这些模数进行计算，最后用 CRT 合并答案．
下面这道题就是一个不错的例子．
[洛谷 P2480 [SDOI2010] 古代猪文](https://www.luogu.com.cn/problem/P2480)
给出 𝐺,𝑛G,n（1 ≤𝐺,𝑛 ≤1091≤G,n≤109），求：
𝐺∑𝑘∣𝑛(𝑛𝑘)mod999 911 659G∑k∣n(nk)mod999 911 659
首先，当 𝐺 =999 911 659G=999 911 659 时，所求显然为 00．
否则，根据 欧拉定理，可知所求为：
𝐺∑𝑘∣𝑛(𝑛𝑘)mod999 911 658mod999 911 659G∑k∣n(nk)mod999 911 658mod999 911 659
现在考虑如何计算：
∑𝑘∣𝑛(𝑛𝑘)mod999 911 658∑k∣n(nk)mod999 911 658
因为 999 911 658999 911 658 不是质数，无法保证 ∀𝑥 ∈[1,999 911 657]∀x∈[1,999 911 657]，𝑥x 都有逆元存在，上面这个式子我们无法直接计算．
注意到 999 911 658 =2 ×3 ×4679 ×35617999 911 658=2×3×4679×35617，其中每个质因子的最高次数均为一，我们可以考虑分别求出 ∑𝑘∣𝑛(𝑛𝑘)∑k∣n(nk) 在模 22，33，46794679，3561735617 这几个质数下的结果，最后用中国剩余定理来合并答案．
也就是说，我们实际上要求下面一个线性方程组的解：
⎧{ { {⎨{ { {⎩𝑥≡𝑎1(mod2)𝑥≡𝑎2(mod3)𝑥≡𝑎3(mod4679)𝑥≡𝑎4(mod35617){x≡a1(mod2)x≡a2(mod3)x≡a3(mod4679)x≡a4(mod35617)
而计算一个组合数对较小的质数取模后的结果，可以利用 卢卡斯定理．
扩展：模数不互质的情况
两个方程
设两个方程分别是 𝑥 ≡𝑎1(mod𝑚1)x≡a1(modm1)、𝑥 ≡𝑎2(mod𝑚2)x≡a2(modm2)；
将它们转化为不定方程：𝑥 =𝑚1𝑝 +𝑎1 =𝑚2𝑞 +𝑎2x=m1p+a1=m2q+a2，其中 𝑝,𝑞p,q 是整数，则有 𝑚1𝑝 −𝑚2𝑞 =𝑎2 −𝑎1m1p−m2q=a2−a1．
由 裴蜀定理，当 𝑎2 −𝑎1a2−a1 不能被 gcd(𝑚1,𝑚2)gcd(m1,m2) 整除时，无解；
其他情况下，可以通过 扩展欧几里得算法 解出来一组可行解 (𝑝,𝑞)(p,q)；
则原来的两方程组成的模方程组的解为 𝑥 ≡𝑏(mod𝑀)x≡b(modM)，其中 𝑏 =𝑚1𝑝 +𝑎1b=m1p+a1，𝑀 =lcm(𝑚1,𝑚2)M=lcm(m1,m2)．
多个方程
用上面的方法两两合并即可．
习题
本页面部分内容译自博文Китайская теорема об остатках 与其英文翻译版 Chinese Remainder Theorem．其中俄文版版权协议为 Public Domain + Leave a Link；英文版版权协议为 CC-BY-SA 4.0．
本页面最近更新： 2026/1/7 08:56:54，更新历史 发现错误？想一起完善？在 GitHub 上编辑此页！ 本页面贡献者：Ir1d, StudyingFather, Yanjun-Zhao, Enter-tainer, H-J-Granger, sshwy, Chrogeek, countercurrent-time, NachtgeistW, Xeonacid, Early0v0, Great-designer, MegaOwIer, Tiphereth-A, 383494, AngelKitty, CCXXXI, cjsoft, diauweb, ezoixx130, GekkaSaori, Henry-ZHR, iamtwz, Konano, kzoacn, LovelyBuggies, Makkiy, mgt, minghu6, P-Y-Y, PotassiumWings, SamZhangQingChuan, stevebraveman, Suyun514, Unnamed2964, weiyong1024, ChungZH, GavinZhengOI, Gesrua, Haohu Shen, HeRaNO, hly1204, ImpleLee, ksyx, kxccc, little-cindy, lychees, Menci, namasikanam, ouuan, Peanut-Tang, Phemon, renbaoshuo, shawlleyw, SukkaW, xyf007 本页面的全部内容在CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用