START
中国剩余定理用于求解线性同余方程组：
a = a1 (mod n1)
a = a2 (mod n2)
a = a3 (mod n3)
........
a = ai (mod ni)
任意ni和nj（i != j）互质，问a的值。
我们可以把a写成a=Σai*ci，（ci待求），这个式子要满足两个条件：
1.任意i!=j时ai*ci%nj=0
2.满足ai*ci%ni=ai。
只要满足了这两个条件的a就是我们要求的a。
如何求ci?：
因为正整数n1,n2......ni都互质，那么任意 i != j 都有gcd(ni,nj)=1。
设mi=（n)/ni。其中n=n1*n2*n3*.......*ni。
于是有gcd(ni,mi)=1。
根据扩欧的性质我们知道，存在mi‘,ni‘使得mi*(mi‘)+ni*(ni‘)=1。
在模ni的条件下就是:mi*(mi‘) = 1 (mod ni)。------①
显然，令ci=mi*(mi‘)，这样的ci是满足条件2的（将①左右同时×ai）
又因为mi包含有nj(i!=j) ，则mi*(mi‘)%nj =0(i!=j)，左右同时×ai得到ai*mi*(mi‘)=0 (mod nj)所以条件1也成立
现在求ci就是求mi*mi‘的问题。
mi和mi‘都很好求。
mi=n/ni。
mi‘直接用扩欧来求，实际上在求的过程我们发现mi‘就是mi的逆元，用扩欧求mi相对ni的逆元就是我上面介绍的原理（如果ni和mi互质的话还可以用费马小定理求解逆元）
求出ai*mi*mi‘后累加即可得到a。
到此，中国剩余定理就讲完了。
模板代码网上很多，这里就不贴了。
END
原文：https://www.cnblogs.com/cautx/p/11386001.html