历史渊源：从《孙子算经》说起
中国剩余定理是中国古代数学辉煌成就的代表之一。其起源可追溯至公元五世纪左右的著作《孙子算经》。书中记载了一道著名的“物不知数”问题：
“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”
这个问题翻译成现代数学语言，就是求一个整数 x，满足：
- x ≡ 2 (mod 3)
- x ≡ 3 (mod 5)
- x ≡ 2 (mod 7)
《孙子算经》给出了巧妙的解法：“三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。” 这实际上就是中国剩余定理早期算法的民间口诀。后世数学家秦九韶在《数书九章》中将其推广为更一般的“大衍求一术”，形成了完整的理论体系。
历史时间轴
公元5世纪
《孙子算经》成书，记载“物不知数”问题，奠定中国剩余定理雏形。
公元1247年
秦九韶著《数书九章》，提出“大衍求一术”，系统化解决一次同余式组问题。
1801年
高斯在《算术研究》中独立提出并证明了该定理，西方称之为Chinese Remainder Theorem。
20世纪至今
随着计算机科学的发展，中国剩余定理成为密码学、编码理论的核心工具。
数学原理：同余方程组的解
在深入算法之前，我们需要理解中国剩余定理的数学本质。它处理的是线性同余方程组的问题。
1. 基本概念
设 m₁, m₂, ..., mₖ 是两两互质的正整数（即 gcd(mᵢ, mⱼ) = 1，当 i ≠ j 时）。对于任意整数 a₁, a₂, ..., aₖ，同余方程组：
x ≡ a₁ (mod m₁)
x ≡ a₂ (mod m₂)
...
x ≡ aₖ (mod mₖ)在模 M = m₁ × m₂ × ... × mₖ 的意义下，存在唯一解 x。
2. 为什么叫“剩余”？
“剩余”指的是除法运算中的余数。中国剩余定理通过已知的各个模数下的余数，反推出原始数字。这在信息压缩和重构中具有独特价值。
3. 存在性与唯一性证明简述
证明通常分为两部分：存在性和唯一性。
- 存在性：通过构造法证明。令 Mᵢ = M / mᵢ，找到 Mᵢ 模 mᵢ 的乘法逆元 yᵢ（即 Mᵢyᵢ ≡ 1 mod mᵢ），则解为 x = Σ aᵢMᵢyᵢ mod M。
- 唯一性：假设 x₁ 和 x₂ 都是解，则 x₁ ≡ x₂ (mod mᵢ) 对所有 i 成立。由于 mᵢ 两两互质，故 x₁ ≡ x₂ (mod M)。
算法步骤：如何求解？
掌握中国剩余定理的关键在于熟练运用算法。以下通过选项卡展示不同复杂度的案例。
案例：x ≡ 2 (mod 3), x ≡ 3 (mod 5), x ≡ 2 (mod 7)
- 计算总模数 M：M = 3 × 5 × 7 = 105。
- 计算 Mᵢ：
- M₁ = 105 / 3 = 35
- M₂ = 105 / 5 = 21
- M₃ = 105 / 7 = 15
- 求逆元 yᵢ：
- 35y₁ ≡ 1 (mod 3) → 2y₁ ≡ 1 (mod 3) → y₁ = 2
- 21y₂ ≡ 1 (mod 5) → 1y₂ ≡ 1 (mod 5) → y₂ = 1
- 15y₃ ≡ 1 (mod 7) → 1y₃ ≡ 1 (mod 7) → y₃ = 1
- 计算解 x：
x = (2×35×2 + 3×21×1 + 2×15×1) mod 105
x = (140 + 63 + 30) mod 105 = 233 mod 105 = 23
答案：最小正整数解为 23。
案例：x ≡ 1 (mod 2), x ≡ 2 (mod 3), x ≡ 3 (mod 5)
这是一个更贴近计算机二进制处理的例子。
- M = 2 × 3 × 5 = 30
- M₁=15, M₂=10, M₃=6
- 求逆元：
- 15y₁ ≡ 1 (mod 2) → 1y₁ ≡ 1 → y₁=1
- 10y₂ ≡ 1 (mod 3) → 1y₂ ≡ 1 → y₂=1
- 6y₃ ≡ 1 (mod 5) → 1y₃ ≡ 1 → y₃=1
- x = (1×15×1 + 2×10×1 + 3×6×1) mod 30 = (15 + 20 + 18) mod 30 = 53 mod 30 = 23
答案：最小正整数解为 23。
广义中国剩余定理：模数不互质
当模数 m₁, m₂ 不互质时，方程组 x ≡ a₁ (mod m₁) 和 x ≡ a₂ (mod m₂) 有解的充要条件是：
a₁ ≡ a₂ (mod gcd(m₁, m₂))
如果满足条件，可以合并这两个方程为一个新方程，模数变为 lcm(m₁, m₂)。重复此过程直到所有方程合并为一个。
| 情况 | 模数关系 | 解的存在性 | 处理方法 |
|---|---|---|---|
| 标准CRT | 两两互质 | 恒有唯一解 | 直接套用公式 |
| 广义CRT | 不互质 | 需满足相容性条件 | 两两合并，扩展欧几里得算法 |
现代应用：超越数论
中国剩余定理绝非仅仅是历史遗迹，它在现代科技中扮演着至关重要的角色，尤其是在计算机科学和密码学领域。
🔐 RSA 密码学加速
在 RSA 解密过程中，计算 m = cᵈ mod n 非常耗时。利用中国剩余定理，可以将模数 n 分解为 p 和 q（RSA密钥的两个大素数），分别在模 p 和模 q 下计算，再将结果合并。这可以将计算速度提高约4倍。
📡 编码理论
在纠错码（如Reed-Solomon码）中，中国剩余定理用于数据的冗余存储和错误恢复。即使部分数据丢失或损坏，也能通过剩余信息重构原始数据。
💻 大数运算优化
计算机处理超大整数乘法时，直接计算效率低。CRT允许将大数映射到多个小模数下并行计算，最后合并结果，显著提升性能。
🌐 秘密共享
在门限签名和秘密共享方案中，中国剩余定理用于将秘密分割成多个份额，只有达到一定数量的份额才能重构秘密。
网友们还关心：CRT 与 离散对数问题
虽然中国剩余定理本身不是加密算法，但它常常与离散对数问题结合使用。例如，在 Diffie-Hellman 密钥交换中，CRT 可用于优化模幂运算。此外，在椭圆曲线密码学中，CRT 也被用于加速标量乘法。
常见问题解答 (FAQ)
A: 中国剩余定理最早出现在公元五世纪的《孙子算经》中，原题为“物不知数”问题。秦九韶在《数书九章》中将其系统化。
A: 广泛应用于现代密码学（如RSA算法加速）、计算机代数系统、误差校正码（如QR码、通信传输）以及分布式计算中。
A: 标准的中国剩余定理要求模数两两互质。如果模数不互质，则需要使用广义中国剩余定理，且解存在的条件是余数满足特定的相容性条件（即 aᵢ ≡ aⱼ mod gcd(mᵢ, mⱼ)）。
A: 求解 a ≡ x⁻¹ (mod m) 通常使用扩展欧几里得算法（Extended Euclidean Algorithm）。如果 m 是质数，也可以使用费马小定理：x ≡ aᵐ⁻² (mod m)。
A: 德国数学家高斯在1801年出版的《算术研究》中独立证明并系统阐述了该定理，因此西方称之为“Chinese Remainder Theorem”。高斯的工作使其在西方数学界广为人知。