之前介绍到的中国剩余定理只能求解模数两两互质的同余方程组。    那么，模数如果不一定两两互质的情况应该怎么求呢？    下面介绍通过合并方程的方法来解决问题（要用到扩展欧几里德算法）。      顾名思义，合并方程就是把所有的同余方程组合并成一个。    举个例子，合并同余方程组  x%A=a  ①                               x%B=b   ②        现在给出两种合并的方法:     1）要把①②式合并成    x%C=c   ③        易知C一定是A和B的最小公倍数的倍数，否则不可能同时满足①②两式。        这里我们取C为A,B的最小公倍数，设d=gcd(A,B),则C=A*B/d.        接下来我们只要求出余数c即可，假设p是方程组①②的其中一个解        因为③是①②两式的合并方程，所以p也是③的解，所以可以得到c=p%C        接下来的问题就是怎么求出方程组①②的其中一个解。        首先，满足方程组①的最小解显然就是x=a        然后满足①②的解就是 (a+kA)%B=b,其中x=a+kA（k为任意自然数）        这个方程很明显可以用扩展欧几里德算法即可求得x，这样就完成了两个方程的合并                当所有的同余方程合并成一个方程 x%G=g 时候，g即为最终的最小解。。       2）至于第二种方法，请参考http://972169909-qq-com.iteye.com/blog/1266328       这种方法我也不是太了解，日后会完善。