剩余定理 · 逐级满足法 —— 逐级满足剩余定理法深度解析

从互质判定到最小公倍数计算，从欧拉函数运用到容斥原理实践，系统构建数论解题思维框架，助您掌握“逐级满足”的核心策略与实战技巧。

? 概念解析：什么是剩余定理与逐级满足法？

剩余定理（尤其是中国剩余定理）是数论中关于同余方程组解的存在性与构造性的重要定理，而逐级满足法是其核心解题策略——通过逐步满足每一个同余条件，最终构建出满足全部条件的解。

基本定义与核心逻辑

给定一组互质的正整数 m₁, m₂, ..., mₙ，以及任意整数 a₁, a₂, ..., aₙ，则同余方程组：

                        x ≡ a₁ (mod m₁)

                        x ≡ a₂ (mod m₂)

                        ...

                        x ≡ aₙ (mod mₙ)

在模 M = m₁ × m₂ × ... × mₙ 下有唯一解。这就是剩余定理的经典表述。

? 关键理解：当模数两两互质时，同余条件之间“互不干扰”，解可被唯一构造出来——这正是“逐级满足法”的数学基础。

什么是“逐级满足”？

所谓逐级满足，是指从第一个同余条件出发，构造一个满足它的数；再在此基础上调整，使其满足第二个条件；依次类推，直至满足全部条件。

例如对以下方程组：

                        x ≡ 2 (mod 3)

                        x ≡ 3 (mod 5)

                        x ≡ 2 (mod 7)

我们首先找满足 x ≡ 2 (mod 3) 的数，如 2、5、8、11、14、17、20、23、26……

再从中筛选满足 x ≡ 3 (mod 5) 的：23 是第一个（23 ÷ 3 = 7…2，23 ÷ 5 = 4…3）。

最后从 23 开始，以 LCM(3,5)=15 为步长递增（23、38、53、68、83、98…），找到满足 x ≡ 2 (mod 7) 的：23（23÷7=3…2）即为解。

最终解为 x ≡ 23 (mod 105)，其中 105 = 3×5×7。

互质判定：解题的第一道关卡

两数 a 与 b 互质，当且仅当它们的最大公约数 GCD(a, b) = 1。

常见互质组合：

任意两个连续整数（如 8 与 9）
质数与非其倍数的任意整数（如 7 与 15）
与任意正整数（GCD(1, n) = 1）
两个不同的质数（如 11 与 13）

反例：(6, 9) 不互质（GCD = 3），(10, 15) 不互质（GCD = 5），(4, 8) 不互质（GCD = 4）。

? 实用技巧：当模数不互质时，需先判断同余方程组是否相容（即是否有解），否则直接无解。例如：

                            x ≡ 1 (mod 4)

                            x ≡ 2 (mod 6)

第一个式子说明 x 为奇数，第二个式子要求 x 为偶数 → 矛盾 → 无解。

最小公倍数（LCM）的深层意义

在逐级满足过程中，每加入一个新模数，解的周期变为当前所有模数的最小公倍数。

例如：满足 x ≡ a (mod m) 和 x ≡ b (mod n) 的解，其周期为 LCM(m, n)，而非简单乘积（仅当 GCD(m, n) = 1 时，LCM(m,n) = m×n）。

计算公式：

LCM(m, n) = |m × n| / GCD(m, n)

扩展至多数：

LCM(a, b, c) = LCM(LCM(a, b), c)

⚖️ 核心原理：欧拉函数与容斥原理的协同作用

欧拉函数 φ(n) 的本质与应用

欧拉函数 φ(n) 定义为小于或等于 n 的正整数中与 n 互质的数的个数。

例如：

φ(1) = 1（定义）
φ(2) = 1（仅 1）
φ(3) = 2（1, 2）
φ(12) = 4（1, 5, 7, 11）
φ(15) = φ(3×5) = φ(3)×φ(5) = 2×4 = 8（1,2,4,7,8,11,13,14）

通用计算公式（n = p₁^k₁ × p₂^k₂ × ... × pᵣ^kᵣ）：

φ(n) = n × (1 - 1/p₁) × (1 - 1/p₂) × ... × (1 - 1/pᵣ)

