中国剩余定理(CRT)
今有物，不知其数，三三数之，剩二；五五数之，剩三；七七数之，剩二。问物几何 ——《孙子算经》
答为“23”。也就是求同余式组 x≡2 （mod3），x≡3 （mod5 ），x≡2 （mod7）的正整数解。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。不难看出，题中3,5,7分别是互质的。具体解法是这样的
1、找出三个数：从3和5的公倍数中找出被7除余1的最小数15，从3和7的公倍数中找出被5除余1 的最小数21，最后从5和7的公倍数中找出除3余1的最小数70。
2、用15乘以2（2为最终结果除以7的余数），用21乘以3（3为最终结果除以5的余数），同理，用70乘以2（2为最终结果除以3的余数），然后把三个乘积相加15∗2+21∗3+70∗2得到和233。
3、用233除以3、5、7的最小公倍数105，得到余数23，这个余数23就是符合条件的最小数。
换成公式：
x ≡2(mod 3)
x ≡3(mod 5)
x ≡2(mod 7)
则进一步得
lcm(5,7)·k≡1(mod 3) →70 ≡1(mod 3)
lcm(3,7)·k≡1(mod 5) →21 ≡1(mod 5)
lcm(3,5)·k≡1(mod 7) →15 ≡1(mod 7)
所以
70×2+21×3+15×2 ≡ x (mod(lcm(3,5,7)))
233 ≡x (mod 105)
得到x=23+105k(k ∈Z) 。这里x的取值有无数多个，当k==0时最小为23，满足题意。
--同余的解法： 因M除以3和7都余2，有等差数列2+21N满足除以3和7都余2，
在2+21N数列 取5项：2，23，44，65，86，得23/5余3，因3*5*7=105，即23+105N数列的数都满足这些条件。最小的就是23
中国剩余定理又称孙子定理，它的证明这样的
因为(mi,mj)=1,i！=j, （这里mi，mj是互素的，如上题中2,3,7），则 (Mi, mi)=1,对每个Mi，都存在Ni,使得
MiNi ≡1 (mod mi)
又m=mi Mi ,故mj | Mi , i！=j,即
MiNi≡0 (mod mj)
则M1 N1b1+ M2 N2b2+…+ Mk Nk bk≡ bi (mod mi).因此
x≡M1 N1b1+ M2 N2b2+…+ Mk Nk bk (mod m)是同余方程的整数解
唯一性证明：
如果y也是上述同余方程的解，则满足
x≡y(mod m1); x≡y(mod m2); …; x≡y(mod mk)
即m1 |(x-y), m2 |(x-y),…, mk |(x-y).所以
m|(x-y)
即x≡y(mod m). 即证方程在模m条件下有唯一解。
证明可能有点难理解，可以看看例题帮助理解：
韩信点兵
韩信带贰仟伍佰士兵出去打仗，回营后，刘邦问士兵人数。韩信让士兵先列成五行纵队，末行一人；列成六行纵队，末行五人；列成七行纵队，末行四人；列成十一行纵队，末行十人。韩信立刻回答二千一百一十一人。刘邦惊为天人！
看过题目后就知道该如何求解了。即解一次同余方程组：（1）x ≡1(mod5); x ≡5(mod6); x ≡4(mod7); x ≡10(mod11)
（2）用孙子定理，
m1 =5, m2 =6, m3=7, m4 =11;这些是对应的除数，
b1 =1, b2 =5, b3=4, b4 =10;这些是对应的商，
m=5*6*7*11=2310;所有除数的乘积。
因此对应的Mi为M1 =462（2310/5），M2=385（2310/6），M3=330（2310/7）。M4=210（2310/11）
对应的Ni(逆元)为N1=3，N2=1，N3=1，N4=1
所以 x ≡ 462*3*1+ 385*1*5+ 330*1*4+210*1*10 ≡6731 ≡2111(mod2310) ，最小为2111。
这里有一个求解思路图：
1 int china (int *a ,int *m, int n) 2 { 3 int M=1,ans=0,mi,i,x,y; 4 for(i=0;i<n;i++) 5 M*=m[i]; //M=m1*m2*m3...*mn 6 for(i=0;i<n;i++) 7 { 8 mi=M/m[i]; //Mi=M/mi 9 exGcd(m[i],mi,x,y); //扩展欧几里德 10 ans=(ans+mi*y*a[i])%M; 11 } 12 return (ans%M+M)%M; 13 }View Code
题目链接：Biorhythms
