猜数游戏
三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五便得知。
———（明）程大位《算法统宗》
我第一次对“中国剩余定理”产生兴趣，只是因为这个名字在一众定理里面十分独特。包括其解法“秦九韶大衍求一术”，也是一个非常典雅、非常能激起中学生无穷想象的神圣名字。这个神圣的东西出自南北朝的《孙子算经》，不是春秋时期吴国带兵打仗的那个孙子，是南北朝的一个数学家孙老师，“鸡兔同笼”这个问题也是出自这本书。
我们如今放学了、下班了热衷于玩推理解谜、密室逃脱，而古代的人就买一本孙老师的算经，每天耕完地、打完仗（能活着回来的话）就回家翻一下，做一下，算一下兔子有多少只、军队有多少人。
回到题头这首诗，如同现代人用一些稀奇古怪的口诀背诵要点一样，题头的这首诗就是明代解谜高手玩孙老师的这个游戏后总结的一个口诀，现在我们也来玩玩。
假如你现在穿越回到南北朝时期，被军官当作奸细抓了起来，军官说如果你知道军营里有多少人就说明你是汉人，放你走，否则你就是胡人派过来的的细作。但是你只能看到三件事：
- 守卫排成三排剩两个人；
- 排成五排剩三个人；
- 排成七排又剩两个人。
你会怎么猜？
大多数人的第一反应大概都是：一个一个试。 试 13，不对；试 17，不对；试 19，不对……一直试下去，直到某个数同时满足这三条。
当然可以这么做，只是这么做有些不可能。你试三次估计就脑袋搬家了。且不说如果有很多解都满足这三个条件呢，世界上有无数个数除以 3 余 2，又有无数个数除以 5 余 3……
这个问题就是出来刁难你的。但是经过你脑海中的演算，虽然条件看起来碎碎的，好像不止一个解，最后却真的只会落到一个整数上。不是一堆，不是模模糊糊的区间，好像就是一个明确的数。
不妨真的试一下。
从 1 开始找，满足“除以 3 余 2”的数是 2、5、8、11、14、17、20、23、26、29、32……
再看这些数里，满足“除以 5 余 3”的有哪些：8、23、38……
再看它们里，满足“除以 7 余 2”的数：23。
就是 23。
这个答案有一种喜悦的不确定感，你终于找到了，但你怎么知道后面没有了。
（作者：Cmglee，维基共享资源，CC BY-SA 4.0）
不要一个一个试
因为我们太习惯把整数看成“一个接一个”的东西了。
1、2、3、4、5……就像楼梯，一级一级往上走。于是当我们遇到“除以 3 余 2，除以 5 余 3，除以 7 余 2”这种条件时，直觉也会说：那就从头排查吧。
可这种做法的问题很明显：楼梯太长了。
你要求的是一个数同时满足多个条件，而不是某一个条件。条件一多，直接试就会变成一种很朴素但很费力的劳动。尤其当数字大起来的时候，这种劳动会立刻变得不体面。你试一百个数，可能都还没碰到正确答案的一根边角。试数字这件事从一开始就带着一种“全局搜索”的味道。它默认你要在一条长长的线里找目标。
这件事很像算日期。
今天是星期五，过 1 天就是星期六，过 2 天就是星期天，过 100 天星期几？往后推去吧，推一百天，一天一天的数去吧，数错了就从头开始数。
余数在旁边伤心的看着你。
余数无法帮你知道过100天是星期几，但它可以告诉你这个整数处在某种循环系统里的哪一个位置。
余数如何帮助我们？
我很喜欢模运算这个概念，一个数除另一个数然后取余数。它有一种非常日常的气质。
回到刚刚的星期问题上，
今天是星期五，过 7 天还是星期五，过 14 天还是星期五，过 15 天就余了一天，往后退推一天就星期六了，过了 20 天，三七二十一，还差一天那就往前推一天，那就星期四。100天，14个整除余2，星期日。所以，星期这个系统本质上就是循环的。你不需要知道过去了多少天，只要知道“除以 7 的余数”就够了。
再比如时钟。
现在是 3 点，过 12 小时还是 3 点。时钟不是一条无限延伸的直线，而是一个圆。时间在它上面走着走着，最后总会绕回来。想知道时间，看一眼钟，我相信任何一个正常的人类都不会第一眼看到12，然后开始往后数，看过了多少个小时，以此来判断现在几点。而是一眼就锁定针现在指在钟面上的哪个位置，哪怕钟面上面没有标数字也是这样的。
日历也一样。一个月 30 天、31 天、28 天，甚至闰年。你以为时间在往前走，其实它一直在带着某些模式反复出现。
数学把这件事抽象出来，叫“模”，一个“模”就是一个循环。比如“除以 7 取余数”，我们称为“模7（$mod$ $7$）”，这就是在星期的世界里说话；“除以 12 取余数”，就是在时钟的世界里说话。一天24个小时，那么第二天的凌晨一点对我们熬夜人来说是今天的25点，其实“25点 ≡ 1点 (mod 24)”。
于是，一个数不再只是它自己。它在不同的模里，会显出不同的侧面。
这很像一个人。
在家里、在学校、在朋友面前、在心爱的人面前，呈现出来的样子都不完全一样。单靠一个瞬间，你不一定看得准一个人。但如果你看见了很多侧面，就会更接近真相。
一个整数在模 3 里是什么样，在模 5 里是什么样，在模 7 里是什么样，这些“余数”，把它固定了下来。
从这里引入数论
高斯说：
数学是科学的皇后，而数论是数学的皇后。
数论其实就是研究整数。
整数这个世界，虽然看上去低调，甚至有点朴素，但它内部的秩序深到不可思议。很多现代数学、现代计算机科学、现代密码学，最后都要回到整数，回到余数，回到除法的残影。 很奇妙。
模运算是数论最重要的工具之一。微积分有导数，线性代数有矩阵，几何有坐标。
而数论里最常见的工具之一就是模。不同的数字，在模运算的世界里，被看作同一个数字，正如25点 ≡ 1点 (mod 24)一样，星期八 ≡ 星期一 (mod 7)，这种等价关系，就叫做同余（Congruence）。
graph TD M["数学"] M --> N["数论"] M --> FF["微积分"] N --> A["整数"] A --> B["整除"] B --> B1["最大公约数（GCD）"] B --> B2["最小公倍数（LCM）"] A --> C["质数"] C --> C1["质因数分解"] B --> D["同余（模运算）"] D --> E["欧几里得算法"] E --> E1["扩展欧几里得算法"] D --> F["欧拉定理"] D --> G["费马小定理"] D --> H["中国剩余定理"] E1 --> H H --> I["现代密码学"] I --> I1["RSA"] I --> I2["ECC（椭圆曲线密码）"] I --> I3["数字签名"] I3 --> I4["区块链"]
回到谜题，终于出现公式了
上面说了这么多，完全就是铺垫，其实就是让大家知道这些英文字母、三个横杠杠代表什么，写到这里还不写公式，会有一点对不起现代数学。
所以现在我们让公式出现，但让它慢慢出现。
设我们要寻找一个整数 (x)，它满足：
$$x \equiv a_1 \pmod{m_1}$$$$x \equiv a_2 \pmod{m_2}$$$$\cdots$$$$x \equiv a_n \pmod{m_n}$$就是说，$x$除以$m_1$余$a_1$，除以$m_2$余$a_2$，……除以$m_n$余$a_n$。
中国剩余定理告诉我们：如果这些模数$m_1,m_2,\dots,m_n$两两互素，那么这个同余方程组一定有解，而且在模
$$ M = m_1,m_2,\cdots,m_n $$意义下，这个解是唯一的。
啥是“两两互素”？
我们需要这些模数尽量独立，因为我们要定位到具体的数，如果你拿 6 和 9 来做模数，它们就都含有共同因子 3，这时余数之间会产生重叠，这不胡闹吗。
所以我们除的数字任意间不能有共同的因子。比如 3 和 5 互素（没有组成对方的因子），3 和 7 互素，5 和 7 也互素。它们之间没有共同的因子，不会浪费一个定位的机会。
所以中国剩余定理并不是对所有模数都无条件成立，它有一个清楚的边界。数学最迷人的地方之一就在这里：它从不随便吹牛。它总是把条件写得明明白白。
为什么解是“唯一”的？
注意这个“唯一”不是说只有一个整数永远满足，而是说在模 (M) 的意义下唯一。
也就是说，可能有无穷多个整数都满足同一组余数条件，但它们彼此相差 (M) 的倍数。对于模 (M) 的世界来说，它们其实是同一个答案，即同余。
这也是我很喜欢模运算的原因。它把“无穷多个相似对象”压缩成一个清晰的类别。像海面上的波纹，虽然每一圈都在动，但你知道它们属于同一种节律。
构造思想是什么？
数学不是光给你结论，而是给你一条搭桥的路。 设
$$ M_i = \frac{M}{m_i} $$也就是把总积 (M) 除以第 (i) 个模数之后得到的那一块。 因为$M_i$和$m_i$互素，所以可以找到一个整数$y_i$，使得
$$ M_i y_i \equiv 1 \pmod{m_i} $$意思是：我们希望 ($M_i$) 在模 ($m_i$) 的世界里变成 1，只要再乘一个合适的数 ($y_i$) 就可以。 这时候，解可以写成：
$$ x \equiv \sum_{i=1}^n a_i M_i y_i \pmod{M} $$其实逻辑很朴素。因为当你把 ($M_i$) 放到模 ($m_j$) 的世界里时，除了 ($j=i$) 的那一项，其他项都会被 ($m_j$) 整除，变成 0。只有对应那一项会留下来，刚好等于 ($a_i$)。
这是一种非常漂亮的“定向”结构：每一项只对自己的模数说话，对别人的模数沉默。
扩展欧几里得算法是什么？
你会发现，上面的构造里需要找到 ($y_i$)，也就是求一个乘法逆元（即找一个数，让它和原来的数相乘以后，结果等于 1。如$2\times\frac12=1$，$\frac12$就是 2 的乘法逆元）。怎么找？ 这时候扩展欧几里得算法就登场了。 简单说，欧几里得算法本来是用来求最大公约数的。扩展版则进一步告诉我们：如果两个数互素，就能把 1 写成它们的整数组合。也就是说，能找到整数 $u,v$，使得
$$ au + bv = 1 $$一旦能把 1 表出来，逆元也就跟着出现了。 欧几里得算法有一种很好的气质：老老实实地做除法，做着做着，结构就出来了。
现代本质：把 23 真的算出来
现在我们来做前面那道题：
$$ x \equiv 2 \pmod{3} $$$$ x \equiv 3 \pmod{5} $$$$ x \equiv 2 \pmod{7} $$模数分别是 3、5、7，它们两两互素，所以可以用中国剩余定理。 先算总积：
$$ M = 3 \times 5 \times 7 = 105 $$然后分别算：
$$ M_1 = \frac{105}{3} = 35,\quad M_2 = \frac{105}{5} = 21,\quad M_3 = \frac{105}{7} = 15 $$接下来，我们要让每个$M_i$在对应模数下变成 1。 对$m_1=3$ 我们要找$y_1$，使得：
$$ 35y_1 \equiv 1 \pmod{3} $$先看 35 除以 3 的余数是 2，所以实际上是在求：
$$ 2y_1 \equiv 1 \pmod{3} $$试一下，$y_1=2$时，$2\times 2=4\equiv 1 \pmod{3}$。 所以$y_1=2$。 对$m_2=5$ 我们要找$y_2$，使得：
$$ 21y_2 \equiv 1 \pmod{5} $$21 除以 5 余 1，所以：
$$ y_2 \equiv 1 \pmod{5} $$最简单取$y_2=1$。 对$m_3=7$ 我们要找$y_3$，使得：
$$ 15y_3 \equiv 1 \pmod{7} $$15 除以 7 余 1，所以：
$$ y_3 \equiv 1 \pmod{7} $$最简单取$y_3=1$。 于是公式给出：
$$ x \equiv 2 \cdot 35 \cdot 2 + 3 \cdot 21 \cdot 1 + 2 \cdot 15 \cdot 1 \pmod{105} $$逐项算：
$$ 2 \cdot 35 \cdot 2 = 140 $$$$ 3 \cdot 21 = 63 $$$$ 2 \cdot 15 = 30 $$相加得： $ 140+63+30=233 $ 再对 105 取模：
$$ 233 \equiv 23 \pmod{105} $$所以解是：
$$ x \equiv 23 \pmod{105} $$也就是说，23、128、233、338……都满足这组余数条件，但在模 105 的意义下，它们都是同一个答案。
flowchart LR A["x ≡ 2 (mod 3)"] B["x ≡ 3 (mod 5)"] C["x ≡ 2 (mod 7)"] A --> D["35 × 逆元 × 2"] B --> E["21 × 逆元 × 3"] C --> F["15 × 逆元 × 2"] D --> G["相加"] E --> G F --> G G --> H["x = 23"]
古人之法：回到开头诗
现在再让我们看回开头那首口诀诗，这是程大位总结秦九韶的解法：
三人同行七十稀。
把除以 3 得到的余数乘以 70。
因为$70≡35=5\times7$同时满足而$70\equiv1\pmod3$, $70\equiv0\pmod5$, $70\equiv0\pmod7$。
这意味着，乘上 70 以后，它在模 3 的世界里保持原来的余数，在模 5 和模 7 的世界里却完全"消失"了。
五树梅花廿一支。
“廿一"就是二十一。
把除以 5 的余数乘以 21。
因为$21=3\times7$，并且$21\equiv1\pmod5$，同时$21\equiv0\pmod3, 21\equiv0\pmod7$。所以，它只会影响模 5 的条件，而不会干扰另外两个条件。
七子团圆正半月。
古人说"半月”，就是十五。
把除以 7 得到的余数乘以 15。
因为$15=3\times5$，满足$15\equiv1\pmod7$，同时$15\equiv0\pmod3,15\equiv0\pmod5$。
它同样只负责自己的那一个条件。于是，我们便得到了三个十分神奇的数字：
| 系数 | 模 3 | 模 5 | 模 7 |
|---|---|---|---|
| 70 | 1 | 0 | 0 |
| 21 | 0 | 1 | 0 |
| 15 | 0 | 0 | 1 |
- 70 只负责模 3；
- 21 只负责模 5；
- 15 只负责模 7。
无论它们怎样相加，都不会互相影响。
除百零五便得知。
这里的"百零五"，正是$105=3\times5\times7$。
将前三项全部相加之后，再不断减去 105（也就是今天所说的对 105 取模），直到得到最小的正整数，便是最终答案。
看到这里，你或许会觉得，这和前面介绍的现代方法似乎有些不同。我们刚刚学到的公式里，还需要计算一个"乘法逆元"，可这首口诀怎么没有描述？
原因就在于，这是一道极其幸运的特例。
对于模数 (3、5、7) 而言，
$$ 70\equiv1\pmod3, $$$$ 21\equiv1\pmod5, $$$$ 15\equiv1\pmod7. $$三个系数天生就已经是各自的乘法逆元，因此根本不需要额外计算。
而对于一般的中国剩余定理问题，这种幸运通常不会发生。例如模数换成 (4、9、11) 或 (5、7、11) 时，仅仅使用$M_i=\frac{M}{m_i}$已经不能满足条件，还必须再乘上一个对应的乘法逆元，这也就是现代教材中的通用公式：
$$ x\equiv\sum a_iM_iN_i\pmod M, $$其中 ($N_i$) 就是 ($M_i$) 在对应模数下的乘法逆元。
换句话说，这首口诀，并不是另一种完全不同的算法，而是现代中国剩余定理公式在 模数恰好为 3、5、7 时的一个优美解法，如“勾股定理”中的勾三、股四、弦五一样，都是古早中国数学家发现的定理中的特例。
一千年前的古人不知道什么叫"乘法逆元"，也不会写下现代的同余公式。但他们已经发现了这三个神奇的数字——70、21、15，并把它们浓缩进了一首二十八字的口诀。直到今天，当我们用现代代数重新审视它时，也能发现这就是中国剩余定理最核心的思想。
互联网如何应用
当你打开一个 HTTPS 网站时
例如进入本站：
你的浏览器和我的服务器之间会进行一次握手。
其中服务器需要证明：
“我就是 hpu.edu.kg。”
它的方法就是：
用自己的 RSA 私钥 对一段数据进行数字签名。
问题来了。
RSA 的私钥运算非常慢。
因为它需要计算类似
$$ m^d \bmod n $$其中
- (n=pq)
- (p,q) 都是几百位的大质数。
直接计算一次这样的幂运算，需要处理上千位的大整数。
中国剩余定理如何加速？
RSA 私钥拥有一个别人没有的信息：
服务器知道
$$ n=pq $$因此，它不用直接算
$$ m^d\bmod n $$而是可以拆成两个更小的问题。
先计算
$$ m^d\bmod p $$再计算
$$ m^d\bmod q $$这两个模数只有原来的一半长度。
计算速度快得多。
最后，再利用中国剩余定理：
把两个答案重新拼回
$$ m^d\bmod n $$整个过程就是：
flowchart LR A["RSA 私钥运算
m^d mod n"] A --> B["拆分"] B --> C["模 p 运算"] B --> D["模 q 运算"] C --> E["CRT 重组"] D --> E E --> F["最终签名/解密结果"] F --> G["HTTPS / SSH / VPN"]
这就是 CRT 在 RSA 中最著名的应用。
为什么会快很多？
假设：
RSA 是 2048 位。
那么
- p 大约 1024 位
- q 大约 1024 位
现代乘法复杂度并不是线性的。
整数长度减半，
计算量通常能下降到原来的四分之一左右。
两个四分之一加起来
约等于
原来的二分之一。
再考虑快速幂等算法，
实际中：
CRT-RSA 通常比直接 RSA 私钥运算快约 3～4 倍。
因此几乎所有 RSA 实现都会使用 CRT。
如果不使用 CRT，
服务器性能会下降很多。
所以它影响了什么？
几乎所有使用 RSA 私钥的地方。
例如：
- HTTPS 网站证书
- SSH 登录
- VPN 身份认证
- 软件数字签名
- PDF 数字签名
- 邮件加密（S/MIME）
只要服务器需要做 RSA 私钥运算，
CRT 基本都会参与。
那区块链呢？
提到区块链，大家肯定首先想起加密货币，比特币（Bitcoin）、以太坊（Ethereum）等，但这些都几乎不涉及到CRT。因为它们主要采用的是ECDSA（椭圆曲线数字签名），并不是 RSA，所以CRT 不是核心。
但是区块链技术依赖数字签名，而数字签名有很多实现。
flowchart LR A["中国剩余定理"] A --> B["RSA"] B --> C["数字签名"] C --> D["HTTPS"] C --> E["软件签名"] C --> F["身份认证"] C -. "现代区块链更多采用\n椭圆曲线数字签名" .-> G["区块链"]
结语
你惊险地答上了军官的问题，你证明了你的身份，成功回到了现代。
当你需要证明自己的身份时，服务器会利用私钥进行数字签名，而中国剩余定理能够把一次庞大的模运算拆成两个更小的计算，再将结果重新合并。在几乎所有 RSA 实现中，这种称为 CRT-RSA 的优化都已成为标准做法，使私钥运算速度提升约 3～4 倍。也正因如此，一个诞生于两千年前的数学定理，今天仍然默默工作在 HTTPS、SSH、VPN、软件签名等现代互联网基础设施的底层。我们能够通过 VPN 访问到Google、Youtube、ChatGPT，也得感谢这些写在草纸上的古老算式。
再看《孙子算经》里的那道题，它其实不是“古人会算”。人类很早就已经意识到，某些问题不必正面硬碰。你可以绕一圈，从另一个角度看它。你可以把一个不可见的整体，拆成一组可见的局部；你也可以从局部重新把整体拼回来。
我不知道人类从开始记录日期的那一天起，到今天一共过去了多少天。这个数字太大，但如果我将这个数除以 7 得余数，我知道今天是星期几；将它除以 12 得余数，我知道它对应哪一个月份；将它除以 365 得余数，我知道它在一年中的第几天。
