中国剩余定理（CRT）

数学与数论 · 孙子算经 · 合并同余组

今有物不知其数

《孙子算经》：「今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？」翻译成同余组：x ≡ 2 (mod 3)、x ≡ 3 (mod 5)、x ≡ 2 (mod 7)。中国剩余定理断言：只要模两两互质，这样的同余组在 mod M（M = 3·5·7 = 105）意义下必有唯一解——而且解可以直接构造出来。

给每条同余造一个「专属项」

三步走。①有声音：取 Mᵢ = M / mᵢ（其余模之积），它对别的模取模都是 0、只在第 i 条同余里「有声音」。②校准成 1：声音大小是 Mᵢ mod mᵢ，未必是 1——用扩展欧几里得求逆元 tᵢ = Mᵢ⁻¹ (mod mᵢ) 把它校准成 1。③点菜：要余数 rᵢ，就乘 rᵢ——专属项 rᵢ·Mᵢ·tᵢ 在第 i 条同余下 ≡ rᵢ、其余同余下 ≡ 0。三项相加，每条同余各取所需互不打扰，再 mod M 收进最小非负解。

点「下一步」看这张构造表逐行填出 Mᵢ → tᵢ → 项（黄色高亮是每一步引用的格子），最后合计 233、归约得 x = 23。右侧代码随每一步同步高亮。

	r	m
同余①	2	3
同余②	3	5
同余③	2	7
合计

今有物不知其数：x≡2 (mod 3)、x≡3 (mod 5)、x≡2 (mod 7)，模两两互质 → M = 3·5·7 = 105，解在 mod 105 内唯一。给每条同余造一个「专属项」

1function crt(rs: number[], ms: number[]): number {
const M = ms.reduce((p, m) => p * m, 1); // 模两两互质
let x = 0;
for (let i = 0; i < ms.length; i++) {
  const Mi = M / ms[i];             // 其余模之积：异模下 ≡ 0
  const ti = modInverse(Mi, ms[i]); // 扩欧求逆：本模下校准成 1
  x += rs[i] * Mi * ti;             // 该同余的专属项
}
return x % M;                       // 合并，mod M 内唯一
10}

同余组x≡2 (mod 3)、x≡3 (mod 5)、x≡2 (mod 7)

M3·5·7 = 105

1 / 12

为什么唯一，用在哪里

前提：模两两互质（否则要用扩展 CRT 合并）。
构造：x = Σ rᵢ·Mᵢ·tᵢ (mod M)，其中 Mᵢ = M/mᵢ、tᵢ = Mᵢ⁻¹ (mod mᵢ)。
唯一性：两个解之差被每个 mᵢ 整除 → 被 M 整除，故 mod M 内唯一，通解 x + k·M。
例：23、128、233… 都满足孙子问题，mod 105 下同一个解。

工程里 CRT 是「拆大为小」的合并器：RSA-CRT 把 mod n=p·q 的解密幂运算拆到 mod p、mod q 里各自用快速幂算（指数还能先对 φ 取模），再用 CRT 合并，约四倍提速；竞赛里则用多个小质数模各自计算、CRT 拼回大答案，避开大数运算。数论这条线到此闭环：筛法找质数 → gcd/扩欧给逆元 → 快速幂做模幂 → CRT 合并同余。

算法可视化

中国剩余定理（CRT）

今有物不知其数

给每条同余造一个「专属项」

为什么唯一，用在哪里