中国剩余定理：从《孙子算经》到现代研究

2026-11-09

一、历史渊源 #

中国剩余定理的英文名称是 Chinese Remainder Theorem，简称CRT，中文也称“孙子定理”或“中国余数定理”。它研究的问题是：知道一个整数分别除以几个数的余数，能否确定这个整数，以及怎样把它算出来。从应用来说，这一定理可以用于计算不同天文周期和纪日周期在某个时刻处于什么位置。

《孙子算经》卷下收录了著名的“物不知数”问题：一堆物品，三个一组剩两个，五个一组剩三个，七个一组剩两个，求物品数量。书中给出的答案是23，并记载了使用70、21、15计算的方法。南宋数学家秦九韶在1247年的《数书九章》中，对这类问题给出了更系统、一般的算法。其中的“大衍求一术”解决了一个关键步骤：寻找某个整数的倍数，使它除以另一个指定整数恰好余1。这也就是现代数学语言里模逆元的计算问题。

二、古文解释 #

2.1 原文及词义 #

《孙子算经》卷下第二十六题记载如下。保留繁体字，标点按现代阅读习惯整理：

今有物，不知其數。三三數之，賸二；五五數之，賸三；七七數之，賸二。問物幾何？
答曰：二十三。
術曰：三三數之，賸二，置一百四十；五五數之，賸三，置六十三；七七數之，賸二，置三十。并之，得二百三十三。以二百一十減之，即得。
凡三三數之，賸一，則置七十；五五數之，賸一，則置二十一；七七數之，賸一，則置十五。一百六以上，以一百五減之，即得。

其中，“数之”的“数”读作“shǔ”，指计数；“三三数之”指每三个分为一组；“賸”就是“剩”；“置”指把数列出来用于计算；“并之”指相加。“一百五”是105，“一百六”是106。

这套方法可以理解为：先找出三笔数，让每一笔负责一个余数要求，同时能被另外两个除数整除，再把三笔数相加。

第一笔负责“除以3余2”。为了让它除以5和7都余0，先从35的倍数中找一个除以3余1的数：

35\div3=11\text{ 余 }2,\qquad 70\div3=23\text{ 余 }1。

70符合要求。要让除以3的余数变成2，就取两份70：

2\times70=140。

140除以3余2，同时能被5和7整除。因此原文说：“三三数之，剩二，置一百四十。”

第二笔负责“除以5余3”。它应当能被3和7整除，所以从21的倍数中找。21除以5恰好余1，取三份即可：

3\times21=63。

63除以5余3，同时能被3和7整除。因此原文说：“五五数之，剩三，置六十三。”

第三笔负责“除以7余2”。它应当能被3和5整除，所以从15的倍数中找。15除以7恰好余1，取两份即可：

2\times15=30。

30除以7余2，同时能被3和5整除。因此原文说：“七七数之，剩二，置三十。”

三笔数的作用如下：

三笔数	除以3的余数	除以5的余数	除以7的余数
140	2	0	0
63	0	3	0
30	0	0	2
合计233	2	3	2

以除以3为例，63和30都能整除，只有140留下2。因此三笔数相加以后，除以3仍然余2。除以5和7时同理。于是：

140+63+30=233

已经是一个满足全部要求的答案。

那“一百六以上，以一百五減之”是什么意思呢？

因为

105=3\times5\times7，

每减去105，都相当于拿走一批能被3、5、7分别分完的物品，三个余数保持不变。因此：

233\longrightarrow128\longrightarrow23。

原文“以二百一十减之”就是一次减去两个105：

233-210=23。

23满足题目要求：

23=3\times7+2=5\times4+3=7\times3+2。

仅靠不断减去105，可以找到这一串解中的最小正数。

三、基本结论 #

中国剩余定理的基本结论是：当几个除数两两互质时，无论指定怎样的合法余数，都存在同时满足全部条件的整数；在从0到“这些除数的乘积减1”的范围内，恰好有一个。

在贯穿例子中，三个除数的乘积是105，因此三个余数能在0到104之间唯一确定23。放宽范围以后，满足条件的正整数依次为：

23,\ 128,\ 233,\ 338,\ldots

四、正式表达 #

4.1 同余符号 #

记号

x\equiv a\pmod m

表示整数差值 $x-a$ 能被 $m$ 整除，也就是 $x$ 与 $a$ 除以 $m$ 的余数相同。当 $0\le a<m$ 时，可以直接读作“ $x$ 除以 $m$ 余 $a$ ”。

4.2 中国剩余定理 #

设 $n$ 为正整数， $m_1,m_2,\ldots,m_n>1$ 是两两互质的整数， $a_1,a_2,\ldots,a_n$ 为任意整数。则同余方程组

