中国剩余定理

历史渊源与古典表述

从 "物不知数" 到 "大衍求一术"

中国剩余定理的起源可明确追溯至南北朝时期的数学典籍《孙子算经》（约公元 4 世纪），其中记载的 "物不知数" 问题堪称中国古代数学的标志性问题："今有物不知其数，三三数之余二，五五数之余三，七七数之余二，问物几何？"。其解答 "二十三" 的得出，蕴含了中国剩余定理的基本思想，但《孙子算经》仅给出了具体问题的算法，未形成系统理论。

这一问题的一般化解法直到南宋时期才由数学家秦九韶在《数书九章》（1247 年）中完成，他将其发展为 "大衍总数术"，其中核心的 "大衍求一术" 正是求解同余式组的通用算法。秦九韶的贡献在于：不仅解决了模数两两互素的情形，还提出了将非互素模数转化为互素情形的方法，其算法的严密性令现代数学家惊叹，德国数学史家康托曾称秦九韶为 "最幸运的天才"。这一成就比西方同类结果早约 550 年，直到 1801 年高斯在《算术探究》中才独立给出严格的数学证明。

古典解法的现代诠释

《孙子算经》中 "物不知数" 问题的解法以四句歌诀传世："三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知"。其现代数学表述为：

70 是 5 与 7 的公倍数且模 3 余 1，即

21 是 3 与 7 的公倍数且模 5 余 1，即

15 是 3 与 5 的公倍数且模 7 余 1，即

105 是 3、5、7 的最小公倍数，即

问题的通解为 ，其中减去 105 的倍数以得到最小正整数解。这一解法已包含中国剩余定理的核心要素：构造满足特定余数条件的基础解，再通过线性组合获得通解。

数学定义与符号体系

标准形式与存在唯一性

中国剩余定理的现代数学表述如下：设 是两两互素的正整数，即对任意 ，有 。则对任意整数 ，同余方程组

存在唯一解 ，其中 为所有模数的乘积。这一解的唯一性意味着在区间 内存在且仅存在一个解，所有解可表示为 （ ）。

关键概念界定

为严格表述定理，需明确以下概念：

模数互素：模数集合 中任意两个数的最大公约数为 1，这是定理成立的必要条件。若模数不互素，则方程组可能无解或有多个解。

衍母与衍数：秦九韶在 "大衍总数术" 中称为 "衍母"，称 为 "衍数"，即排除第 个模数后的乘积。

乘率：满足 的整数 ，即 模 的乘法逆元，秦九韶称之为 "乘率"，其求法正是 "大衍求一术" 的核心。

多种推导方法的系统分析

构造性证明：从局部解到全局解

构造性证明是理解中国剩余定理最直观的方法，其核心思想是将复杂方程组分解为简单子问题，再通过线性组合获得通解。具体步骤如下：

计算衍母 ： ，表示解的周期。

计算衍数 ： ，显然 与 互素（因 不含 的素因子）。

求乘率 ：解同余式 ，由 知逆元 存在。

构造局部解 ： ，易验证 且 （ ）。

组合全局解： ，则 对所有 成立，最小正解为 。

以 "物不知数" 问题为例（ , ）：

求乘率： ；同理

局部解： , ,

全局解： , 最小解

数学归纳法证明：从二元到多元

数学归纳法提供了从简单到复杂的严格证明路径，先证明二元情形，再推广至多元。

基础步骤（ ）：考虑方程组

其中 。令 ，代入第二式得 。因 与 互素，存在唯一解 ，故 存在唯一解 。

归纳步骤：假设 个方程的方程组有唯一解 ，则 个方程的方程组等价于

其中 是前 个方程的解。因 与 互素（由归纳假设及模数两两互素），由二元情形知此方程组有唯一解 。

代数结构视角：环同构与剩余类

从近世代数角度，中国剩余定理揭示了整数环与剩余类环直积之间的同构关系。定义映射

定理断言 是环同构。证明如下：

单射：若 ，则 对所有 ，因 两两互素，故 ，即 。

