13 中国剩余定理 CRT
学习目标
学完这一节，你应该能够：
* 理解中国剩余定理解决什么问题；
* 理解经典 CRT 为什么要求模数两两互质；
* 理解“只对一个同余条件起作用的开关”怎样构造；
* 一步一步推出 CRT 的构造公式；
* 验证构造出的解确实满足所有同余条件；
* 理解为什么解在模所有模数乘积的意义下唯一；
* 看懂经典 CRT 的 C++ 实现。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
1. CRT 要解决什么问题
有时一个整数需要同时满足多个余数条件。
例如求整数 xxx，满足：
x≡2(mod3)x\equiv2\pmod3 x≡2(mod3)
x≡3(mod5)x\equiv3\pmod5 x≡3(mod5)
x≡2(mod7)x\equiv2\pmod7 x≡2(mod7)
也就是说：
* xxx 除以 3 余 2；
* xxx 除以 5 余 3；
* xxx 除以 7 余 2。
枚举可以发现：
x=23x=23 x=23
因为：
23 mod 3=223\bmod3=2 23mod3=2
23 mod 5=323\bmod5=3 23mod5=3
23 mod 7=223\bmod7=2 23mod7=2
中国剩余定理就是用来系统解决这类问题的。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 经典中国剩余定理的条件
考虑：
x≡a1(modm1)x\equiv a_1\pmod{m_1} x≡a1 (modm1 )
x≡a2(modm2)x\equiv a_2\pmod{m_2} x≡a2 (modm2 )
一直到：
x≡ak(modmk)x\equiv a_k\pmod{m_k} x≡ak (modmk )
经典 CRT 要求：
m1,m2,…,mkm_1,m_2,\dots,m_k m1 ,m2 ,…,mk
两两互质。
“两两互质”表示任意两个不同模数都满足：
gcd(mi,mj)=1\gcd(m_i,m_j)=1 gcd(mi ,mj )=1
在这个条件下：
1. 方程组一定有解；
2. 所有解在模：
M=m1m2⋯mkM=m_1m_2\cdots m_k M=m1 m2 ⋯mk
意义下属于同一个剩余类。
下面从“怎样构造一个解”开始。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 先构造一个只负责第一个条件的数
先看三个模数：
m1,m2,m3m_1,m_2,m_3 m1 ,m2 ,m3
希望构造一个数 E1E_1E1 ，满足：
E1≡1(modm1)E_1\equiv1\pmod{m_1} E1 ≡1(modm1 )
但是：
E1≡0(modm2)E_1\equiv0\pmod{m_2} E1 ≡0(modm2 )
并且：
E1≡0(modm3)E_1\equiv0\pmod{m_3} E1 ≡0(modm3 )
为什么这样构造有用？
因为把它乘上 a1a_1a1 后：
模 m1m_1m1 ：
a1E1≡a1(modm1)a_1E_1\equiv a_1\pmod{m_1} a1 E1 ≡a1 (modm1 )
模 m2m_2m2 ：
a1E1≡0(modm2)a_1E_1\equiv0\pmod{m_2} a1 E1 ≡0(modm2 )
模 m3m_3m3 ：
a1E1≡0(modm3)a_1E_1\equiv0\pmod{m_3} a1 E1 ≡0(modm3 )
所以：
> a1E1a_1E_1a1 E1 只负责第一个余数条件，不会干扰另外两个条件。
可以把 E1E_1E1 理解成“只打开第一个条件的开关”。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 怎样先让它在其他模数下都等于 0
为了让：
E1≡0(modm2)E_1\equiv0\pmod{m_2} E1 ≡0(modm2 )
以及：
E1≡0(modm3)E_1\equiv0\pmod{m_3} E1 ≡0(modm3 )
先取：
M1=m2m3M_1=m_2m_3 M1 =m2 m3
因为 M1M_1M1 含有因子 m2m_2m2 ：
m2∣M1m_2\mid M_1 m2 ∣M1
所以：
M1≡0(modm2)M_1\equiv0\pmod{m_2} M1 ≡0(modm2 )
同理：
M1≡0(modm3)M_1\equiv0\pmod{m_3} M1 ≡0(modm3 )
这样，“在其他模数下等于 0”的要求已经满足。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
5. 但是 M1M_1M1 在模 M1M_1M1 下未必等于 1
我们还希望：
E1≡1(modm1)E_1\equiv1\pmod{m_1} E1 ≡1(modm1 )
但是：
M1=m2m3M_1=m_2m_3 M1 =m2 m3
模 m1m_1m1 后一般不一定等于 1。
所以再乘一个整数 t1t_1t1 ，希望：
M1t1≡1(modm1)M_1t_1\equiv1\pmod{m_1} M1 t1 ≡1(modm1 )
也就是说，t1t_1t1 应该是 M1M_1M1 在模 m1m_1m1 下的逆元。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
6. 为什么 M1M_1M1 的逆元一定存在
因为：
m1,m2,m3m_1,m_2,m_3 m1 ,m2 ,m3
两两互质。
假设 M1M_1M1 和 m1m_1m1 有一个大于 1 的公共质因子 qqq。
那么：
q∣M1=m2m3q\mid M_1=m_2m_3 q∣M1 =m2 m3
因为 qqq 是质数，所以 qqq 必须整除 m2m_2m2 或 m3m_3m3 中至少一个。
同时又有：
q∣m1q\mid m_1 q∣m1
这就说明 m1m_1m1 与 m2m_2m2 或 m3m_3m3 有大于 1 的公共因子，与“两两互质”矛盾。
所以：
gcd(M1,m1)=1\gcd(M_1,m_1)=1 gcd(M1 ,m1 )=1
因此 M1M_1M1 在模 m1m_1m1 下存在逆元。
可以找到 t1t_1t1 ，使：
M1t1≡1(modm1)M_1t_1\equiv1\pmod{m_1} M1 t1 ≡1(modm1 )
于是令：
E1=M1t1E_1=M_1t_1 E1 =M1 t1
就有：
E1≡1(modm1)E_1\equiv1\pmod{m_1} E1 ≡1(modm1 )
并且因为 E1E_1E1 仍然含有因子 M1=m2m3M_1=m_2m_3M1 =m2 m3 ：
E1≡0(modm2)E_1\equiv0\pmod{m_2} E1 ≡0(modm2 )
E1≡0(modm3)E_1\equiv0\pmod{m_3} E1 ≡0(modm3 )
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
7. 同样构造其他“开关”
令：
M=m1m2m3M=m_1m_2m_3 M=m1 m2 m3
定义：
M1=Mm1M_1=\frac{M}{m_1} M1 =m1 M
M2=Mm2M_2=\frac{M}{m_2} M2 =m2 M
M3=Mm3M_3=\frac{M}{m_3} M3 =m3 M
分别寻找：
M1t1≡1(modm1)M_1t_1\equiv1\pmod{m_1} M1 t1 ≡1(modm1 )
M2t2≡1(modm2)M_2t_2\equiv1\pmod{m_2} M2 t2 ≡1(modm2 )
M3t3≡1(modm3)M_3t_3\equiv1\pmod{m_3} M3 t3 ≡1(modm3 )
再令：
E1=M1t1E_1=M_1t_1 E1 =M1 t1
E2=M2t2E_2=M_2t_2 E2 =M2 t2
E3=M3t3E_3=M_3t_3 E3 =M3 t3
那么：
* E1E_1E1 只在模 m1m_1m1 下等于 1，在另外两个模数下等于 0；
* E2E_2E2 只在模 m2m_2m2 下等于 1，在另外两个模数下等于 0；
* E3E_3E3 只在模 m3m_3m3 下等于 1，在另外两个模数下等于 0。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
8. 把这些“开关”加起来
构造：
x=a1E1+a2E2+a3E3x=a_1E_1+a_2E_2+a_3E_3 x=a1 E1 +a2 E2 +a3 E3
模 m1m_1m1 ：
x≡a1⋅1+a2⋅0+a3⋅0(modm1)x\equiv a_1\cdot1+a_2\cdot0+a_3\cdot0\pmod{m_1} x≡a1 ⋅1+a2 ⋅0+a3 ⋅0(modm1 )
所以：
x≡a1(modm1)x\equiv a_1\pmod{m_1} x≡a1 (modm1 )
模 m2m_2m2 ：
x≡a1⋅0+a2⋅1+a3⋅0(modm2)x\equiv a_1\cdot0+a_2\cdot1+a_3\cdot0\pmod{m_2} x≡a1 ⋅0+a2 ⋅1+a3 ⋅0(modm2 )
所以：
x≡a2(modm2)x\equiv a_2\pmod{m_2} x≡a2 (modm2 )
模 m3m_3m3 ：
x≡a1⋅0+a2⋅0+a3⋅1(modm3)x\equiv a_1\cdot0+a_2\cdot0+a_3\cdot1\pmod{m_3} x≡a1 ⋅0+a2 ⋅0+a3 ⋅1(modm3 )
所以：
x≡a3(modm3)x\equiv a_3\pmod{m_3} x≡a3 (modm3 )
因此这个 xxx 同时满足三个同余条件。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
9. 推广到 KKK 个同余条件
令：
M=m1m2⋯mkM=m_1m_2\cdots m_k M=m1 m2 ⋯mk
对每个 iii 定义：
Mi=MmiM_i=\frac{M}{m_i} Mi =mi M
因为所有模数两两互质，所以：
gcd(Mi,mi)=1\gcd(M_i,m_i)=1 gcd(Mi ,mi )=1
因此 MiM_iMi 在模 mim_imi 下存在逆元。
设 tit_iti 满足：
Miti≡1(modmi)M_it_i\equiv1\pmod{m_i} Mi ti ≡1(modmi )
那么：
Ei=MitiE_i=M_it_i Ei =Mi ti
满足：
Ei≡1(modmi)E_i\equiv1\pmod{m_i} Ei ≡1(modmi )
对于任意 j≠ij\ne ij=i，因为 MiM_iMi 中仍然含有因子 mjm_jmj ，所以：
Ei≡0(modmj)E_i\equiv0\pmod{m_j} Ei ≡0(modmj )
因此构造：
x=a1M1t1+a2M2t2+⋯+akMktkx=a_1M_1t_1+a_2M_2t_2+\cdots+a_kM_kt_k x=a1 M1 t1 +a2 M2 t2 +⋯+ak Mk tk
就能同时满足全部同余条件。
也可以用求和符号简写为：
x≡∑i=1kaiMiti(modM)\boxed{x\equiv\sum_{i=1}^{k}a_iM_it_i\pmod M} x≡i=1∑k ai Mi ti (modM)
这里的 ∑\sum∑ 只是表示把从 i=1i=1i=1 到 i=ki=ki=k 的这些项全部加起来。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
10. 用具体例子完整构造一次
求：
x≡2(mod3)x\equiv2\pmod3 x≡2(mod3)
x≡3(mod5)x\equiv3\pmod5 x≡3(mod5)
x≡2(mod7)x\equiv2\pmod7 x≡2(mod7)
三个模数：
3,5,73,5,7 3,5,7
两两互质。
先算：
M=3×5×7=105M=3\times5\times7=105 M=3×5×7=105
10.1 第一个条件
M1=1053=35M_1=\frac{105}{3}=35 M1 =3105 =35
寻找 t1t_1t1 ，使：
35t1≡1(mod3)35t_1\equiv1\pmod3 35t1 ≡1(mod3)
因为：
35≡2(mod3)35\equiv2\pmod3 35≡2(mod3)
所以：
2t1≡1(mod3)2t_1\equiv1\pmod3 2t1 ≡1(mod3)
取：
t1=2t_1=2 t1 =2
因为：
2×2=4≡1(mod3)2\times2=4\equiv1\pmod3 2×2=4≡1(mod3)
所以：
E1=35×2=70E_1=35\times2=70 E1 =35×2=70
10.2 第二个条件
M2=1055=21M_2=\frac{105}{5}=21 M2 =5105 =21
寻找 t2t_2t2 ，使：
21t2≡1(mod5)21t_2\equiv1\pmod5 21t2 ≡1(mod5)
因为：
21≡1(mod5)21\equiv1\pmod5 21≡1(mod5)
所以：
t2=1t_2=1 t2 =1
因此：
E2=21E_2=21 E2 =21
10.3 第三个条件
M3=1057=15M_3=\frac{105}{7}=15 M3 =7105 =15
寻找 t3t_3t3 ，使：
15t3≡1(mod7)15t_3\equiv1\pmod7 15t3 ≡1(mod7)
因为：
15≡1(mod7)15\equiv1\pmod7 15≡1(mod7)
所以：
t3=1t_3=1 t3 =1
因此：
E3=15E_3=15 E3 =15
10.4 合并
构造：
x=2E1+3E2+2E3x=2E_1+3E_2+2E_3 x=2E1 +3E2 +2E3
代入：
x=2×70+3×21+2×15x=2\times70+3\times21+2\times15 x=2×70+3×21+2×15
所以：
x=140+63+30=233x=140+63+30=233 x=140+63+30=233
而：
233=105×2+23233=105\times2+23 233=105×2+23
所以：
233≡23(mod105)233\equiv23\pmod{105} 233≡23(mod105)
最小非负解是：
x=23\boxed{x=23} x=23
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
11. 为什么解在模 MMM 下唯一
假设 x1x_1x1 和 x2x_2x2 都满足所有同余条件。
那么对于每个 iii：
x1≡ai(modmi)x_1\equiv a_i\pmod{m_i} x1 ≡ai (modmi )
并且：
x2≡ai(modmi)x_2\equiv a_i\pmod{m_i} x2 ≡ai (modmi )
所以：
x1≡x2(modmi)x_1\equiv x_2\pmod{m_i} x1 ≡x2 (modmi )
根据同余的定义：
mi∣(x1−x2)m_i\mid(x_1-x_2) mi ∣(x1 −x2 )
也就是说，每一个：
m1,m2,…,mkm_1,m_2,\dots,m_k m1 ,m2 ,…,mk
都整除：
x1−x2x_1-x_2 x1 −x2
接下来需要说明：为什么它们的乘积也整除这个差。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
12. 一个需要用到的小结论
如果：
gcd(u,v)=1\gcd(u,v)=1 gcd(u,v)=1
并且：
u∣Nu\mid N u∣N
v∣Nv\mid N v∣N
那么：
uv∣Nuv\mid N uv∣N
证明如下。
因为：
u∣Nu\mid N u∣N
所以存在整数 sss，使：
N=usN=us N=us
又因为：
v∣Nv\mid N v∣N
所以：
v∣usv\mid us v∣us
由：
gcd(u,v)=1\gcd(u,v)=1 gcd(u,v)=1
根据裴蜀定理，存在整数 A,BA,BA,B，使：
Au+Bv=1Au+Bv=1 Au+Bv=1
两边乘 sss：
Aus+Bvs=sAus+Bvs=s Aus+Bvs=s
因为：
v∣usv\mid us v∣us
所以：
v∣Ausv\mid Aus v∣Aus
而：
v∣Bvsv\mid Bvs v∣Bvs
因此：
v∣sv\mid s v∣s
所以存在整数 ttt，使：
s=vts=vt s=vt
于是：
N=us=uvtN=us=uvt N=us=uvt
因此：
uv∣Nuv\mid N uv∣N
小结论得证。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
13. 用这个结论证明 CRT 的唯一性
因为：
m1,m2,…,mkm_1,m_2,\dots,m_k m1 ,m2 ,…,mk
两两互质，而且每个 mim_imi 都整除：
x1−x2x_1-x_2 x1 −x2
所以先由：
m1∣(x1−x2)m_1\mid(x_1-x_2) m1 ∣(x1 −x2 )
和：
m2∣(x1−x2)m_2\mid(x_1-x_2) m2 ∣(x1 −x2 )
再利用上一小节的小结论，得到：
m1m2∣(x1−x2)m_1m_2\mid(x_1-x_2) m1 m2 ∣(x1 −x2 )
接下来还需要确认：
gcd(m1m2,m3)=1\gcd(m_1m_2,m_3)=1 gcd(m1 m2 ,m3 )=1
为什么？
如果 m1m2m_1m_2m1 m2 和 m3m_3m3 有一个公共质因子 qqq，那么 qqq 整除 m1m2m_1m_2m1 m2 ，所以 qqq 至少整除 m1,m2m_1,m_2m1 ,m2 中的一个。
同时 qqq 又整除 m3m_3m3 。
这就会导致 m3m_3m3 与 m1m_1m1 或 m2m_2m2 不互质，与“两两互质”矛盾。
所以：
gcd(m1m2,m3)=1\gcd(m_1m_2,m_3)=1 gcd(m1 m2 ,m3 )=1
于是再利用上一小节的小结论：
m1m2m3∣(x1−x2)m_1m_2m_3\mid(x_1-x_2) m1 m2 m3 ∣(x1 −x2 )
继续同样的过程，每加入一个新的 mim_imi ，它都与前面已经相乘得到的模数乘积互质。
因此最终：
m1m2⋯mk∣(x1−x2)m_1m_2\cdots m_k\mid(x_1-x_2) m1 m2 ⋯mk ∣(x1 −x2 )
也就是：
M∣(x1−x2)M\mid(x_1-x_2) M∣(x1 −x2 )
根据同余的定义：
x1≡x2(modM)\boxed{x_1\equiv x_2\pmod M} x1 ≡x2 (modM)
所以：
> 所有解在模 MMM 的意义下属于同一个剩余类。
这就是“解在模 MMM 下唯一”的含义。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
14. C++ 中怎样求 TIT_ITI
tit_iti 是 MiM_iMi 在模 mim_imi 下的逆元。
前面已经学过，可以使用扩展欧几里得算法求逆元：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
15. 经典 CRT 模板
下面模板假设所有模数的乘积 MMM 能够放进 long long。
这里使用 __int128 计算中间乘积，是为了降低 a[i] * Mi * ti 在乘法过程中溢出的风险。
如果连所有模数的乘积 MMM 本身都超过 long long，还需要进一步改写数据类型和算法实现。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
16. 代码逐步对应公式
先计算：
对应：
M=m1m2⋯mkM=m_1m_2\cdots m_k M=m1 m2 ⋯mk
然后：
对应：
Mi=MmiM_i=\frac{M}{m_i} Mi =mi M
接着：
对应：
Miti≡1(modmi)M_it_i\equiv1\pmod{m_i} Mi ti ≡1(modmi )
最后：
在数学上对应不断加入：
aiMitia_iM_it_i ai Mi ti
最终得到：
x≡∑i=1kaiMiti(modM)x\equiv\sum_{i=1}^{k}a_iM_it_i\pmod M x≡i=1∑k ai Mi ti (modM)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
17. 为什么经典 CRT 强调“两两互质”
构造中的关键一步是：
Mi=MmiM_i=\frac M{m_i} Mi =mi M
必须在模 mim_imi 下存在逆元。
这要求：
gcd(Mi,mi)=1\gcd(M_i,m_i)=1 gcd(Mi ,mi )=1
当所有模数两两互质时，这个条件自动成立。
如果模数不两两互质，就不能直接使用这里的经典 CRT 构造。
那种情况需要另外判断各个同余条件是否相容，并使用更一般的方法处理，不属于本章的经典 CRT 范围。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
18. 小练习
练习 1
为什么希望构造：
Ei≡1(modmi)E_i\equiv1\pmod{m_i} Ei ≡1(modmi )
同时对于 j≠ij\ne ij=i：
Ei≡0(modmj)E_i\equiv0\pmod{m_j} Ei ≡0(modmj )
练习 2
为什么：
Mi=MmiM_i=\frac M{m_i} Mi =mi M
在模其他 mjm_jmj 下自动等于 0？
练习 3
为什么 MiM_iMi 在模 mim_imi 下存在逆元？
练习 4
求最小非负整数 xxx：
x≡1(mod3)x\equiv1\pmod3 x≡1(mod3)
x≡2(mod5)x\equiv2\pmod5 x≡2(mod5)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
19. 答案
练习 1
因为这样 aiEia_iE_iai Ei 只负责第 iii 个余数条件，不会影响其他条件。
练习 2
当 j≠ij\ne ij=i 时，MiM_iMi 的乘积中仍然包含因子 mjm_jmj ，所以：
mj∣Mim_j\mid M_i mj ∣Mi
因此：
Mi≡0(modmj)M_i\equiv0\pmod{m_j} Mi ≡0(modmj )
练习 3
因为所有模数两两互质，所以：
gcd(Mi,mi)=1\gcd(M_i,m_i)=1 gcd(Mi ,mi )=1
根据逆元存在条件，MiM_iMi 在模 mim_imi 下存在逆元。
练习 4
满足：
x≡1(mod3)x\equiv1\pmod3 x≡1(mod3)
的数有：
1,4,7,10,…1,4,7,10,\dots 1,4,7,10,…
其中：
7≡2(mod5)7\equiv2\pmod5 7≡2(mod5)
所以最小非负解是：
7\boxed{7} 7