\begin{cases} x\equiv a_1\pmod{m_1},\\ x\equiv a_2\pmod{m_2},\\ \qquad\vdots\\ x\equiv a_n\pmod{m_n} \end{cases}

有解，并且在模 $M=m_1m_2\cdots m_n$ 的意义下唯一。

如果 $x_0$ 是其中一个整数解，那么全部整数解恰好为

\boxed{x=x_0+kM,\qquad k\in\mathbb Z}。

其中 $\mathbb Z$ 表示整数集合。取 $x_0$ 除以 $M$ 的非负余数，就得到区间 $0\le x<M$ 内的唯一解。

4.3 非两两互质除数时的推广 #

对于任意正整数模数 $m_i>1$ ，上述方程组有解的充要条件是：对任意 $i,j$ ，

\gcd(m_i,m_j)\mid(a_i-a_j)。

这里 $\gcd$ 表示最大公因数，符号“ $\mid$ ”表示整除。这个条件要求：两个除数共有的因数，不能与这两条余数要求产生矛盾。这么说可能有些抽象，还是以例子来说明：

对于4和6两个数存在最大公因数2，它们不互质。如果我们需要求解的方程有如下两种要求，则第一组有解，第二组无解。

第一组，除以4余1，除以6余3。把满足各自条件的正整数列出来，可以发现共同解为：

9,\ 21,\ 33,\ldots

通解可以写作：

x=9+12k,\qquad k\in\mathbb Z

其中12是4和6的最小公倍数。

第二组，除以4余1，除以6余2。因为除以4余1的数，一定是奇数；除以6余2的数，一定是偶数，二者矛盾，所以这种方程无解。

对于这两组方程，第一组的要求余数之差是3-1=2，最大公因数2，则2整除2，不产生矛盾；第二组的要求余数之差是2-1=1，此时最大公因数将不再整除，由此可以推出矛盾，该方程组无解。

在有解时，解在模 $\operatorname{lcm}(m_1,\ldots,m_n)$ 的意义下唯一，其中 $\operatorname{lcm}$ 表示最小公倍数。两两互质时，最小公倍数等于乘积，就回到上一小节的形式。

五、标准证明 #

标准的构造性证明分为两步：先构造一个满足全部条件的整数，再证明任意两个解相差 $M$ 的整数倍。

5.1 前置知识：裴蜀定理 #

裴蜀定理也称“贝祖等式”或“贝祖恒等式”（Bézout’s identity）。

对于不全为0的整数 $a,b$ ，设 $d=\gcd(a,b)$ ，则存在整数 $u,v$ ，使得

au+bv=d。

整数系数 $u,v$ 可以为正、为负或为0。例如：

12\times(-1)+18\times1=6=\gcd(12,18)。

本证明使用其中的互质情形：

\gcd(a,b)=1\quad\Longrightarrow\quad \text{存在整数 }u,v,\text{ 使 }au+bv=1。

例如35和3互质，并且

35\times2+3\times(-23)=1。

移项得到 $70=3\times23+1$ ，说明35确实有一个倍数除以3余1。

5.2 构造解，证明存在性 #

令

M=m_1m_2\cdots m_n,\qquad M_i=\frac{M}{m_i}。

$M_i$ 是除 $m_i$ 外所有模数的乘积，所以它能被其他每个 $m_j$ 整除。由于各模数两两互质，有

\gcd(M_i,m_i)=1。

由裴蜀定理，存在整数 $t_i,s_i$ ，使

M_it_i+m_is_i=1。

于是

M_it_i\equiv1\pmod{m_i}。

令 $e_i=M_it_i$ 。它具有两种性质：

e_i\equiv1\pmod{m_i},\qquad e_i\equiv0\pmod{m_j}\quad(j\ne i)。

这就是古代例子中70、21、15所具有的共同性质：对自己的模数余1，对其他模数余0。

现在构造

\boxed{x_0=\sum_{i=1}^{n}a_ie_i =\sum_{i=1}^{n}a_iM_it_i}。

任选一个模数 $m_k$ 。在这个模数下，所有 $i\ne k$ 的项都余0，只有第 $k$ 项留下，因此

x_0\equiv a_ke_k\equiv a_k\pmod{m_k}。

这对每个 $k$ 都成立，所以 $x_0$ 满足全部方程。解的存在性得证。

5.3 证明唯一性 #

假设 $x$ 和 $y$ 都满足全部方程。对每个 $i$ ，都有

x\equiv a_i\pmod{m_i},\qquad y\equiv a_i\pmod{m_i}。

两式相减得到 $m_i\mid(x-y)$ 。由于各 $m_i$ 两两互质，它们的乘积也整除 $x-y$ ，即

M\mid(x-y)。

因此 $x\equiv y\pmod M$ ，即任意两个解相差 $M$ 的整数倍。反过来，给一个解加上 $M$ 的整数倍，显然仍满足全部方程，所以全部整数解正好为 $x_0+kM$ 。