满射：对任意 ，由构造性证明知存在 使 。

同态： 且 显然成立。

这种同构关系意味着模 的算术运算可分解为模 的独立运算，这正是现代计算机中余数数制（RNS）的理论基础。

大衍求一术：乘率的构造性求法

秦九韶的 "大衍求一术" 是中国剩余定理的精髓，其核心是求解乘率 ，即同余式 的解。秦九韶在《数书九章》中详述了这一算法，其步骤与现代辗转相除法异曲同工：

初始化："置奇右上，定居右下，立天元一于左上"。即令右上为 （"奇数"），右下为 （"定数"），左上为 1（"天元一"），左下为 0。

辗转相除："以右上除右下，对得商数与左上一相生，入左下"。即计算 ，更新左下为 ，然后交换右上与右下、左上与左下，重复此过程直至右上为 1。

结果提取："须使右上末后奇一而止，乃验左上所得，以为乘率"。即当右上变为 1 时，左上的数即为乘率 。

实例：求解 （即 "物不知数" 中 ）：

初始：右上 ，右下 ，左上 = 1，左下 = 0

第一步： ，左下 = ，交换后右上 = 1，左上 = 1，左下 = 1

右上已为 1，故乘率 （验证： ）

这一算法展现了中国古代数学的机械化特征，与现代程序设计中的循环结构高度相似，其蕴含的构造性思想对数学机械化具有重要启发。

非互素模数情形的推广

中国剩余定理要求模数两两互素，当此条件不满足时，方程组可能无解或有解但不唯一。设 ，则方程组有解的充要条件是对所有 ， 。此时可通过以下步骤求解：

合并方程组：将同余式两两合并，例如合并 和 ：

令 ，代入第二式得

记 ，若 则无解；否则两边同除以 得

因 与 互素，存在唯一解 ，故合并后方程为

迭代合并：重复上述过程，直至得到单个同余式或判断无解

实例：解方程组

，检查 能否被 2 整除：是

合并得 ，代入第二式：

故 ，解为

现代应用与理论延伸

密码学中的核心工具

中国剩余定理在现代密码学中具有不可替代的地位：

RSA 加密：利用 CRT 可将大整数模运算分解为小模数运算，加速解密过程。例如解密私钥运算 ，可先计算 和 （其中 ），再通过 CRT 合并结果，运算效率提升约 4 倍。

全同态加密：RNS - BFV 等方案基于 CRT 将密文表示为多个小模数余数，实现同态运算的并行化，大幅提升计算效率。

群签名：基于 CRT 构建的群签名方案可实现匿名性与可追踪性，每个成员的私钥对应不同模数的余数，通过 CRT 组合生成签名。

计算机科学与编码理论

余数数制（RNS）：利用 CRT 将大整数表示为一组小模数余数，使加减法和乘法可并行计算，广泛应用于高性能计算和数字信号处理。例如一个 32 位整数可表示为模 的余数，所有运算在小模数下独立进行。

分布式计算：在分布式系统中，CRT 可用于合并不同节点的局部计算结果，例如分布式数据库中的查询优化。

数学理论的拓展

多项式环上的 CRT：若 是两两互素的多项式，则对任意多项式 ，存在唯一多项式 满足 ，且 。这一结果是拉格朗日插值法的理论基础。

代数几何：在概形理论中，CRT 推广为 "平展上同调" 中的 excision 性质，是研究代数簇局部 - 整体性质的重要工具。

结语：古今智慧的对话

从《孙子算经》的 "物不知数" 到现代密码学的全同态加密，中国剩余定理跨越两千年的时空，展现了数学思想的永恒魅力。秦九韶的 "大衍求一术" 不仅是算法机械化的典范，其 "分而治之" 的核心思想更成为解决复杂问题的普适方法。在数字化时代，这一古老定理通过余数数制、分布式计算等形式，继续为科技进步提供数学支撑。真正的数学智慧不仅能够解决特定问题，更能跨越时代，持续为人类知识体系贡献新的视角与方法。