中国剩余定理(CRT)解题实战:CLRS 31.5 节全部习题精解与推导
本文以当前仓库中 docs/Chap31/31.5.md 为主体,完整推导《算法导论》第 3 版第 31 章 31.5 节(The Chinese Remainder Theorem)的 4 道课后习题,并补充 CRT 定理(Theorem 31.27)与式 (31.28)–(31.30) 的原理、逐步数值构造、通解验算,以及同一仓库中配套解法(模逆、扩展欧几里得、模幂)的源码级佐证。读完本文,你将掌握:用 CRT 构造公式求同余方程组的全部解、判断解的个数、证明 CRT 同构对逆元与多项式根的保持性。
一、背景:中国剩余定理与前置知识
本节对应仓库章节体系中的 31.5 The Chinese remainder theorem(见 mkdocs.yml 导航 VII Selected Topics → 31 Number-Theoretic Algorithms)。CRT 是数论算法一章中的核心桥梁:它上承 31.1–31.4 节(整除、gcd、模算术、模线性方程),下启 31.6 节(元素幂)与 31.7 节(RSA 公钥密码系统),因此本节习题全部围绕「模分解 → 逐模求解 → 组合还原」这一范式展开。
1.1 CRT 定理(Theorem 31.27)与式 (31.28)–(31.30)
设
n=n1n2⋯nk,
其中 n1,n2,…,nk 两两互素(pairwise relatively prime)。则映射
a↔(a1,a2,…,ak),ai=amodni,
是 Zn 与直积 Zn1×Zn2×⋯×Znk 之间的一一对应(bijection)。
构造公式(式 (31.28)):令 Mi=n/ni(即除 ni 外其余模数的乘积),取 Mi−1 为 Mi 模 ni 的乘法逆元,记
ci=Mi⋅(Mi−1modni),
则对任意目标余数组 (a1,…,ak),唯一解为
a≡(i=1∑kaici)(modn).
CRT 同构还保持运算:式 (31.29) 保证模 n 下的加法对应到各分量模 ni 下的加法,式 (31.30) 保证模 n 下的乘法对应到各分量模 ni 下的乘法。这两条运算律正是习题 31.5-3 与 31.5-4 的证明基础(文档原句「Based on 31.28–31.30」)。
1.2 前置工具回顾(仓库配套解法)
- 模逆的计算:CRT 构造需要大量 Mi−1modni,其通用算法是扩展欧几里得
EXTENDED-EUCLID,完整伪代码见 docs/Chap31/31.2.md(返回三元组 (d,x,y) 满足 ax+by=gcd(a,b))。
- 两两互素的判别:docs/Chap31/31.2.md 习题 31.2-9 证明了 n1,…,nk 两两互素当且仅当 gcd 乘积对互素,这是 CRT 适用性的判据。
- 模线性方程:单个同余方程 ax≡b(modn) 的解结构见 docs/Chap31/31.4.md,CRT 将「模 n 的一个方程」分解为「模 ni 的 k 个方程」后逐一求解再合并。
二、习题 31.5-1:两模同余方程组的 CRT 逐步构造
题目:求方程组
x≡4(mod5),x≡5(mod11)
的全部解。
2.1 代入 CRT 构造公式
模数 n1=5、n2=11 互素(gcd(5,11)=1),n=55。按式 (31.28),对 i=1,2 计算 Mi=n/ni:
| 分量 i |
模数 ni |
Mi=n/ni |
Mimodni |
Mi−1modni |
ci=Mi⋅(Mi−1modni) |
| 1 |
5 |
11 |
1 |
1(1×1≡1(mod5)) |
11 |
| 2 |
11 |
5 |
5 |
9(5×9=45≡1(mod11)) |
45 |
这正是文档中的关键数值:m1=11,m2=5;m1−1=1,m2−1=9;c1=11,c2=45(注意文档中 mi 取的是「另一个模数」,即与定理中 Mi 相同的含义)。
2.2 组合求解
a=(c1a1+c2a2)mod(n1n2)=(11⋅4+45⋅5)mod55=269mod55=49.
全部解:x≡49(mod55),即
x=49+55t,t∈Z.
2.3 验算
49mod5=4,49mod11=5(49=44+5).
两条同余式同时满足,且模 55 的剩余类唯一,故 49+55t 即全部解集。方法要点:每个 ci 的作用是「只在该分量对应的模 ni 下等于 1、在其余模 nj 下等于 0」,从而 aici 精确地贡献目标余数而不互相干扰。
三、习题 31.5-2:三模同余方程组的求解
题目:求所有被 9、8、7 除分别余 1、2、3 的整数 x,即
x≡1(mod9),x≡2(mod8),x≡3(mod7).
3.1 通解形式
9,8,7 两两互素,n=9×8×7=504。文档给出的答案是
x=10+504i,i∈Z,
等价地 x≡10(mod504)。
验算:
10mod9=1,10mod8=2,10mod7=3.
三条同余式全部满足;由于 mod504 的解唯一,10+504i(i∈Z)即全部解。
3.2 用构造公式独立复现 10
作为练习,我们按式 (31.28) 完整构造(这也验证了 31.5-2 的答案来源):
| 分量 i |
ni |
Mi=504/ni |
Mi−1modni |
ci=Mi⋅(Mi−1) |
| 1 |
9 |
56 |
2−1≡5(mod9) |
56×5=280 |
| 2 |
8 |
63 |
7−1≡7(mod8) |
63×7=441 |
| 3 |
7 |
72 |
2−1≡4(mod7) |
72×4=288 |
于是
a=(1×280+2×441+3×288)mod504=2026mod504=10,
与文档答案一致。其中各逆元可快速核对:2×5=10≡1(mod9),7×7=49≡1(mod8),2×4=8≡1(mod7)。
方法要点:分量数 k 增多时,构造公式完全不变,只是求和项数从 2 变成 k;每个 Mi 始终是与 ni 互素的(因 ni 与其余 nj 两两互素),所以 Mi−1modni 必定存在——这正是 31.5-3 要论证的核心事实。
四、习题 31.5-3:CRT 同构下的逆元保持性
题目:在 Theorem 31.27 的定义下证明:若 gcd(a,n)=1,则
(a−1modn)↔((a1−1modn1),(a2−1modn2),…,(ak−1modnk)).
4.1 论证思路
第一步:每个分量上的逆元都存在。 文档给出的关键观察是
gcd(a,n)=1⇒gcd(a,ni)=1(∀i).
理由:ni∣n,任何同时整除 a 与 ni 的整数也同时整除 a 与 n,故 gcd(a,ni) 必整除 gcd(a,n)=1。因此每个 ai=amodni 在 Zni∗ 中都是单位,唯一逆元 ai−1modni 存在。
第二步:用乘法运算律(式 (31.30))传递。 由逆元定义,a⋅a−1≡1(modn)。CRT 同构把模 n 的乘法对应到各分量乘法,即
a⋅a−1modn↔(a1⋅b1modn1,…,ak⋅bkmodnk),
其中 bi=a−1modni。等号右侧必须等于单位元的分量表示 (1,…,1),于是每个分量满足
ai⋅bi≡1(modni),
即 bi≡ai−1(modni)。再由 CRT 一一对应性,模 n 下 a−1 的剩余类恰好对应各分量逆元的元组。
4.2 结论
a−1modn↔(a1−1modn1,…,ak−1modnk).
实战意义:当 n 为大合数(如 RSA 模数)时,求「模 n 的大逆元」可分解为对每个小模 ni 求逆再经 CRT 还原,显著降低单次运算规模。模逆本身也可用 docs/Chap31/31.6.md 习题 31.6-3 的欧拉定理方法 a−1≡aϕ(n)−1(modn) 计算,两种途径殊途同归。
五、习题 31.5-4:多项式根的个数乘积律
题目:在 Theorem 31.27 的定义下,证明对任意多项式 f,方程 f(x)≡0(modn) 的根的个数等于以下 k 个方程根数之积:
f(x)≡0(modn1),f(x)≡0(modn2),…,f(x)≡0(modnk).
文档给出的提示为「Based on 31.28–31.30」,即基于 CRT 的构造公式与分量运算律。
5.1 论证思路
第一步:根的「可分解性」。 对任意整数 x:
- 若 f(x)≡0(modn),则因 ni∣n,必有 f(x)≡0(modni)(对所有 i);
- 反之,若 f(x)≡0(modni) 对所有 i 成立,则每个 ni∣f(x);由于 n1,…,nk 两两互素,乘积 n=n1⋯nk∣f(x),即 f(x)≡0(modn)。
因此,x 是模 n 的根当且仅当 x 同时是模每个 ni 的根。
第二步:用 CRT 组合计数。 设模 ni 下 f 恰有 ri 个不同的根(剩余类),记为 xi(1),…,xi(ri)。任取一组分量根 (x1(j1),…,xk(jk)),由式 (31.28) 的构造公式唯一确定一个剩余类 xmodn,且由第一步它正是模 n 下的根。反之,任何模 n 的根 x 按 (xmodn1,…,xmodnk) 分解,也唯一对应这样一组分量根。
由于 CRT 是一一对应,不同的分量组合必然产生不同的模 n 剩余类,不存在重复计数。故
#{xmodn:f(x)≡0(modn)}=r1×r2×⋯×rk.
5.2 直觉与特例
- k=2 时:模 n1 有 2 个根、模 n2 有 3 个根,则模 n1n2 恰有 2×3=6 个根——每个「模 n1 的根 × 模 n2 的根」对都通过 CRT 合并成一个根。
- 若某 ri=0(某个分量无根),乘积为 0,整体无根,逻辑自洽。
- 这一性质是 CRT 同构「保根数」的推论,其前提(两两互素、运算分量化)正是式 (31.28)–(31.30) 所刻画的。
六、仓库配套佐证与延伸阅读
本节习题的全部数值计算都依赖两类底层运算,在仓库中均有对应解法文件:
- 扩展欧几里得求模逆:docs/Chap31/31.2.md 给出
EXTENDED-EUCLID 的递归与迭代伪代码(习题 31.2-2 演示了 899 与 493 的具体调用),并证明 gcd(a,n)=gcd(a+kn,n)(习题 31.2-3),后者正是「Mi 与 ni 互素 ⇒ 逆元存在」的严格依据;同文件的 LCM 实现(习题 31.2-8)可用于验证模数乘积。此外 docs/Chap31/Problems/31-1.md 的 BINARY-GCD 提供了不依赖取余的替代 gcd 算法。
- 模幂与欧拉求逆:docs/Chap31/31.6.md 习题 31.6-3 展示 a−1≡aϕ(n)−1(modn),与 CRT 组合求逆互为补充。
- CRT 的实际舞台——RSA:在仓库的章节导航(mkdocs.yml)中,31.5 节之后紧跟 31.7 The RSA public-key cryptosystem;docs/Chap31/31.7.md 习题 31.7-1 演示了模数 n=319 下的加解密全流程。RSA 解密在实践中正是借助 CRT 把模 n=pq 的大指数运算分解为模 p、模 q 的小指数运算来加速,这使本节习题(尤其是 31.5-1、31.5-3)具有直接的实际工程意义。
- 本仓库背景:这是面向《算法导论》第 3 版的习题解答开源仓库(详见 README.md),采用 MkDocs 静态站点 + KaTeX 渲染数学公式,全部章节与本节文件可通过导航树按章索引。本节原文即位于 docs/Chap31/31.5.md。
速查小结:CRT 三步法——① 检验模数两两互素(用 gcd);② 对每个 i 计算 Mi=n/ni 及其模 ni 的逆元,得到 ci;③ 求和 a≡∑aici(modn) 即得唯一剩余类,全部解为该剩余类加任意整数倍 n。这一范式贯穿 31.5 节四道习题,也是后续 RSA 高性能实现的理论基石。