如果进一步要求 $0\le x,y<M$ ，则 $|x-y|<M$ 。绝对值小于 $M$ 的 $M$ 的整数倍只有0，因此 $x=y$ 。这就证明了该范围内的唯一性。

5.4 对照《孙子算经》的数字 #

在贯穿例子中， $M=105$ ，上述构造为：

模数 $m_i$	$M_i=105/m_i$	选取的 $t_i$	$e_i=M_it_i$	目标余数 $a_i$
3	35	2	70	2
5	21	1	21	3
7	15	1	15	2

由构造公式：

x_0=2\times70+3\times21+2\times15=233。

取233除以105的非负余数，得到23。全部整数解为

\boxed{x=23+105k,\qquad k\in\mathbb Z}。

六、应用场景 #

中国剩余定理提供了一种计算方式：把一个大模数下的问题分成几个较小模数下的问题，分别计算，再恢复结果。它也能把多个周期条件或局部取值条件合成为一个整体解。

6.1 RSA解密和签名加速 #

RSA的模数通常为 $N=pq$ ，其中 $p,q$ 是两个大素数。私钥运算需要计算形如

y=c^d\bmod N

的结果。持有私钥的人知道 $p,q$ ，可以先分别计算结果模 $p$ 和模 $q$ 的余数，再用中国剩余定理恢复 $y\bmod N$ 。两次较小模数下的运算还可以并行执行。

RSA规范明确包含这种计算方式，并给出了相应的私钥参数及组合算法。RFC 8017，第3节及第5节

6.2 剩余数系统与同态加密 #

用一个整数在多个模数下的余数来表示它，这种表示称为剩余数系统（Residue Number System），简称RNS。例如，在0到104之间，23对应模3、5、7的余数三元组为 $(2,3,2)$ 。

余数表示允许分别执行加法和乘法。例如，17对应 $(2,2,3)$ ，将它与23相加时，三个分量分别计算并取余：

(2,3,2)+(2,2,3) \longrightarrow(1,0,5)。

余数 $(1,0,5)$ 在0到104之间对应40，正好是 $23+17$ 。对于大数，这种方式可以把计算分配给多个较小模数下的运算单元。

需要注意，余数运算直接保留的是模 $M$ 的结果。如果希望恢复通常意义下的整数加法或乘法结果，还必须保证结果落在事先约定的唯一恢复范围内，或增加额外的信息。

同态加密允许在密文上进行计算。由于这类系统常常需要大规模模运算，RNS因而成为重要的计算表示。

6.3 多项式插值 #

中国剩余定理可以推广到多项式。多项式 $f(x)$ 除以 $x-a$ 的余数是 $f(a)$ ，所以指定函数值 $f(a_i)=b_i$ ，可以写成

f(x)\equiv b_i\pmod{x-a_i}。

在实数或有理数范围内，当 $a_i$ 互不相同时，这些一次多项式两两互质。于是，多项式版本的中国剩余定理保证：对于 $n$ 个不同位置及其指定值，存在唯一的、次数小于 $n$ 的插值多项式。

例如，对于插值函数的求解问题，要求 $f(1)=2$ 、 $f(2)=5$ ，在次数小于2的多项式中，唯一答案为

f(x)=3x-1。

这是中国剩余定理与拉格朗日插值之间的联系。

6.4 周期条件的合并 #

如果某项活动每3天重复一次，另一项每5天重复一次，指定它们分别处于什么阶段，就会形成关于天数的余数条件。例如，用整数 $t$ 表示从某个起点经过的天数：

t\equiv2\pmod3,\qquad t\equiv3\pmod5。

符合要求的天数为 $t=8+15k$ 。这类计算可以解释周期对齐和历法中的部分问题。

七、研究动态 #

中国剩余定理是优化计算性能的一种常用技术，在理论论证方面因为已经有成熟的基础理论，一般不作为一个独立热点来研究。但是围绕它的推广、计算算法，以及它在同态加密等方向中的应用，仍然有新的研究。

比如，CRYPTO 2025上“Homomorphic Encryption for Large Integers from Nested Residue Number Systems”，研究多层余数表示如何改善大整数同态计算。

中国剩余定理在应用上主要存在以下问题：

一是计算伴随着转换的代价。中国剩余定理可以高效运算，但是需要对数据进行转换再进行计算，如果这种转换在实际系统中的频率非常高，则可能会抵消掉其加速的收益。

二是转换存在信息的损失，仅凭余数无法区分原数。中国剩余定理在对数据进行取余计算后，余数本身失去了原本数据的大小关系。在对数据进行恢复计算时，需要额外的存储或者计算条件，才能准确恢复原有数据。

三是算法正确性不代表实现正确性。RSA可以分别在两个素数下计算，再通过CRT合并。如果其中一路出现特定故障，并输出了未经有效校验的错误签名，攻击者可能获得恢复私钥所需的信息。

