一、 千年谜题：物不知数
中国剩余定理（Chinese Remainder Theorem）是中国古代数学最璀璨的明珠之一，在西方数学史上被尊称为“中国剩余定理”，在国内则常被称为“孙子定理”。
这个问题最早出现在公元 5 世纪（南北朝时期）的数学著作《孙子算经》卷下第二十六题，原文脍炙人口：
翻译成现代白话文，就是一个充满趣味的数字谜题：
有一堆东西，不知道具体有多少个。
如果 $3$ 个 $3$ 个地数，最后余 $2$ 个；
如果 $5$ 个 $5$ 个地数，最后余 $3$ 个；
如果 $7$ 个 $7$ 个地数，最后余 $2$ 个。
请问这堆东西至少有多少个？
如果用现代数学符号（同余式）来表示，我们要求解整数 $x$，满足以下方程组：
$$
\begin{cases}
x \equiv 2 \pmod 3 \\
x \equiv 3 \pmod 5 \\
x \equiv 2 \pmod 7
\end{cases}
$$
《孙子算经》虽然给出了答案 23，但真正系统性解决这个问题并将其上升为理论的，是南宋数学家秦九韶。他在《数书九章》中提出的“大衍求一术”，不仅完美解决了此类问题，更比西方同类成果（高斯）早了 500 多年。
二、 古人的智慧：大衍求一术（构造法）
秦九韶的方法非常巧妙，我们可以将其称为“构造法”。他的核心思想可以概括为：“分而治之，各个击破”。
既然我们要同时满足除以 $3$、$5$、$7$ 的余数条件，那能不能先找到三个“特殊数”，每个数只负责满足一个条件，而不破坏其他条件呢？
第一步：寻找“公倍数”与“特殊数”
我们需要找三个基准数：
- 针对模 3：它是 $5$ 和 $7$ 的公倍数（能被 $5, 7$ 整除），但除以 $3$ 余 $1$。
- 针对模 5：它是 $3$ 和 $7$ 的公倍数（能被 $3, 7$ 整除），但除以 $5$ 余 $1$。
- 针对模 7：它是 $3$ 和 $5$ 的公倍数（能被 $3, 5$ 整除），但除以 $7$ 余 $1$。
这在数学上叫做寻找“模逆元”。我们可以列一个表来寻找这三个数：
| 目标模数 | 公倍数 | 1倍 | 2倍 | 3倍 | 最终的“特殊数” |
|---|---|---|---|---|---|
| 模 3余1 | [5,7]的倍数 | 35 | 70 | 105 | 70 |
| 模 5余1 | [3,7]的倍数 | 21 | 42 | 63 | 21 |
| 模 7余1 | [3,5]的倍数 | 15 | 30 | 45 | 15 |
第二步：组合答案
找到了这三个“特殊数”（$70, 21, 15$），我们就可以根据题目要求的余数（$2, 3, 2$）进行组合了：
70 是 $5,7$ 的倍数，除以 $3$ 余 $1$。题目要求除以 $3$ 余 2，所以取 $70 \times 2$。
21 是 $3,7$ 的倍数，除以 $5$ 余 $1$。题目要求除以 $5$ 余 3，所以取 $21 \times 3$。
15 是 $3,5$ 的倍数，除以 $7$ 余 $1$。题目要求除以 $7$ 余 2，所以取 $15 \times 2$。
将它们加起来：
$$x = 70 \times 2 + 21 \times 3 + 15 \times 2 = 140 + 63 + 30 = 233$$
第三步：求最小正整数解
$233$ 虽然符合条件，但它太大了。因为 $3, 5, 7$ 的最小公倍数是 $105$，我们在 $233$ 的基础上减去 $105$ 的倍数，余数性质是不会变的。
$$233 – 105 \times 2 = 233 – 210 = 23$$
所以，23 就是最小的答案。
明代数学家程大位在《算法统宗》中将这一过程编成了朗朗上口的《孙子歌》：
五树梅花廿一枝。
七子团圆正半月，
除百零五便得知。
其中，“七十稀”指模3用的特殊数70，“廿一枝”指模5用的21，“正半月”指15（模7用的），“除百零五”则是指最后要减去公倍数。
三、 通用的利器：逐级满足法（迭代法）
虽然中国剩余定理公式优美，但它有一个局限：要求除数（模数）两两互质。如果除数不互质，或者方程组数量很多，找“特殊数”会非常麻烦。
著名数学家陈景润在《初等数论Ⅰ》中详细讲解了一种更通用、更适合计算机思维的方法——逐级满足法（也叫代入法或迭代法）。
这个方法的逻辑是：不要试图一步登天，而是两两合并，逐级通关。
题目：
$$
\begin{cases}
a \equiv 2 \pmod 3 \quad \dots \text{①} \\
a \equiv 3 \pmod 5 \quad \dots \text{②} \\
a \equiv 2 \pmod 7 \quad \dots \text{③}
\end{cases}
$$
第一步：合并方程 ① 和 ②
由方程 ①，我们可以把 $a$ 写成代数式：
$$a = 3x + 2$$
将它代入方程 ②：
$$3x + 2 \equiv 3 \pmod 5$$
两边同时减去 2：
$$3x \equiv 1 \pmod 5$$
这里我们需要求 $x$ 的值。观察可知，当 $x=2$ 时，$3 \times 2 = 6$，除以 $5$ 余 $1$。
所以，$x \equiv 2 \pmod 5$。
写成代数式即：$x = 5y + 2$。
把 $x$ 代回 $a$ 的表达式：
$$a = 3(5y + 2) + 2 = 15y + 6 + 2 = 15y + 8$$
阶段成果：此时，$a = 15y + 8$。这个式子意味着：只要 $a$ 是 $15$ 的倍数加 $8$，就能同时满足前两个方程！（你可以验证：8 除以 3 余 2，除以 5 余 3，完全正确）。
第二步：合并结果与方程 ③
现在我们有了新方程组：
$$
\begin{cases}
a \equiv 8 \pmod{15} \\
a \equiv 2 \pmod 7
\end{cases}
$$
将 $a = 15y + 8$ 代入方程 ③：
$$15y + 8 \equiv 2 \pmod 7$$
利用同余性质简化（因为 $15 \div 7 \dots 1$，所以 $15y \equiv 1y$；$8 \div 7 \dots 1$，所以 $8 \equiv 1$）：
$$y + 1 \equiv 2 \pmod 7$$
两边减 1：
$$y \equiv 1 \pmod 7$$
这意味着 $y$ 的最小正整数解是 $1$。
第三步：得出最终结果
把 $y=1$ 代回 $a$ 的表达式：
$$a = 15 \times 1 + 8 = 23$$
如果要求通解，则加上 $15$ 和 $7$ 的公倍数 $105$：
$$a = 105k + 23$$
逐级满足法的优势：
- 逻辑清晰：就像解方程组一样，消元、代入。
- 适应性强：即使除数不互质（例如除以 4 余 1，除以 6 余 3），只要有解，用这个方法一定能算出来；如果算出矛盾（例如 $2y = 3$），则说明无解。
四、 深度思考：为什么有时会“无解”？
在《孙子算经》的原题中，$3, 5, 7$ 都是质数，它们两两互质，所以一定有解。但在实际应用中，如果模数不互质，可能会出现冲突。
例如：一个数除以 $4$ 余 $1$，除以 $6$ 余 $2$。
$$
\begin{cases}
x = 4k + 1 \quad (\text{奇数}) \\
x = 6m + 2 \quad (\text{偶数})
\end{cases}
$$
一个数不可能既是奇数又是偶数，所以此题无解。
有解的充要条件：
对于方程组 $x \equiv a_1 \pmod {m_1}$ 和 $x \equiv a_2 \pmod {m_2}$，当且仅当 $a_1 – a_2$ 能被 $\gcd(m_1, m_2)$（最大公约数）整除时，方程组才有解。
这正是“逐级满足法”的强大之处，它能在计算过程中自动发现这些矛盾，而不需要预先背诵复杂的定理条件。
结语
从秦九韶的“大衍求一术”到现代的代数推导，中国剩余定理跨越了千年。它不仅是古代农历推算、工程计算的基础，更是现代计算机密码学（如RSA加密）的核心基石之一。
无论是古人的歌诀，还是现代的方程，数学的魅力就在于殊途同归——用最简洁的逻辑，描述最万千的世界。
暂无评论内容