在中国古代数学的璀璨星河中，《孙子算经》所记载的“物不知数"问题犹如一颗耀眼的星辰，它不仅奠定了中国剩余定理（Chinese Remainder Theorem, 简称 CRT）的基础，更展现了东方数学独特的构造性思维。本页面致力于为您提供最详尽的中国剩余定理口诀解析、历史演变、数学原理证明以及现代计算机科学的实际应用。无论是为了应对学术考试，还是探索数论之美，亦或是进行密码学研究，这里都是您不可或缺的参考手册。我们将通过结构化数据、深度文案和可视化图表，为您拆解这一古老而常新的数学命题。
中国剩余定理的雏形最早出现在公元四世纪的《孙子算经》卷下第二十六题中。题目原文如下：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”这是一个典型的同余方程组问题。该问题的解法被后世称为“大衍求一术"，由宋代数学家秦九韶在《数书九章》中系统化完善。
值得注意的是，虽然西方在 1801 年由高斯在《算术研究》中正式提出了这一理论的完整形式，但中国数学家早在 13 世纪就已经掌握了比西方早五百多年的解法。因此，国际数学界将其命名为Chinese Remainder Theorem，以表彰中国古代数学家的卓越贡献。
首次提出“物不知数”问题，标志着中国剩余定理问题的起源。
系统提出“大衍总数术”，将不定方程组的解法推广到任意模数，完成了理论体系的构建。
德国数学家高斯独立发现了该定理，并在西方学术界确立了其地位，命名为CRT。
广泛应用于 RSA 加密算法加速、大整数运算、分布式计算等领域，成为现代信息安全的基石之一。
针对《孙子算经》中最经典的“七”模数情况，古人总结出了一句流传千古的口诀。这句口诀不仅包含了数值，更隐含了最小公倍数与逆元的计算逻辑。
“三人同行七十稀，
“五树梅花廿一枝，
“七子团圆正半月，
“除百零五便得知。”
解读：
为什么是 70、21 和 15？这些数字并非随意选取，它们具有特定的数论性质：
这三者之和为 106，减去 105 后余 1，这正是构造解的关键——寻找乘法逆元的过程。
假设韩信点兵，三三数之剩二，五五数之剩三，七七数之剩二，问兵几何？
计算过程：
1. 3 的余数是 2 → 2 × 70 = 140
2. 5 的余数是 3 → 3 × 21 = 63
3. 7 的余数是 2 → 2 × 15 = 30
4. 求和：140 + 63 + 30 = 233
5. 取模：233 mod 105 = 23
答案：韩信至少有 23 名士兵。
虽然古人口诀精妙，但仅适用于模数为 3、5、7 的特殊情况。在现代数学中，我们需要一个通用的中国剩余定理算法来解决任意互质模数的同余方程组。
设有一组同余方程：
其中 m₁, m₂, ..., mₙ 两两互质。令 M = m₁ × m₂ × ... × mₙ，Mᵢ = M / mᵢ。
则方程组的通解为：
其中 yᵢ 是 Mᵢ 关于 mᵢ 的乘法逆元，即满足 Mᵢ × yᵢ ≡ 1 (mod mᵢ) 的整数。
我们只需要验证这个构造出来的 x 是否满足每一个同余方程。以第一个方程为例：
考虑 x mod m₁：
当 j ≠ 1 时，Mⱼ 包含因子 m₁，所以 Mⱼ ≡ 0 (mod m₁)，因此项 aⱼMⱼyⱼ ≡ 0 (mod m₁)。
只有第一项 a₁M₁y₁ 不为 0。根据定义，M₁y₁ ≡ 1 (mod m₁)，所以：
x ≡ a₁ × 1 + 0 + ... + 0 ≡ a₁ (mod m₁)。
同理可证对其他所有 i 都成立。由于模数互质，解在模 M 意义下是唯一的。
在计算机科学领域，中国剩余定理是处理大数运算的核心工具之一。以下提供 Python 和 C++ 两种主流语言的实现方案，展示了如何利用扩展欧几里得算法自动求解逆元。
Python 内置的大整数支持使其成为实现 CRT 的首选语言。
def extended_gcd(a, b):
if a == 0:
return b, 0, 1
else:
gcd, x, y = extended_gcd(b % a, a)
return gcd, y - (b // a) x, x
def mod_inverse(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(n_list, a_list):
"""
n_list: 模数列表 [m1, m2, ...]
a_list: 余数列表 [r1, r2, ...]
"""
product_n = 1
for n in n_list:
product_n = n
total_sum = 0
for n_i, a_i in zip(n_list, a_list):
p_n_i = product_n // n_i
inv_p_n_i = mod_inverse(p_n_i, n_i)
total_sum += a_i p_n_i inv_p_n_i
return total_sum % product_n
测试案例：物不知数
n_mods = [3, 5, 7]
remainders = [2, 3, 2]
result = chinese_remainder_theorem(n_mods, remainders)
print(f"最小正整数解为：{result}")
适用于对性能要求极高的场景，如嵌入式系统或高频交易算法。
#include <iostream>
using namespace std;
// 扩展欧几里得算法
long long extgcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) {
x = 1; y = 0;
return a;
}
long long d = extgcd(b, a % b, y, x);
y -= a / b x;
return d;
}
// 求逆元
long long modInverse(long long a, long long m) {
long long x, y;
long long g = extgcd(a, m, x, y);
if (g != 1) return -1; // 不存在逆元
return (x % m + m) % m;
}
int main() {
int n = 3;
long long a[] = {2, 3, 2}; // 余数
long long m[] = {3, 5, 7}; // 模数
long long M = 1;
for(int i=0; i<n; i++) M = m[i];
long long result = 0;
for(int i=0; i<n; i++) {
long long Mi = M / m[i];
long long yi = modInverse(Mi, m[i]);
result = (result + a[i] Mi % M yi % M) % M;
}
cout << "Result: " << result << endl;
return 0;
}