中国剩余定理

问题形式

方程组如下（以三个模数为例）：

1
2
3
x ≡ a1 (mod n1)
x ≡ a2 (mod n2)
x ≡ a3 (mod n3)

其中 n1, n2, n3 两两互质，N = n1 * n2 * n3，则在 [0, N-1] 内存在唯一解

物不知数

一个整数，除以 3 余 2，除以 5 余 3，除以 7 余 2，求该数

模数：3, 5, 7，两两互质，N = 3 * 5 * 7 = 105

1. 构造基数框架

对每个模数 ni，我们需找一个数 Mi 满足：

1
2
Mi ≡ 1 (mod ni)
Mi ≡ 0 (mod 其他所有模数)

构造方法：令 Ni = N / ni，求出 Ni 模 ni 的逆元 yi，使得 (Ni * yi) ≡ 1 (mod ni)，则 Mi = Ni * yi

2. 逐项计算

① n1 = 3，N1 = 105 / 3 = 35

求 35 mod 3 的逆元：35 ≡ 2 (mod 3)

在模 3 的世界里，35 和 2 是等价的

因此，”求 35 模 3 的逆元” 就变成了 “求 2 模 3 的逆元”

2 * 2 = 4 ≡ 1 (mod 3)，逆元 y1 = 2

基数：M1 = 35 * 2 = 70

② n2 = 5，N2 = 105 / 5 = 21

21 ≡ 1 (mod 5)，逆元 y2 = 1

基数：M2 = 21 * 1 = 21

③ n3 = 7，N3 = 105 / 7 = 15

15 ≡ 1 (mod 7)，逆元 y3 = 1

基础：M3 = 15 * 1 = 15

3. 合成解

1
2
3
4
x = a1*M1 + a2*M2 + a3*M3
  = 2*70 + 3*21 + 2*15
  = 140 + 63 + 30
  = 233

模 105 得到最小正整数解：

1
x = 233 mod 105 = 23