欧拉函数在逐级满足法中的角色

虽然欧拉函数不直接参与同余方程的求解，但它在以下场景中至关重要：

判断解空间结构：φ(n) 的结果代表模 n 下可逆元的个数，这些可逆元构成乘法群，其结构影响扩展欧几里得算法的执行路径。
优化模反元素计算：当 GCD(a, n) = 1 时，a 在模 n 下的逆元为 a^{φ(n)-1} mod n（欧拉定理）。
统计满足条件的解的个数：例如求 1 到 N 中与 n 互质的数的个数，可近似为 N × φ(n)/n。

容斥原理：处理非互质模数的终极武器

当模数不互质时，中国剩余定理不再直接适用，此时需用容斥原理判断相容性或求解特定范围内的解数。

经典问题：求 1 到 100 中能被 2 或 3 整除的数的个数。

能被 2 整除：50 个
能被 3 整除：33 个
能被 6 整除（2 和 3 的 LCM）：16 个
总数 = 50 + 33 − 16 = 67

推广至 n 个条件：

                        |A₁ ∪ A₂ ∪ ... ∪ Aₙ| = Σ|Aᵢ| − Σ|Aᵢ ∩ Aⱼ| + Σ|Aᵢ ∩ Aⱼ ∩ Aₖ| − ... + (−1)^{n+1}|A₁ ∩ ... ∩ Aₙ}|
                    

逐级满足法 vs 容斥原理：何时用哪个？

应用场景	推荐方法	原因
模数两两互质	逐级满足法	解存在且唯一（模乘积），构造性强
求“能被多个数整除”的数的个数	LCM + 除法	直接计算 LCM 的倍数个数
求“能被至少一个数整除”的数的个数	容斥原理	需排除重复计数
模数不互质但方程组有解	逐级满足 + 相容性检验	每步需验证 GCD(m₁,m₂) \| (a₂−a₁)

?️ 实战方法：逐级满足法四步操作法

第一步：预处理与相容性检验

将所有同余式标准化为 x ≡ aᵢ (mod mᵢ)，其中 0 ≤ aᵢ < mᵢ。

对每对模数 (mᵢ, mⱼ)，计算 d = GCD(mᵢ, mⱼ)。

检查是否 aᵢ ≡ aⱼ (mod d)。若存在不满足，则整个方程组无解。

示例：检验以下方程组是否相容：

                            x ≡ 3 (mod 6)

                            x ≡ 5 (mod 9)

GCD(6,9) = 3

检查：3 mod 3 = 0，5 mod 3 = 2 → 0 ≠ 2 → 不相容 → 无解

第二步：逐级合并（两两合并）

将两个同余式合并为一个：

                            x ≡ a (mod m)

                            x ≡ b (mod n)

等价于：

                            x = a + m·k

                            a + m·k ≡ b (mod n) ⇒ m·k ≡ (b − a) (mod n)

令 d = GCD(m, n)，若 d ∤ (b−a)，则无解；否则化简为：

(m/d)·k ≡ (b−a)/d (mod n/d)

由于 GCD(m/d, n/d) = 1，可求出 k ≡ k₀ (mod n/d)，代入得：

x = a + m·(k₀ + t·n/d) = (a + m·k₀) + t·LCM(m,n)

即合并为 x ≡ c (mod LCM(m,n))

第三步：求解线性同余方程（扩展欧几里得算法）

核心是求解：m·k ≡ (b−a) (mod n)

扩展欧几里得算法返回 (d, x₀, y₀)，使得：m·x₀ + n·y₀ = d = GCD(m,n)

若 d ∣ (b−a)，则特解为：k₀ = x₀ × (b−a)/d