例如，ACM CCS 2023的“Keegan Ryan等：《Passive SSH Key Compromise via Lattices》”，研究签名计算发生特定故障时，结合已知填充结构与格方法，在消息信息不完全已知的情况下恢复RSA私钥。

八、知识总结 #

中国剩余定理在数论中的定位，是同余理论的核心定理之一，也是把整数运算与抽象代数连接起来的基础结果。

它的重要作用是把一个合数模数下的问题，分解成若干个互质模数下的问题，并在分别处理后，再把结果合并。

首先，它把最大公因数、裴蜀定理和模逆元连接在一起。各个概念知识关系体系如下：

概念	与中国剩余定理的关系	贯穿例子
最大公因数与互质	判断不同余数条件能否独立指定	3、5、7两两互质
裴蜀定理	保证所需的整数系数存在	$35\times2-3\times23=1$
模逆元	找到“乘上以后余1”的乘数	$35\times2\equiv1\pmod3$ ，所以2是35模3的逆元
扩展欧几里得算法	实际算出这些系数和逆元	用算法求出上面的2和−23
线性丢番图方程	把余数条件改写为整数方程	$x=mu+a=nv+b$ ，得到 $mu-nv=b-a$

其次，它与素因数分解相结合，形成数论中非常常用的解题路线。

例如：

360=2^3\times3^2\times5=8\times9\times5。

8、9、5两两互质。因此，一个模360的同余问题，可以分别放到模8、模9、模5的环境中研究，再通过CRT合并。

数论中常见的路线是：

\text{一般模数的问题} \longrightarrow \text{各个素数幂下的问题} \longrightarrow \text{用CRT合并结果}。

第三，它能用于研究高次同余方程，包括平方根问题。

对于二次同余方程：

x^2\equiv1\pmod{15}。

要求解可以先把“除以15余1”拆成两个条件。

“ $x^2$ 除以15余1”等价于“ $x^2-1$ 能被15整除”。因为 $15=3\times5$ ，而且3与5互质，这又等价于：

\begin{cases} x^2\text{ 除以3余1},\\ x^2\text{ 除以5余1}。 \end{cases}

对于第一个要求，任何整数 $x$ 除以3，只可能余0、1或2。平方后则余0、1和1。所以，要让平方除以3余1，原来的 $x$ 必须满足余1或者余2。

对于第二个要求，任何整数 $x$ 除以5，只可能余0到4。平方后则余0、1和4。所以，要让平方除以5余1，原来的 $x$ 必须满足余1或者余4。

$x$ 除以5的余数	平方计算	$x^2$ 除以5的余数
0	$0^2=0$	0
1	$1^2=1$	1
2	$2^2=4$	4
3	$3^2=9$	4
4	$4^2=16$	1

合并一下发现，除以3有两种余数选择，除以5也有两种，所以共有四种组合。

组合	对 $x$ 的要求	0到14之间的答案
第一种	除以3余1，除以5余1	1
第二种	除以3余1，除以5余4	4
第三种	除以3余2，除以5余1	11
第四种	除以3余2，除以5余4	14

所以， $x^2$ 除以15余1的全部解是：

\boxed{x\equiv1、4、11、14\pmod{15}}。

第四，它解释了欧拉函数为什么具有“互质乘法性”。

欧拉函数 $\varphi(n)$ 表示1到 $n$ 中，与 $n$ 互质的整数数量。例如：

\varphi(3)=2,\qquad\varphi(5)=4。

一个数与15互质，等价于它既不被3整除，也不被5整除。因此：

模3的余数有2种选择：1、2；
模5的余数有4种选择：1、2、3、4。

CRT保证每一组选择，恰好对应一个模15的数。于是：

\varphi(15)=2\times4=8。

推广后得到：

\boxed{\gcd(m,n)=1 \quad\Rightarrow\quad \varphi(mn)=\varphi(m)\varphi(n)}。

这就是欧拉函数的互质乘法性。

第五，在抽象代数中，CRT表达的是整个运算结构的分解。

对于：

x\bmod15 \quad\longleftrightarrow\quad (x\bmod3,\ x\bmod5)。

数学上进一步拓展写成：

\boxed{\mathbb Z/15\mathbb Z \cong \mathbb Z/3\mathbb Z\times\mathbb Z/5\mathbb Z}。

其中：

$\mathbb Z/15\mathbb Z$ ：模15的余数及其加法、乘法；
右侧：模3和模5两套运算组成的配对系统；
$\cong$ ：两边在保持运算的意义下具有相同结构，叫作“同构”。

这就是所谓的环同构。这里“环”可以先理解为一套可以进行加法、减法和乘法的数学结构。CRT因此也是关于模整数环的结构定理。