中国剩余定理(CRT)解题实战:CLRS 31.5 节全部习题精解与推导

原创2026-10-14 10:41:20584 阅读
文章标签:文档教程

中国剩余定理(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,n = n_1 n_2 \cdots n_k,

其中 n1,n2,…,nkn_1, n_2, \ldots, n_k 两两互素(pairwise relatively prime)。则映射

a↔(a1,a2,…,ak),ai=a mod ni,a \leftrightarrow (a_1, a_2, \ldots, a_k), \qquad a_i = a \bmod n_i,

是 Zn\mathbb Z_n 与直积 Zn1×Zn2×⋯×Znk\mathbb Z_{n_1} \times \mathbb Z_{n_2} \times \cdots \times \mathbb Z_{n_k} 之间的一一对应(bijection)。

构造公式(式 (31.28)):令 Mi=n/niM_i = n / n_i(即除 nin_i 外其余模数的乘积),取 Mi−1M_i^{-1} 为 MiM_i 模 nin_i 的乘法逆元,记

ci=Mi⋅(Mi−1 mod ni),c_i = M_i \cdot (M_i^{-1} \bmod n_i),

则对任意目标余数组 (a1,…,ak)(a_1, \ldots, a_k),唯一解为

a≡(∑i=1kaici)(modn).a \equiv \left( \sum_{i=1}^{k} a_i c_i \right) \pmod n.

CRT 同构还保持运算:式 (31.29) 保证模 nn 下的加法对应到各分量模 nin_i 下的加法,式 (31.30) 保证模 nn 下的乘法对应到各分量模 nin_i 下的乘法。这两条运算律正是习题 31.5-3 与 31.5-4 的证明基础(文档原句「Based on 31.28–31.30」)。

1.2 前置工具回顾(仓库配套解法)

  • 模逆的计算:CRT 构造需要大量 Mi−1 mod niM_i^{-1} \bmod n_i,其通用算法是扩展欧几里得 EXTENDED-EUCLID,完整伪代码见 docs/Chap31/31.2.md(返回三元组 (d,x,y)(d, x, y) 满足 ax+by=gcd⁡(a,b)ax + by = \gcd(a, b))。
  • 两两互素的判别:docs/Chap31/31.2.md 习题 31.2-9 证明了 n1,…,nkn_1, \ldots, n_k 两两互素当且仅当 gcd⁡\gcd 乘积对互素,这是 CRT 适用性的判据。
  • 模线性方程:单个同余方程 ax≡b(modn)ax \equiv b \pmod n 的解结构见 docs/Chap31/31.4.md,CRT 将「模 nn 的一个方程」分解为「模 nin_i 的 kk 个方程」后逐一求解再合并。

二、习题 31.5-1:两模同余方程组的 CRT 逐步构造

题目:求方程组

x≡4(mod5),x≡5(mod11)x \equiv 4 \pmod 5, \qquad x \equiv 5 \pmod{11}

的全部解。

2.1 代入 CRT 构造公式

模数 n1=5n_1 = 5、n2=11n_2 = 11 互素(gcd⁡(5,11)=1\gcd(5, 11) = 1),n=55n = 55。按式 (31.28),对 i=1,2i = 1, 2 计算 Mi=n/niM_i = n / n_i:

分量 ii 模数 nin_i Mi=n/niM_i = n/n_i Mi mod niM_i \bmod n_i Mi−1 mod niM_i^{-1} \bmod n_i ci=Mi⋅(Mi−1 mod ni)c_i = M_i \cdot (M_i^{-1} \bmod n_i)
1 5 11 1 1(1×1≡1(mod5)1 \times 1 \equiv 1 \pmod 5) 11
2 11 5 5 9(5×9=45≡1(mod11)5 \times 9 = 45 \equiv 1 \pmod{11}) 45

这正是文档中的关键数值:m1=11m_1 = 11,m2=5m_2 = 5;m1−1=1m_1^{-1} = 1,m2−1=9m_2^{-1} = 9;c1=11c_1 = 11,c2=45c_2 = 45(注意文档中 mim_i 取的是「另一个模数」,即与定理中 MiM_i 相同的含义)。

2.2 组合求解

a=(c1a1+c2a2) mod (n1n2)=(11⋅4+45⋅5) mod 55=269 mod 55=49.a = (c_1 a_1 + c_2 a_2) \bmod (n_1 n_2) = (11 \cdot 4 + 45 \cdot 5) \bmod 55 = 269 \bmod 55 = 49.

全部解:x≡49(mod55)x \equiv 49 \pmod{55},即

x=49+55t,t∈Z.x = 49 + 55t, \qquad t \in \mathbb Z.

2.3 验算

49 mod 5=4,49 mod 11=5(49=44+5).49 \bmod 5 = 4, \qquad 49 \bmod 11 = 5 \quad (49 = 44 + 5).

两条同余式同时满足,且模 55 的剩余类唯一,故 49+55t49 + 55t 即全部解集。方法要点:每个 cic_i 的作用是「只在该分量对应的模 nin_i 下等于 1、在其余模 njn_j 下等于 0」,从而 aicia_i c_i 精确地贡献目标余数而不互相干扰。


三、习题 31.5-2:三模同余方程组的求解

题目:求所有被 9、8、7 除分别余 1、2、3 的整数 xx,即

x≡1(mod9),x≡2(mod8),x≡3(mod7).x \equiv 1 \pmod 9, \qquad x \equiv 2 \pmod 8, \qquad x \equiv 3 \pmod 7.

3.1 通解形式

9,8,79, 8, 7 两两互素,n=9×8×7=504n = 9 \times 8 \times 7 = 504。文档给出的答案是

x=10+504i,i∈Z,x = 10 + 504i, \qquad i \in \mathbb Z,

等价地 x≡10(mod504)x \equiv 10 \pmod{504}。

验算:

10 mod 9=1,10 mod 8=2,10 mod 7=3.10 \bmod 9 = 1, \qquad 10 \bmod 8 = 2, \qquad 10 \bmod 7 = 3.

三条同余式全部满足;由于  mod 504\bmod 504 的解唯一,10+504i10 + 504i(i∈Zi \in \mathbb Z)即全部解。

3.2 用构造公式独立复现 10

作为练习,我们按式 (31.28) 完整构造(这也验证了 31.5-2 的答案来源):

分量 ii nin_i Mi=504/niM_i = 504/n_i Mi−1 mod niM_i^{-1} \bmod n_i ci=Mi⋅(Mi−1)c_i = M_i \cdot (M_i^{-1})
1 9 56 2−1≡5(mod9)2^{-1} \equiv 5 \pmod 9 56×5=28056 \times 5 = 280
2 8 63 7−1≡7(mod8)7^{-1} \equiv 7 \pmod 8 63×7=44163 \times 7 = 441
3 7 72 2−1≡4(mod7)2^{-1} \equiv 4 \pmod 7 72×4=28872 \times 4 = 288

于是

a=(1×280+2×441+3×288) mod 504=2026 mod 504=10,a = (1 \times 280 + 2 \times 441 + 3 \times 288) \bmod 504 = 2026 \bmod 504 = 10,

与文档答案一致。其中各逆元可快速核对:2×5=10≡1(mod9)2 \times 5 = 10 \equiv 1 \pmod 9,7×7=49≡1(mod8)7 \times 7 = 49 \equiv 1 \pmod 8,2×4=8≡1(mod7)2 \times 4 = 8 \equiv 1 \pmod 7。

方法要点:分量数 kk 增多时,构造公式完全不变,只是求和项数从 2 变成 kk;每个 MiM_i 始终是与 nin_i 互素的(因 nin_i 与其余 njn_j 两两互素),所以 Mi−1 mod niM_i^{-1} \bmod n_i 必定存在——这正是 31.5-3 要论证的核心事实。


四、习题 31.5-3:CRT 同构下的逆元保持性

题目:在 Theorem 31.27 的定义下证明:若 gcd⁡(a,n)=1\gcd(a, n) = 1,则

(a−1 mod n)↔((a1−1 mod n1),  (a2−1 mod n2),  …,  (ak−1 mod nk)).(a^{-1} \bmod n) \leftrightarrow \bigl((a_1^{-1} \bmod n_1),\; (a_2^{-1} \bmod n_2),\; \ldots,\; (a_k^{-1} \bmod n_k)\bigr).

4.1 论证思路

第一步:每个分量上的逆元都存在。 文档给出的关键观察是

gcd⁡(a,n)=1  ⇒  gcd⁡(a,ni)=1(∀ i).\gcd(a, n) = 1 \;\Rightarrow\; \gcd(a, n_i) = 1 \quad (\forall\, i).

理由:ni∣nn_i \mid n,任何同时整除 aa 与 nin_i 的整数也同时整除 aa 与 nn,故 gcd⁡(a,ni)\gcd(a, n_i) 必整除 gcd⁡(a,n)=1\gcd(a, n) = 1。因此每个 ai=a mod nia_i = a \bmod n_i 在 Zni∗\mathbb Z_{n_i}^* 中都是单位,唯一逆元 ai−1 mod nia_i^{-1} \bmod n_i 存在。

第二步:用乘法运算律(式 (31.30))传递。 由逆元定义,a⋅a−1≡1(modn)a \cdot a^{-1} \equiv 1 \pmod n。CRT 同构把模 nn 的乘法对应到各分量乘法,即

a⋅a−1 mod n↔(a1⋅b1 mod n1,  …,  ak⋅bk mod nk),a \cdot a^{-1} \bmod n \leftrightarrow \bigl(a_1 \cdot b_1 \bmod n_1,\; \ldots,\; a_k \cdot b_k \bmod n_k\bigr),

其中 bi=a−1 mod nib_i = a^{-1} \bmod n_i。等号右侧必须等于单位元的分量表示 (1,…,1)(1, \ldots, 1),于是每个分量满足

ai⋅bi≡1(modni),a_i \cdot b_i \equiv 1 \pmod{n_i},

即 bi≡ai−1(modni)b_i \equiv a_i^{-1} \pmod{n_i}。再由 CRT 一一对应性,模 nn 下 a−1a^{-1} 的剩余类恰好对应各分量逆元的元组。

4.2 结论

a−1 mod n  ↔  (a1−1 mod n1,…,ak−1 mod nk).a^{-1} \bmod n \;\leftrightarrow\; \bigl(a_1^{-1} \bmod n_1, \ldots, a_k^{-1} \bmod n_k\bigr).

实战意义:当 nn 为大合数(如 RSA 模数)时,求「模 nn 的大逆元」可分解为对每个小模 nin_i 求逆再经 CRT 还原,显著降低单次运算规模。模逆本身也可用 docs/Chap31/31.6.md 习题 31.6-3 的欧拉定理方法 a−1≡aϕ(n)−1(modn)a^{-1} \equiv a^{\phi(n)-1} \pmod n 计算,两种途径殊途同归。


五、习题 31.5-4:多项式根的个数乘积律

题目:在 Theorem 31.27 的定义下,证明对任意多项式 ff,方程 f(x)≡0(modn)f(x) \equiv 0 \pmod n 的根的个数等于以下 kk 个方程根数之积:

f(x)≡0(modn1),f(x)≡0(modn2),…,f(x)≡0(modnk).f(x) \equiv 0 \pmod{n_1}, \quad f(x) \equiv 0 \pmod{n_2}, \quad \ldots, \quad f(x) \equiv 0 \pmod{n_k}.

文档给出的提示为「Based on 31.28–31.30」,即基于 CRT 的构造公式与分量运算律。

5.1 论证思路

第一步:根的「可分解性」。 对任意整数 xx:

  • 若 f(x)≡0(modn)f(x) \equiv 0 \pmod n,则因 ni∣nn_i \mid n,必有 f(x)≡0(modni)f(x) \equiv 0 \pmod{n_i}(对所有 ii);
  • 反之,若 f(x)≡0(modni)f(x) \equiv 0 \pmod{n_i} 对所有 ii 成立,则每个 ni∣f(x)n_i \mid f(x);由于 n1,…,nkn_1, \ldots, n_k 两两互素,乘积 n=n1⋯nk∣f(x)n = n_1 \cdots n_k \mid f(x),即 f(x)≡0(modn)f(x) \equiv 0 \pmod n。

因此,xx 是模 nn 的根当且仅当 xx 同时是模每个 nin_i 的根。

第二步:用 CRT 组合计数。 设模 nin_i 下 ff 恰有 rir_i 个不同的根(剩余类),记为 xi(1),…,xi(ri)x_i^{(1)}, \ldots, x_i^{(r_i)}。任取一组分量根 (x1(j1),…,xk(jk))(x_1^{(j_1)}, \ldots, x_k^{(j_k)}),由式 (31.28) 的构造公式唯一确定一个剩余类 x mod nx \bmod n,且由第一步它正是模 nn 下的根。反之,任何模 nn 的根 xx 按 (x mod n1,…,x mod nk)(x \bmod n_1, \ldots, x \bmod n_k) 分解,也唯一对应这样一组分量根。

由于 CRT 是一一对应,不同的分量组合必然产生不同的模 nn 剩余类,不存在重复计数。故

#{ x mod n:f(x)≡0(modn) }=r1×r2×⋯×rk.\#\{\,x \bmod n : f(x) \equiv 0 \pmod n\,\} = r_1 \times r_2 \times \cdots \times r_k.

5.2 直觉与特例

  • k=2k = 2 时:模 n1n_1 有 2 个根、模 n2n_2 有 3 个根,则模 n1n2n_1 n_2 恰有 2×3=62 \times 3 = 6 个根——每个「模 n1n_1 的根 × 模 n2n_2 的根」对都通过 CRT 合并成一个根。
  • 若某 ri=0r_i = 0(某个分量无根),乘积为 0,整体无根,逻辑自洽。
  • 这一性质是 CRT 同构「保根数」的推论,其前提(两两互素、运算分量化)正是式 (31.28)–(31.30) 所刻画的。

六、仓库配套佐证与延伸阅读

本节习题的全部数值计算都依赖两类底层运算,在仓库中均有对应解法文件:

  • 扩展欧几里得求模逆:docs/Chap31/31.2.md 给出 EXTENDED-EUCLID 的递归与迭代伪代码(习题 31.2-2 演示了 899899 与 493493 的具体调用),并证明 gcd⁡(a,n)=gcd⁡(a+kn,n)\gcd(a, n) = \gcd(a + kn, n)(习题 31.2-3),后者正是「MiM_i 与 nin_i 互素 ⇒ 逆元存在」的严格依据;同文件的 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)a^{-1} \equiv a^{\phi(n)-1} \pmod n,与 CRT 组合求逆互为补充。
  • CRT 的实际舞台——RSA:在仓库的章节导航(mkdocs.yml)中,31.5 节之后紧跟 31.7 The RSA public-key cryptosystem;docs/Chap31/31.7.md 习题 31.7-1 演示了模数 n=319n = 319 下的加解密全流程。RSA 解密在实践中正是借助 CRT 把模 n=pqn = pq 的大指数运算分解为模 pp、模 qq 的小指数运算来加速,这使本节习题(尤其是 31.5-1、31.5-3)具有直接的实际工程意义。
  • 本仓库背景:这是面向《算法导论》第 3 版的习题解答开源仓库(详见 README.md),采用 MkDocs 静态站点 + KaTeX 渲染数学公式,全部章节与本节文件可通过导航树按章索引。本节原文即位于 docs/Chap31/31.5.md。

速查小结:CRT 三步法——① 检验模数两两互素(用 gcd);② 对每个 ii 计算 Mi=n/niM_i = n/n_i 及其模 nin_i 的逆元,得到 cic_i;③ 求和 a≡∑aici(modn)a \equiv \sum a_i c_i \pmod n 即得唯一剩余类,全部解为该剩余类加任意整数倍 nn。这一范式贯穿 31.5 节四道习题,也是后续 RSA 高性能实现的理论基石。

登录后查看全文
CLRS