迭代法解同余方程组X≡0(mod 13),x≡9(mod 10),x≡9(mod 13)？
如何将同余式方程化为同余式组来解？
设(a, m) = 1，m>0，则同余式ax≡b(mod m)恰有一个解。设(a, m) = d，m>0，则同余式ax≡b(mod m)有解的充分必要条件是d|b，此时恰有d个解。根据以上两个定理，同余方程ax≡b (mod m)在a?0且(a,m)|b的条件下，必有(a,m)个关于模m互不同余的解。又根据最大公约数的性质，必有二整数x、y，能使ax+my=(a,m)。由于(a,m)|b，所以有，，使，由此即可得到原方程的(a,m)个关于模m互不同余的解为。
同余方程组解法
我写个简例吧：
AAA解法：
解同余式组:x≡1(mod5) x≡2(mod11)
解：中国剩余定理的等效解法
令x=5a+11b +55t 亦即 x==5a+11b mod 5*11
代入原同余式组得
11b==1 mod 5
5a==2 mod 11
解得b==1 mod 5, a=-4==7 mod 11
取任意一组特解如b=1,a=7代入得
x==5*7+11*1=46 mod 55
BBB解的数量之判定法：
对于多个模并非两两互质的情况，可以先确立一组两两互质的分解基数集（质数集是一个常用的特例），将这些模用分解基数表示成为多个因数项，将其中相关于同一个分解基数的项进行归并。如果有矛盾，则无解。
否则有解。
例：同余式组
x=2 mod 16
x=3 mod 5
x=6 mod 12
取4, 3, 5作为分解基。变成
x=2 mod 4^2
x=3 mod 5
x=6 mod 4
x=6 mod 3
其中相关于同一个分解基数的情况，仅有x=2 mod 16与x=6 mod 4是相关于分解基数"4"的,它们没有矛盾。取两相容解集的交集，即其中解集较小的那个：x=2 mod 16.
再与x=3 mod 5及x=6==0 mod 3联立求解。
另例：
x=2 mod 18
x=8 mod 12
以3,2为分解基。
相关于分解基数3的转化式有x=2 mod 3^2, x=2 mod 3, 取前者。
相关于分解基数2的转化式有x=0 mod 2, x=0 mod 4, 取后者。
另例：同余式组
x=3 mod 12
x=2 mod 18
以2,3为分解基集，于是原同余式组变成
x==3 mod 2^2
x==3 mod 3
x==2 mod 3^2
x==2 mod 2
矛盾。故此同余式无解。
如果是形如
ax=b mod m形状的同余式联立的，
则可能出现无解、一解、多解的情况。一个基本的例子如下：
12x=18 mod 27 注：相当于12x=9+18k
自然就等价于同余式
4x=3 mod 9
解得x=3 mod 9, 转化为模27的同余式，为
x=3,12,21 mod 27
AAAAAA快速计算法
例如同余式组(以下用==表示同余号)
x==
2 mod 5
-2 mod 6
-3 mod 7
对中国剩余定理一个简单的改进可以是这样：
令
x=5*6*7*(a/5+b/6+c/7) mod 5*6*7
即x=6*7*a+5*7*b+5*6* c+ 5*6*7 t
代入原题即得
6*7*a==2 mod 5
5*7*b==-2 mod 6
5*6*c==-3 mod 7
求得
a==1 mod 3, 或者说是形如-1+3u的任意整数。
b=2 mod 5, ...
c=2 mod 7
剩下的就是如果计算出x来了。下面也给了简化方法。
从下面这个式子上看
x=5*6*7*(a/5+b/6+c/7) mod 5*6*7
=5*6*7*(a/5+b/6+c/7 mod 1) 注意，这个式子极具有启发性！
我们看到，我们需要的x的值，只要取以5*6*7作分母时的分数(a/5+b/6+c/7) 的分子就行了，
如果我们将 a/5+b/6+c/7表示成带分数，即整数加真分数的形式。
还可以发现，如果要取最小正整数解，就取这个真分数的分子就形子。。
在计算过程中，
任意加减一个整数，造成数的增大和变小，并不影响我们的结果。
同时，任意交换加项，也不影响。
下面我们来计算：
1/5+2/6+2/7 mod 1=16/30+2/7=172/210
再例：这是我刚答的一道题，讲的较为明确精炼，请参考。
一个数÷5余1，÷7余3，÷9余2，这个数最小是几？
题目转化为同余式组
x==1 mod 5
x==3 mod 7
x==2 mod 9
解：
令x==7*9*a+5*9*b+5*7*c mod 5*7*9
即x=7*9*a+5*9*b+5*7*c+5*7*9*t
即x==5*7*9*(a/5+b/7+c/9 mod 1)
即x=5*7*9*(a/5+b/7+c/9+t)
代入原同余式组得
7*9*a==1 mod 5 , 于是a==2 mod 5, 取其特值2为代表。
5*9*b ==3 mod 7，于是b==1 mod 7,取其特值1为代表。
5*7*c==2 mod 9,于是c==-2 mod 9,取其特值-2为代表。
再以
x==5*7*9*(a/5+b/7+c/9 mod 1)为求值式，进行计算。
先计算（a/5+b/7+c/9 mod 1)
注意，计算过程中，任一个加项或整体值上可以加减任一个整数，不影响。同时，在计算时，可以充分运用加法的交换律与结合律，随意调整加法项的位置与加法过程的顺序。
其中，mod 1这个提法一定要理解，这样可以为解同余式组带来极大的方便。
mod 1表示两个对象相差一个整数值。如果mod用来表示求余，则表示求一个数的小数部分；如果N==0 mod 1，即说明N为整数。
2/5+1/7-2/9 mod 1 ==2/5-2/9+1/7==8/45+1/7==101/45*7==101/315
于是x==101 mod 315
这个数最小为 101
求解同余方程组，求详细过程。
x≡1(mod 6)
x≡4(mod 9)
x≡7(mod 15)
解：
以下同余号≡也用==表示。
x≡1(mod 6) 等价于x==1 mod 2且x==1 mod 3
x==7 mod 15 等价于x==1 mod 3且x==2 mod 5
x==4 mod 9蕴含了 x==1 mod 3
于是原同余式组等价于
x==1 mod 2
x==4 mod 9
x==2 mod 5
下面是中国剩余定理的等价解法。
令x == 9*5 a +2*5 b+ 2*9 c mod 2*9*5 亦即 x = 9*5 a +2*5 b+ 2*9 c + 2*9*5 k
代入原同余式组，得
a ==1 mod 2, b==4 mod 9, c==-1 mod 5
取其代表值即可。如 a=1, b=4, c=-1，得到
x==67 mod 90
外一则：我的计算过程：
x==
1 @ 2
4 @ 9
-1 @ 5
=>17@ 18 或-1 @ 18
=67mod 90 或 -23 mod 90
注：
这里的@表示模积计数表示，是我的一种特殊算法，可以方便的计算这类表达式。详见我的相关答题或空间中关于中国剩余定理的文章。
楼上几位朋友们则是通过观察找到了快速解法。也可以阐述如下：
x≡1(mod 6)
x≡4(mod 9)
x≡7(mod 15)
解：易见
x==-5 mod 6
x==-5 mod 9
故 x==-5 mod lcm[6,9] 注：lcm表示最小公倍数。
即x==-5 mod 18
又观察到 x==-23 mod 18
x==-8==-23 mod 5
故x==-23 mod lcm[18,5]
即x==-23==67 mod 90
解一次同余式组 x≡3(mod9) x≡4(mod11) x≡5(mod17)
x≡3(mod9) x≡4(mod11) x≡5(mod17)
x=3+9a x=4+11b x=5+17c 除以9余3 除以11余4 除以17余5
9a=11b+1 a=5 b=4 x=45 符合前两个式子 因为9和11最小公倍数是99
下一个x要比上一个大99 x=45+99k
第三个式子也考虑进来。 x=45+99k=5+17c 99k+40=17c
k=1,2,3....时 139,238,337.....中, 只有238=17*14是17的倍数 17和99的最小公倍数是1683
所以 x的下一个解=238+1683
答案 x=238+1683n n为整数