跳转至

# 中国剩余定理

## 引入

> 「物不知数」问题：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二．问物几何？

即求满足以下条件的整数：除以 3 3 余 2 2，除以 5 5 余 3 3，除以 7 7 余 2 2．

该问题最早见于《孙子算经》中，并有该问题的具体解法．宋朝数学家秦九韶于 1247 年《数书九章》卷一、二《大衍类》对「物不知数」问题做出了完整系统的解答．上面具体问题的解答口诀由明朝数学家程大位在《算法统宗》中给出：

> 三人同行七十希，五树梅花廿一支，七子团圆正半月，除百零五便得知．

2 ×7 0 +3 ×2 1 +2 ×1 5 =2 3 3 =2 ×1 0 5 +2 3 2×70+3×21+2×15=233=2×105+23，故答案为 2 3 23．

## 定义

中国剩余定理 (Chinese Remainder Theorem, CRT) 可求解如下形式的一元线性同余方程组（其中 𝑛 1,𝑛 2,⋯,𝑛 𝑘 n 1,n 2,⋯,n k 两两互质）：

⎧{ { {⎨{ { {⎩𝑥≡𝑎 1(m o d 𝑛 1)𝑥≡𝑎 2(m o d 𝑛 2)⋮𝑥≡𝑎 𝑘(m o d 𝑛 𝑘){x≡a 1(mod n 1)x≡a 2(mod n 2)⋮x≡a k(mod n k)

上面的「物不知数」问题就是一元线性同余方程组的一个实例．

## 过程

1. 计算所有模数的积 𝑛 n；
2. 对于第 𝑖 i 个方程：
   1. 计算 𝑚 𝑖 =𝑛 𝑛 𝑖 m i=n n i；
   2. 计算 𝑚 𝑖 m i 在模 𝑛 𝑖 n i 意义下的 逆元 𝑚−1 𝑖 m i−1；
   3. 计算 𝑐 𝑖 =𝑚 𝑖 𝑚−1 𝑖 c i=m i m i−1（不要对 𝑛 𝑖 n i 取模）．
3. 方程组在模 𝑛 n 意义下的唯一解为：𝑥 =∑𝑘 𝑖=1 𝑎 𝑖 𝑐 𝑖(m o d 𝑛)x=∑i=1 k a i c i(mod n)．

## 实现

C++Python

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    LL CRT(int k, LL* a, LL* r) {
      LL n = 1, ans = 0;
      for (int i = 1; i <= k; i++) n = n * r[i];
      for (int i = 1; i <= k; i++) {
        LL m = n / r[i], b, y;
        exgcd(m, r[i], b, y);  // b * m mod r[i] = 1
        ans = (ans + a[i] * m * b % n) % n;
      }
      return (ans % n + n) % n;
    }

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    def CRT(k, a, r):
        n = 1
        ans = 0
        for i in range(1, k + 1):
            n = n * r[i]
        for i in range(1, k + 1):
            m = n // r[i]
            b = y = 0
            exgcd(m, r[i], b, y)  # b * m mod r[i] = 1
            ans = (ans + a[i] * m * b % n) % n
        return (ans % n + n) % n

## 证明

我们需要证明上面算法计算所得的 𝑥 x 对于任意 𝑖 =1,2,⋯,𝑘 i=1,2,⋯,k 满足 𝑥 ≡𝑎 𝑖(m o d 𝑛 𝑖)x≡a i(mod n i)．

当 𝑖 ≠𝑗 i≠j 时，有 𝑚 𝑗 ≡0(m o d 𝑛 𝑖)m j≡0(mod n i)，故 𝑐 𝑗 ≡𝑚 𝑗 ≡0(m o d 𝑛 𝑖)c j≡m j≡0(mod n i)．又有 𝑐 𝑖 ≡𝑚 𝑖 ⋅(𝑚−1 𝑖 m o d 𝑛 𝑖) ≡1(m o d 𝑛 𝑖)c i≡m i⋅(m i−1 mod n i)≡1(mod n i)，所以我们有：

𝑥≡𝑘∑𝑗=1 𝑎 𝑗 𝑐 𝑗(m o d 𝑛 𝑖)≡𝑎 𝑖 𝑐 𝑖(m o d 𝑛 𝑖)≡𝑎 𝑖⋅𝑚 𝑖⋅(𝑚−1 𝑖 m o d 𝑛 𝑖)(m o d 𝑛 𝑖)≡𝑎 𝑖(m o d 𝑛 𝑖)x≡∑j=1 k a j c j(mod n i)≡a i c i(mod n i)≡a i⋅m i⋅(m i−1 mod n i)(mod n i)≡a i(mod n i)

即对于任意 𝑖 =1,2,⋯,𝑘 i=1,2,⋯,k，上面算法得到的 𝑥 x 总是满足 𝑥 ≡𝑎 𝑖(m o d 𝑛 𝑖)x≡a i(mod n i)，即证明了解同余方程组的算法的正确性．

因为我们没有对输入的 𝑎 𝑖 a i 作特殊限制，所以任何一组输入 {𝑎 𝑖}{a i} 都对应一个解 𝑥 x．另外，若 𝑥 ≠𝑦 x≠y，则总存在 𝑖 i 使得 𝑥 x 和 𝑦 y 在模 𝑛 𝑖 n i 下不同余．故系数列表 {𝑎 𝑖}{a i} 与解 𝑥 x 之间是一一映射关系，方程组总是有唯一解．

## 解释

下面演示 CRT 如何解「物不知数」问题．

1. 𝑛 =3 ×5 ×7 =1 0 5 n=3×5×7=105；
2. 三人同行 七十 希：𝑛 1 =3,𝑚 1 =𝑛/𝑛 1 =3 5,𝑚−1 1 ≡2(m o d 3)n 1=3,m 1=n/n 1=35,m 1−1≡2(mod 3)，故 𝑐 1 =3 5 ×2 =7 0 c 1=35×2=70；
3. 五树梅花 廿一 支：𝑛 2 =5,𝑚 2 =𝑛/𝑛 2 =2 1,𝑚−1 2 ≡1(m o d 5)n 2=5,m 2=n/n 2=21,m 2−1≡1(mod 5)，故 𝑐 2 =2 1 ×1 =2 1 c 2=21×1=21；
4. 七子团圆正 半月：𝑛 3 =7,𝑚 3 =𝑛/𝑛 3 =1 5,𝑚−1 3 ≡1(m o d 7)n 3=7,m 3=n/n 3=15,m 3−1≡1(mod 7)，故 𝑐 3 =1 5 ×1 =1 5 c 3=15×1=15；
5. 所以方程组的唯一解为 𝑥 ≡2 ×7 0 +3 ×2 1 +2 ×1 5 ≡2 3 3 ≡2 3(m o d 1 0 5)x≡2×70+3×21+2×15≡233≡23(mod 105)．（除 百零五 便得知）

## Garner 算法

CRT 的另一个用途是用一组比较小的质数表示一个大的整数．

例如，若 𝑎 a 满足如下线性方程组，且 𝑎 <∏𝑘 𝑖=1 𝑝 𝑖 a<∏i=1 k p i（其中 𝑝 𝑖 p i 为质数）：

⎧{ { {⎨{ { {⎩𝑎≡𝑎 1(m o d 𝑝 1)𝑎≡𝑎 2(m o d 𝑝 2)⋮𝑎≡𝑎 𝑘(m o d 𝑝 𝑘){a≡a 1(mod p 1)a≡a 2(mod p 2)⋮a≡a k(mod p k)

我们可以用以下形式的式子（称作 𝑎 a 的混合基数表示）表示 𝑎 a：

𝑎=𝑥 1+𝑥 2 𝑝 1+𝑥 3 𝑝 1 𝑝 2+…+𝑥 𝑘 𝑝 1…𝑝 𝑘−1 a=x 1+x 2 p 1+x 3 p 1 p 2+…+x k p 1…p k−1

Garner 算法 将用来计算系数 𝑥 1,…,𝑥 𝑘 x 1,…,x k．

令 𝑟 𝑖 𝑗 r i j 为 𝑝 𝑖 p i 在模 𝑝 𝑗 p j 意义下的 逆：

𝑝 𝑖⋅𝑟 𝑖,𝑗≡1(m o d 𝑝 𝑗)p i⋅r i,j≡1(mod p j)

把 𝑎 a 代入我们得到的第一个方程：

𝑎 1≡𝑥 1(m o d 𝑝 1)a 1≡x 1(mod p 1)

代入第二个方程得出：

𝑎 2≡𝑥 1+𝑥 2 𝑝 1(m o d 𝑝 2)a 2≡x 1+x 2 p 1(mod p 2)

方程两边减 𝑥 1 x 1，除 𝑝 1 p 1 后得

𝑎 2−𝑥 1≡𝑥 2 𝑝 1(m o d 𝑝 2)(𝑎 2−𝑥 1)𝑟 1,2≡𝑥 2(m o d 𝑝 2)𝑥 2≡(𝑎 2−𝑥 1)𝑟 1,2(m o d 𝑝 2)a 2−x 1≡x 2 p 1(mod p 2)(a 2−x 1)r 1,2≡x 2(mod p 2)x 2≡(a 2−x 1)r 1,2(mod p 2)

类似地，我们可以得到：

𝑥 𝑘=(…((𝑎 𝑘−𝑥 1)𝑟 1,𝑘−𝑥 2)𝑟 2,𝑘)−…)𝑟 𝑘−1,𝑘 m o d 𝑝 𝑘 x k=(…((a k−x 1)r 1,k−x 2)r 2,k)−…)r k−1,k mod p k
实现
C++Python

    1
    2
    3
    4
    5
    6
    7
    8
    for (int i = 0; i < k; ++i) {
      x[i] = a[i];
      for (int j = 0; j < i; ++j) {
        x[i] = r[j][i] * (x[i] - x[j]);
        x[i] = x[i] % p[i];
        if (x[i] < 0) x[i] += p[i];
      }
    }

    1
    2
    3
    4
    5
    6
    7
    for i in range(0, k):
        x[i] = a[i]
        for j in range(0, i):
            x[i] = r[j][i] * (x[i] - x[j])
            x[i] = x[i] % p[i]
            if x[i] < 0:
                x[i] = x[i] + p[i]

该算法的时间复杂度为 𝑂(𝑘 2)O(k 2)．实际上 Garner 算法并不要求模数为质数，只要求模数两两互质，我们有如下伪代码：

𝐂 𝐡 𝐢 𝐧 𝐞 𝐬 𝐞 𝐑 𝐞 𝐦 𝐚 𝐢 𝐧 𝐝 𝐞 𝐫 𝐀 𝐥 𝐠 𝐨 𝐫 𝐢 𝐭 𝐡 𝐦 c r a⁡(𝐯,𝐦):𝐈 𝐧 𝐩 𝐮 𝐭: 𝐦=(𝑚 0,𝑚 1,…,𝑚 𝑛−1), 𝑚 𝑖∈ℤ+∧g c d(𝑚 𝑖,𝑚 𝑗)=1 f o r a l l 𝑖≠𝑗,𝐯=(𝑣 0,…,𝑣 𝑛−1) w h e r e 𝑣 𝑖=𝑥 m o d 𝑚 𝑖.𝐎 𝐮 𝐭 𝐩 𝐮 𝐭: 𝑥 m o d∏𝑛−1 𝑖=0 𝑚 𝑖.1 𝐟 𝐨 𝐫 𝑖 f r o m 1 t o (𝑛−1) 𝐝 𝐨 2 𝐶 𝑖←(∏𝑖−1 𝑗=0 𝑚 𝑗)−1 m o d 𝑚 𝑖 3 𝑥←𝑣 0 4 𝐟 𝐨 𝐫 𝑖 f r o m 1 t o (𝑛−1) 𝐝 𝐨 5 𝑢←(𝑣 𝑖−𝑥)⋅𝐶 𝑖 m o d 𝑚 𝑖 6 𝑥←𝑥+𝑢∏𝑖−1 𝑗=0 𝑚 𝑗 7 𝐫 𝐞 𝐭 𝐮 𝐫 𝐧 (𝑥)Chinese Remainder Algorithm cra⁡(v,m):Input: m=(m 0,m 1,…,m n−1), m i∈Z+∧gcd(m i,m j)=1 for all i≠j,v=(v 0,…,v n−1) where v i=x mod m i.Output: x mod∏i=0 n−1 m i.1 for i from 1 to (n−1) do 2 C i←(∏j=0 i−1 m j)−1 mod m i 3 x←v 0 4 for i from 1 to (n−1) do 5 u←(v i−x)⋅C i mod m i 6 x←x+u∏j=0 i−1 m j 7 return (x)

可以发现在第六行中的计算过程对应上述混合基数的表示．

## 应用

某些计数问题或数论问题出于加长代码、增加难度、或者是一些其他原因，给出的模数：不是质数！

但是对其质因数分解会发现它没有平方因子，也就是该模数是由一些不重复的质数相乘得到．

那么我们可以分别对这些模数进行计算，最后用 CRT 合并答案．

下面这道题就是一个不错的例子．

洛谷 P2480 [SDOI2010] 古代猪文

给出 𝐺,𝑛 G,n（1 ≤𝐺,𝑛 ≤1 0 9 1≤G,n≤10 9），求：

𝐺∑𝑘∣𝑛(𝑛 𝑘)m o d 9 9 9 9 1 1 6 5 9 G∑k∣n(n k)mod 999 911 659

首先，当 𝐺 =9 9 9 9 1 1 6 5 9 G=999 911 659 时，所求显然为 0 0．

否则，根据 欧拉定理，可知所求为：

𝐺∑𝑘∣𝑛(𝑛 𝑘)m o d 9 9 9 9 1 1 6 5 8 m o d 9 9 9 9 1 1 6 5 9 G∑k∣n(n k)mod 999 911 658 mod 999 911 659

现在考虑如何计算：

∑𝑘∣𝑛(𝑛 𝑘)m o d 9 9 9 9 1 1 6 5 8∑k∣n(n k)mod 999 911 658

因为 9 9 9 9 1 1 6 5 8 999 911 658 不是质数，无法保证 ∀𝑥 ∈[1,9 9 9 9 1 1 6 5 7]∀x∈[1,999 911 657]，𝑥 x 都有逆元存在，上面这个式子我们无法直接计算．

注意到 9 9 9 9 1 1 6 5 8 =2 ×3 ×4 6 7 9 ×3 5 6 1 7 999 911 658=2×3×4679×35617，其中每个质因子的最高次数均为一，我们可以考虑分别求出 ∑𝑘∣𝑛(𝑛 𝑘)∑k∣n(n k) 在模 2 2，3 3，4 6 7 9 4679，3 5 6 1 7 35617 这几个质数下的结果，最后用中国剩余定理来合并答案．

也就是说，我们实际上要求下面一个线性方程组的解：

⎧{ { {⎨{ { {⎩𝑥≡𝑎 1(m o d 2)𝑥≡𝑎 2(m o d 3)𝑥≡𝑎 3(m o d 4 6 7 9)𝑥≡𝑎 4(m o d 3 5 6 1 7){x≡a 1(mod 2)x≡a 2(mod 3)x≡a 3(mod 4679)x≡a 4(mod 35617)

而计算一个组合数对较小的质数取模后的结果，可以利用 卢卡斯定理．

## 扩展：模数不互质的情况

### 两个方程

设两个方程分别是 𝑥 ≡𝑎 1(m o d 𝑚 1)x≡a 1(mod m 1)、𝑥 ≡𝑎 2(m o d 𝑚 2)x≡a 2(mod m 2)；

将它们转化为不定方程：𝑥 =𝑚 1 𝑝 +𝑎 1 =𝑚 2 𝑞 +𝑎 2 x=m 1 p+a 1=m 2 q+a 2，其中 𝑝,𝑞 p,q 是整数，则有 𝑚 1 𝑝 −𝑚 2 𝑞 =𝑎 2 −𝑎 1 m 1 p−m 2 q=a 2−a 1．

由 裴蜀定理，当 𝑎 2 −𝑎 1 a 2−a 1 不能被 g c d(𝑚 1,𝑚 2)gcd(m 1,m 2) 整除时，无解；

其他情况下，可以通过 扩展欧几里得算法 解出来一组可行解 (𝑝,𝑞)(p,q)；

则原来的两方程组成的模方程组的解为 𝑥 ≡𝑏(m o d 𝑀)x≡b(mod M)，其中 𝑏 =𝑚 1 𝑝 +𝑎 1 b=m 1 p+a 1，𝑀 =l c m(𝑚 1,𝑚 2)M=lcm(m 1,m 2)．

### 多个方程

用上面的方法两两合并即可．

## 习题

- 【模板】中国剩余定理（CRT）/曹冲养猪
- 【模板】扩展中国剩余定理
- 「NOI2018」屠龙勇士

- 「TJOI2009」猜数字

  本页面部分内容译自博文 Китайская теорема об остатках 与其英文翻译版 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 协议之条款下提供，附加条款亦可能应用