代码示例（Python）：

                            def extended_gcd(a, b):
                                if b == 0:
                                    return a, 1, 0
                                g, x, y = extended_gcd(b, a % b)
                                return g, y, x - (a // b)  y
                            def solve_two(a, m, b, n):
                                # 求解 x ≡ a (mod m), x ≡ b (mod n)
                                g, p, q = extended_gcd(m, n)
                                if (b - a) % g != 0:
                                    return None  # 无解
                                lcm = m // g  n
                                k0 = p  (b - a) // g
                                x = a + m  k0
                                return x % lcm, lcm
                        

第四步：解的通式与范围筛选

合并所有条件后，得到：x ≡ x₀ (mod M)

在区间 [L, R] 内的解的个数为：

count = floor((R - x₀)/M) - floor((L - 1 - x₀)/M)

示例：求满足 x ≡ 23 (mod 105) 且 1 ≤ x ≤ 1000 的解的个数。

                            x₀ = 23, M = 105, L = 1, R = 1000
                            floor((1000 - 23)/105) = floor(977/105) = 9
                            floor((0 - 23)/105) = floor(-23/105) = -1
                            count = 9 - (-1) = 10
                        

解为：23, 128, 233, 338, 443, 548, 653, 758, 863, 968

⚠️ 常见陷阱：

忽略标准化步骤（aᵢ 应在 [0, mᵢ) 内）
合并时未检查相容性，强行计算导致错误
通解公式中忘记取模，导致结果过大
范围筛选时未考虑边界（L-1 的处理）

? 经典案例：从简单到复杂，全面掌握解题技巧

案例 1：标准三模互质问题（中国剩余定理经典应用）

求解：

                        x ≡ 2 (mod 3)

                        x ≡ 3 (mod 5)

                        x ≡ 2 (mod 7)

解：

合并前两个：x = 2 + 3k，代入第二式 ⇒ 2 + 3k ≡ 3 (mod 5) ⇒ 3k ≡ 1 (mod 5) ⇒ k ≡ 2 (mod 5) ⇒ x = 2 + 3×2 = 8 (mod 15)
合并结果与第三式：x = 8 + 15m，代入第三式 ⇒ 8 + 15m ≡ 2 (mod 7) ⇒ 1 + m ≡ 2 (mod 7) ⇒ m ≡ 1 (mod 7) ⇒ x = 8 + 15 = 23 (mod 105)

最终解： x ≡ 23 (mod 105)

验证：23 ÷ 3 = 7…2 ✓，23 ÷ 5 = 4…3 ✓，23 ÷ 7 = 3…2 ✓

案例 2：模数不互质但有解（需相容性检验）

求解：

                        x ≡ 5 (mod 6)

                        x ≡ 11 (mod 15)

解：

GCD(6,15) = 3
mod 3 = 2，11 mod 3 = 2 → 相容 ✓
x = 5 + 6k，代入第二式：5 + 6k ≡ 11 (mod 15) ⇒ 6k ≡ 6 (mod 15) ⇒ 2k ≡ 2 (mod 5) ⇒ k ≡ 1 (mod 5)
⇒ x = 5 + 6×1 = 11 (mod LCM(6,15)=30)

最终解： x ≡ 11 (mod 30)

案例 3：应用逐级满足法求大数模幂（RSA 解密辅助）

求 2¹⁰⁰ mod 1001

注意：1001 = 7 × 11 × 13（三数互质）

分别计算：

¹⁰⁰ mod 7 = (2³)³³ × 2¹ mod 7 = 1³³ × 2 = 2

                        2¹⁰⁰ mod 11 = (2¹⁰)¹⁰ mod 11 = 1¹⁰ = 1（费马小定理）

                        2¹⁰⁰ mod 13 = (2¹²)⁸ × 2⁴ mod 13 = 1⁸ × 3 = 3

解方程组：

                        x ≡ 2 (mod 7)

                        x ≡ 1 (mod 11)

                        x ≡ 3 (mod 13)

逐步合并：

合并前两个：x = 2 + 7k ⇒ 2 + 7k ≡ 1 (mod 11) ⇒ 7k ≡ −1 ≡ 10 (mod 11) ⇒ k ≡ 8 (mod 11) ⇒ x = 2 + 56 = 58 (mod 77)
合并结果与第三式：x = 58 + 77m ⇒ 58 + 77m ≡ 3 (mod 13) ⇒ 6 + 12m ≡ 3 (mod 13) ⇒ 12m ≡ −3 ≡ 10 (mod 13) ⇒ m ≡ 10 (mod 13)（因 12⁻¹ ≡ −1 ≡ 12）⇒ x = 58 + 770 = 828 (mod 1001)

答案： 2¹⁰⁰ mod 1001 = 828

案例 4：求满足多个同余条件的最小正整数

个数被 3 除余 2，被 5 除余 3，被 7 除余 4，求最小正整数。

                        x ≡ 2 (mod 3)

                        x ≡ 3 (mod 5)

                        x ≡ 4 (mod 7)

解法同案例 1，但注意余数递增，可观察：x + 1 ≡ 0 (mod 3,5,7) ⇒ x + 1 是 105 的倍数 ⇒ 最小 x = 105 − 1 = 104

验证：104 ÷ 3 = 34…2 ✓，104 ÷ 5 = 20…4 ❌（咦？）

哦！余数应为 3，而非 4。修正：x + 1 ≡ 0 (mod 3,5) ⇒ x ≡ −1 (mod 15)，但 x ≡ 4 (mod 7) ⇒ x = 14k − 1，代入：14k − 1 ≡ 4 (mod 7) ⇒ −1 ≡ 4 (mod 7) → 矛盾。

正确做法：仍用标准合并法，得 x ≡ 53 (mod 105)，最小为 53。

答案： 53

? 周边知识：构建完整的数论知识网络

费马小定理

若 p 为质数，且 GCD(a, p) = 1，则：a^{p−1} ≡ 1 (mod p)

推论：a^p ≡ a (mod p)（对任意 a 成立）

用途：快速模幂、检验质数（伪素数测试）

扩展欧几里得算法

求解方程：ax + by = GCD(a, b)

返回 (d, x, y)，其中 d = GCD(a, b)

用途：求模逆元、解线性同余方程

模逆元

满足 a·a⁻¹ ≡ 1 (mod m) 的 a⁻¹

存在条件：GCD(a, m) = 1

求法：扩展欧几里得算法或 a^{φ(m)−1} mod m

RSA 加密原理

选两质数 p, q，计算 n = p·q，φ(n) = (p−1)(q−1)

选 e 满足 GCD(e, φ(n)) = 1

求 d = e⁻¹ mod φ(n)

加密：c = m^e mod n；解密：m = c^d mod n

核心：剩余定理可加速模 n 运算（分别模 p 和 q）

互质数对的统计规律

到 N 中互质数对 (a, b)（a < b）的个数近似为：(3/π²)·N²

推导依据：GCD(a, b) = 1 的概率为 6/π² ≈ 0.6079

示例：N = 100 时，互质对约 0.6079 × C(100,2) ≈ 3039 对

最小公倍数的分布特性

随机选取两个正整数 m, n，其 LCM 的期望值为无穷大，但 LCM(m, n) ≤ m·n，且：

Σ_{m=1}^n Σ_{n=1}^n LCM(m, n) ~ (π²/12)·n²·ln n + C·n²

这说明 LCM 的增长速度介于线性和平方之间。

❓ 网友还关心：高频问题与深度解答

剩余定理和逐级满足法有什么本质区别？

,284 人关注

模数不互质时还能用剩余定理吗？

人关注

逐级满足法和暴力枚举哪个更快？

人关注

如何用编程实现剩余定理求解？

人关注

剩余定理在密码学中有哪些实际应用？

人关注

欧拉函数和剩余定理有什么联系？

人关注

中国剩余定理的名字来源是什么？

人关注

如何快速判断两个大数是否互质？

人关注

网友提问精选

Q1：模数不互质时，逐级满足法是否完全失效？

A：并非失效，而是需要增加相容性检验步骤。例如：

                        x ≡ 4 (mod 6)

                        x ≡ 7 (mod 9)

GCD(6,9)=3，4 mod 3 = 1，7 mod 3 = 1 → 相容。

解法：x = 4 + 6k，代入得 4 + 6k ≡ 7 (mod 9) ⇒ 6k ≡ 3 (mod 9) ⇒ 2k ≡ 1 (mod 3) ⇒ k ≡ 2 (mod 3) ⇒ x = 4 + 12 = 16 (mod 18)。

因此，逐级满足法仍适用，只是合并时需验证 GCD | (b−a)。

Q2：为什么剩余定理要求模数两两互质？

A：这是保证解唯一性的关键条件。数学上，环 Z/MZ 同构于直积环 Z/m₁Z × Z/m₂Z × ... × Z/mₙZ 当且仅当模数两两互质。

直观理解：若模数有公因数 d > 1，则两个模数共享一个“周期分量”，可能导致约束冲突（如 x ≡ 1 (mod 2) 与 x ≡ 0 (mod 4) 矛盾）。

Q3：能否用逐级满足法求解非线性同余方程？

A：不能直接使用。逐级满足法仅适用于线性同余方程组。非线性方程（如 x² ≡ a (mod n)）需用二次剩余理论、Hensel 引理等更高级工具。

例外：若非线性方程可转化为线性（如通过变量替换），则可间接应用。

? 发展简史：从《孙子算经》到现代密码学

公元 3 世纪

《孙子算经》提出“物不知数”问题：

“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”

即求解同余方程组，给出“三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五便得知”的口诀解法。

年

秦九韶《数书九章》系统化：

提出“大衍求一术”（即求解一次同余方程组的算法），比欧洲高斯早 555 年。

完整阐述了“定理数”“乘率”“约数”“缀术”等概念，构成现代剩余定理的雏形。

年

高斯《算术探索》正式提出：

在第36节中给出一般形式的中国剩余定理，并证明其唯一性。

因高斯的影响力，该定理在西方被称为“Chinese Remainder Theorem”。

世纪中叶

与抽象代数结合：

环论中，定理被推广为：若 ideals I₁, ..., Iₙ 两两互素，则 R/(∩Iᵢ) ≅ Π R/Iᵢ。

成为交换代数与代数几何的核心工具。

年

RSA 加密算法诞生：

Rivest, Shamir, Adleman 利用剩余定理加速模幂运算，实现高效加密解密。

标志着剩余定理在现代信息安全中的关键应用。

世纪

分布式计算与密码学扩展：

秘密共享（Shamir's Secret Sharing）、快速傅里叶变换（NTT）、椭圆曲线密码学中广泛应用。

逐级满足思想延伸至约束满足问题（CSP）与人工智能规划领域。

? 实际应用：从理论到现实世界的桥梁

密码学：RSA 加密的加速器

在 RSA 解密中，需计算 m = c^d mod n，其中 n = p·q。

直接计算模 n 的幂运算复杂度高，而：

计算 m₁ = c^d mod p
计算 m₂ = c^d mod q
用剩余定理合并得 m mod n

由于 p 和 q 约为 n 的平方根，此法可将运算速度提升约 4 倍（因模数减半，指数运算复杂度呈指数下降）。

计算机科学：大整数分解与哈希设计

在多项式哈希中，常选择多个互质大质数作为模数，计算哈希值的多个分量，再用剩余定理合并，降低碰撞概率。

例如：哈希函数 h(x) = (h₁(x), h₂(x), h₃(x))，其中 hᵢ(x) = P(x) mod pᵢ，pᵢ 为互质大质数。

数学竞赛：解题的“杀手锏”

在国际数学奥林匹克（IMO）、中国数学奥林匹克（CMO）中，剩余定理是解决数论题的常规武器。

典型题型：

求大数的末几位数字（模 10^k）
证明某数能被多个数整除
构造满足特定余数条件的数列

信号处理：快速傅里叶变换（NTT）

数论变换（NTT）是 FFT 在有限域上的模拟，要求模数为质数且存在原根。

当需要长序列卷积时，可选择多个 NTT-prime（如 998244353, 1004535809），分别计算后用剩余定理合并，避免浮点误差。

日常应用：日历计算与排班问题

求两个周期事件的共同发生时间：

甲每 6 天值一次班，乙每 8 天值一次班，今天两人同班，问下次同班是几天后？

即求 LCM(6,8) = 24 天后。

若甲余 1 天（即明天值），乙余 3 天，则解同余方程组：

                        x ≡ 1 (mod 6)

                        x ≡ 3 (mod 8)

得 x ≡ 9 (mod 24)，即 9 天后两人同班。