历史渊源：从“物不知数”说起
中国剩余定理（Chinese Remainder Theorem, CRT）是中国古代数学留给世界的宝贵遗产之一。其起源可追溯至南北朝时期（公元425-519年）的数学著作《孙子算经》。书中记载了一道著名的趣题——“物不知数”：
“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”
这道题的意思是：有一个未知数，除以3余2，除以5余3，除以7余2，求这个数是多少？《孙子算经》给出了简捷的算法口诀：“三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。”
历史发展时间轴
《孙子算经》成书，首次提出“物不知数”问题及其解法，这是中国剩余定理的最早雏形。
秦九韶在《数书九章》中系统总结了求解一次同余方程组的方法，称为“大衍求一术”，将解法一般化，并严格证明了其正确性。这是世界数学史上的重大贡献，比西方早了500多年。
德国数学家卡尔·弗里德里希·高斯在《算术研究》中正式提出了同余理论，并给出了现代形式的中国剩余定理证明，使其成为数论的核心定理之一。
随着计算机科学的发展，中国剩余定理在密码学、编码理论和分布式计算中展现出巨大的实用价值，成为现代信息安全的重要基石。
定理定义与数学表述
中国剩余定理（CRT）是数论中的一个重要定理，它阐述了如何求解一个由多个模线性同余方程组成的方程组。该定理指出，如果模数两两互质，那么该方程组在模它们乘积的意义下存在唯一解。
1. 形式化描述
设 m1, m2, ..., mk 是两两互质的正整数，即对于任意 i ≠ j，都有 gcd(mi, mj) = 1。对于任意整数 a1, a2, ..., ak，同余方程组：
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
...
x ≡ ak (mod mk)
在模 M = m1 × m2 × ... × mk 的意义下存在唯一解。
2. 核心概念解析
- 同余（Congruence）：若整数
a和b除以正整数m的余数相同，则称a和b模m同余，记作a ≡ b (mod m)。 - 互质（Coprime）：两个整数的最大公约数为1，则称它们互质。这是CRT成立的必要条件。
- 模逆元（Modular Inverse）：若
a x ≡ 1 (mod m)，则称x为a模m的逆元。求解逆元通常使用扩展欧几里得算法。
算法详解：大衍求一术与现代步骤
求解中国剩余定理问题，既可以使用古代秦九韶的“大衍求一术”，也可以使用现代通用的构造性证明方法。以下是现代标准求解步骤：
计算总模数 M
首先，计算所有模数 mi 的乘积，记为 M。
M = m1 × m2 × ... × mk
注意：此步骤要求所有 mi 两两互质。
计算中间变量 Mi
对于每个方程 i，计算 Mi = M / mi。即总模数除以当前方程的模数。
例如，若有三个模数 m1, m2, m3，则：
M1 = M / m1 = m2 × m3M2 = M / m2 = m1 × m3M3 = M / m3 = m1 × m2
求解模逆元 Yi
对于每个 i，寻找整数 Yi，使得：
Mi × Yi ≡ 1 (mod mi)
Yi 即为 Mi 模 mi 的乘法逆元。由于 gcd(Mi, mi) = 1，逆元一定存在。可以使用扩展欧几里得算法高效求解。
合成最终解 x
最终解 x 可以通过以下公式计算：
x = (Σ (ai × Mi × Yi)) mod M
其中 ai 是原方程组中的余数。计算结果 x 即为满足所有同余方程的最小非负整数解。
Python 代码实现示例
def extended_gcd(a, b):
if a == 0:
return b, 0, 1
else:
g, y, x = extended_gcd(b % a, a)
return g, x - (b // a) y, y
def modinv(a, m):
g, x, y = extended_gcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return (x % m + m) % m
def chinese_remainder_theorem(remainders, moduli):
# 计算总模数 M
M = 1
for m in moduli:
M = m
x = 0
for i in range(len(remainders)):
M_i = M // moduli[i]
Y_i = modinv(M_i, moduli[i])
x += remainders[i] M_i Y_i
return x % M
示例：x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
remainders = [2, 3, 2]
moduli = [3, 5, 7]
print("解为:", chinese_remainder_theorem(remainders, moduli))经典案例：孙子算经“物不知数”详解
让我们用上述算法重新解决《孙子算经》中的经典问题：
问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
| 步骤 | 计算内容 | 具体数值 | 说明 |
|---|---|---|---|
| 1 | 定义参数 | a=[2,3,2], m=[3,5,7] | 余数与模数 |
| 2 | 计算 M | M = 3 × 5 × 7 = 105 | 总模数 |
| 3 | 计算 M1, M2, M3 | 35, 21, 15 | M/mi |
| 4 | 求解逆元 Yi | Y1=2, Y2=1, Y3=1 | MiYi ≡ 1 (mod mi) 35×2=70≡1(mod 3) 21×1=21≡1(mod 5) 15×1=15≡1(mod 7) |
| 5 | 计算项 aiMiYi | 2×35×2=140 3×21×1=63 2×15×1=30 |
各项乘积 |
| 6 | 求和 x | 140 + 63 + 30 = 233 | 总和 |
| 7 | 取模 M | 233 mod 105 = 23 | 最小非负解 |
结论：这个数最小是 23。验证：23÷3=7...2，23÷5=4...3，23÷7=3...2。符合题意。
《孙子算经》中的口诀“三人同行七十稀”对应的是 70 (即 21×1×... 的变体，古法略有不同但本质一致)，“五树梅花廿一枝”对应 21，“七子团圆正半月”对应 15 (15天即半月)。“除百零五便得知”即最后对 105 取模。
现代应用：从密码学到分布式计算
⚡ 密码学中的 RSA 加速
在 RSA 公钥密码系统中，私钥解密过程涉及大数模幂运算。利用中国剩余定理，可以将模数 n = p × q 的运算分解为模 p 和模 q 的两个较小运算，再合并结果。这使得解密速度提高约 4 倍，极大地提升了 RSA 的效率。
⚙️ 快速傅里叶变换 (FFT)
中国剩余定理变换 (CRT) 是快速傅里叶变换的一种替代方案，用于大整数乘法。通过将大整数映射到多个小模数域进行点乘，然后再用 CRT 合并结果，可以避免大数运算的复杂性，提高乘法效率。
🔒 秘密共享 (Shamir's Secret Sharing)
在信息安全领域，门限秘密共享方案常利用多项式插值，其理论基础与 CRT 密切相关。通过将秘密分解为多个份额，分发给不同参与者，只有达到一定数量的人合作才能利用类似 CRT 的算法恢复秘密。
📡 纠错码与通信
在数据通信中，中国剩余定理编码用于构造纠错码。通过在多个互质模数下对数据进行编码，接收端即使丢失部分信息，也能通过剩余的信息恢复原始数据，提高传输的可靠性。
常见疑问解答 (FAQ)
是的。中国剩余定理（Chinese Remainder Theorem, CRT）在西方常被称为孙子定理，源于中国古代数学著作《孙子算经》中的“物不知数”问题。虽然现代数学表述更为严谨和通用，但核心思想一致。
它广泛应用于数论、计算机科学、密码学（如RSA算法加速）、信号处理（快速傅里叶变换）以及纠错码等领域。它是现代信息安全的重要基石之一。
标准的中国剩余定理要求模数两两互质。如果模数不互质，需要检查方程组是否有解。如果有解，可以通过扩展中国剩余定理（EXCRT）求解，其原理是将方程两两合并，逐步缩小范围。
可以使用《孙子算经》中的口诀：“三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。”
即：(余数1×70 + 余数2×21 + 余数3×15) mod 105。
这个口诀是针对模数 3, 5, 7 的特例，其他模数需重新计算逆元。