原理概述：什么是剩余定理？
剩余定理逐步满足法，通常被称为中国剩余定理（Chinese Remainder Theorem, 简称CRT），是数论中一个关于同余方程组的重要定理。它最早出现在中国古代数学著作《孙子算经》中，著名的“物不知数”问题便是其经典原型。
核心定义
假设我们有一组同余方程，其模数两两互质（即任意两个模数的最大公约数为1），则该方程组在模数乘积的意义下有唯一解。简单来说，如果你知道一个数除以几个不同数的余数，且这些除数互质，你就能唯一确定这个数（在一定范围内）。
互质性要求
模数 m1, m2, ..., mk 必须两两互质。这是定理成立的必要前提，否则解可能不存在或不唯一。
唯一解存在
在模 M = m1 m2 ... mk 的意义下，解是唯一的。这意味着所有解之间相差 M 的整数倍。
构造性证明
定理不仅证明解存在，还提供了构造解的具体方法，即“逐步满足法”，通过叠加特解来得到最终结果。
经典原型：物不知数
《孙子算经》卷下第二十六题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”
翻译成现代数学语言，即求解同余方程组：
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
这个问题的答案最小是23。这就是剩余定理逐步满足法最原始的应用场景。
算法步骤：逐步满足法详解
“逐步满足法”的核心思想是：先构造出满足某一个方程余数条件，而对其他方程余数为0的“特解”，然后将这些特解加权求和，最后取模得到最终结果。
第一步：检查与预处理
首先，列出所有同余方程，形式如下：
x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
...
x ≡ ak (mod mk)
关键检查：确认所有模数 m1, m2, ..., mk 是否两两互质。如果不互质，需要先通过扩展欧几里得算法或合并方程的方法处理，将其转化为互质模数的形式，或者判断无解。
计算总模数 M = m1 m2 ... mk。
第二步：构造基础特解
对于每一个方程 i，我们需要构造一个数 xi，满足：
xi能被所有其他模数mj (j ≠ i)整除。xi ≡ 1 (mod mi)。
具体操作：
1. 计算 Mi = M / mi（即总模数除以当前模数）。
2. 求 Mi 关于模 mi 的模逆元 ti，即满足 Mi ti ≡ 1 (mod mi) 的整数 ti。
3. 则该方程的特解基础部分为 yi = Mi ti。
第三步：加权求和
将每个方程的余数 ai 乘以其对应的特解基础部分 yi，然后将所有结果相加：
S = a1y1 + a2y2 + ... + akyk
此时，S 已经满足所有同余方程的条件，但它可能非常大，远大于总模数 M。
第四步：取模求最小正整数
为了得到最小正整数解，我们对总和 S 取模 M：
x = S mod M
如果结果为0，则最小正整数解为 M（取决于具体定义，通常取余数范围 [0, M-1] 或 [1, M]）。
示例：在“物不知数”问题中，M=105。我们构造出特解后求和，再对105取余，最终得到23。
经典案例演练
为了更深入理解剩余定理逐步满足法，我们通过一个稍微复杂的例子来演示全过程。
案例：求解同余方程组
求解 x：
x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)
| 步骤 | 操作 | 计算过程 | 结果 |
|---|---|---|---|
| 1 | 计算总模数 M | 3 × 5 × 7 | M = 105 |
| 2 | 方程1特解 | M1=35, 35×2≡1(mod 3)→t1=2, y1=35×2=70 | y1 = 70 |
| 3 | 方程2特解 | M2=21, 21×1≡1(mod 5)→t2=1, y2=21×1=21 | y2 = 21 |
| 4 | 方程3特解 | M3=15, 15×1≡1(mod 7)→t3=1, y3=15×1=15 | y3 = 15 |
| 5 | 加权求和 S | 2×70 + 3×21 + 2×15 | S = 140 + 63 + 30 = 233 |
| 6 | 取模求 x | 233 mod 105 | x = 23 |
验证：23 ÷ 3 = 7...2，23 ÷ 5 = 4...3，23 ÷ 7 = 3...2。符合所有条件。
历史演变：从孙子到高斯
《孙子算经》
中国南北朝时期，记载了“物不知数”问题，提出了初步的解法口诀：“三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。”
斐波那契《算盘书》
意大利数学家斐波那契在欧洲著作中独立提出了类似的问题和解法，使得这一知识在西方逐渐传播。
高斯《算术研究》
德国数学家高斯在《算术研究》中系统地引入了同余符号“≡”，并给出了中国剩余定理的现代形式证明，奠定了其在数论中的地位。
计算机科学应用
随着计算机诞生，CRT被广泛应用于大整数运算加速、RSA密码系统、纠错编码等领域，成为现代信息安全的基石之一。
实际应用：不止于数学题
剩余定理逐步满足法在现代科技中扮演着至关重要的角色，尤其是在处理大数和并行计算方面。
1. 密码学中的加速运算
在RSA加密算法中，私钥解密过程涉及极大的指数模运算。利用CRT，可以将一个大模数 N = p q 的运算分解为两个小模数 p 和 q 下的运算，速度可提升约4倍。
2. 大整数表示与计算
在计算机处理超过硬件寄存器长度的超大整数时，可以使用多个较小的互质模数分别存储和计算该整数。这种表示法称为剩余数系统（Residue Number System, RNS）。加减乘除运算可以在各个模数下独立并行进行，最后通过CRT合并结果。
3. 错误纠正码
在数据存储和传输中，CRC校验和里德-所罗门码等纠错技术有时利用同余原理来检测和纠正错误，确保信息的完整性。
常见问题解答 (FAQ)
标准的剩余定理（中国剩余定理）要求模数两两互质。如果模数不互质，则需要先判断方程组是否有解，并通过扩大模数或使用扩展欧几里得算法合并方程，不能直接套用简单的逐步满足法公式。
该方法的核心思想是“先满足一个条件，再保持已满足条件不变，去满足下一个条件”。在构造特解时，我们让某个数只对当前关心的方程有余数，而对其他方程余数为0，从而逐步叠加出最终解。
在密码学（如RSA算法的大数分解与加速）、错误纠正码、以及大整数运算的模运算优化中，剩余定理都有广泛应用。它允许我们将一个大数的运算分解为多个小模数下的并行运算，提高计算效率。
可以使用扩展欧几里得算法。例如求 35 关于模 3 的逆元，即解 35x ≡ 1 (mod 3)。因为 35 ≡ 2 (mod 3)，所以解 2x ≡ 1 (mod 3)，显然 x=2。或者直接用辗转相除法回溯求解。