中国剩余定理即孙子定理的五种解法
加深一下理解，找了点纯数学的资料（老者善学，尤老骥伏枥，况乎我也）：
“中国剩余定理”是公元5-6世纪、我国南北朝时期的一部著名算术著作《孙子算经》中的一个“物不知数”的解法问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？答曰：二十三。
《孙子算经》中虽然也有计算方法的叙述，如术曰：「三三数之剩二，置一百四十，五五数之剩三，置六十三，七七数之剩二，置三十，并之，得二百三十三，以二百一十减之， 即得。凡三三数之剩一，则置七十，五五数之剩一，则置二十一，七七数之剩一，则置十五，即得。」但也仅仅知道140+63+30=233、 233-210=23，得物数23。至于接着说的剩一、置70、置21、置15，应该是说140=70*2、63=21*3、30=15*2的来源，而 2、3、2又正是剩余数、210又正是除数3、5、7的最小公倍数的2倍。综合之，解的算式为70*2+21*3+15*2－2*3*5*7=23。虽然 如此，但仍不知为什么要这么算，还有， 70、21、15是怎样来的？等等，如读天书。如果换一个题目你能算吗？连照搬都没法搬。
这个问题，过了八、九百年，到了宋代，才有秦九韶在《算书九章》中给以解答。但现代人读古代数书，正如读古代医书一样，绝大多数是丈二和尚模不着头了。
“中国剩余定理”的现代数学提法是，解一元一次同余式方程组：
X≡2 (mod 3)
X≡3 (mod 5)
X≡2 (mod 7)
初等数论中有解法，得X最小值为23，通解为X=23 + 105K。但因为原理很难理解，所以也只能按公式规定的步骤与方法，依样画葫芦的计算罢了。时间一长也就忘光了。由此可见，“中国剩余定理”的理论及计算方法，还达不到普知的地步，不像一元二次方程的公式，初中生都知道公式怎样来的，怎样应用的。
若要问我：你对“中国剩余定理”的态度是怎样的呢？回答只有两个字：“敬畏”。
其实“中国剩余定理”，就是解一组带余除法的不定方程：
X÷3=A…2
X÷5=B…3
X÷7=C…2，
若避开难点，换个角度看，那么解这组方程，不一定非用“同余式方程组”的解法。就我所知，有五个方法：
一、枚举法
二、解不定方程法
三、逐级满足法
四、化为相同除数的同余式法、
五、才用到典经的、不同除数的同余式组解法
现将陈景润所著《初等数论Ⅰ》中的一个习题为例，分而习之。
试解
X≡2 (mod 7 )
X≡5 (mod 9 )
X≡1 (mod 5 )
一 、枚举法
X≡2 (mod 7 ) X÷7=A…2 X=7A+2
X≡5 (mod 9 ) 相当于 X÷9=B…5 → X=9B+5
X≡1 (mod 5 ) X÷5=C…1 X=5C+1
枚举法就是按A=0、1、2、3、4… B=0、1、2、3、4… C=0、1、2、3、4…
代入各式，计算各式的X，当三个X相同时，就是一个解。
A、B、C 0 1 2 3 4 … 9 10 11 12 … 16 17 18…
XA 2 9 16 23 30… 65 72 79 86…
XB 5 14 23 32 41 … 86 …
XC 1 6 11 16 21 … 46 51 56 61 … 81 86 …
即，当A=12、B=9、C=17时，X 都等于86。所以最小 X=86。由于7、9、5的最小公倍数是315，所以，通解 X=86+315K (K=0、1、2、3、…)
枚举法就是凑，很'笨’，但也最直观。适合小学生学习。也可用电子表格计算，那太快捷了。
二 、解不定方程法
X=7A+2
X=9B+5 →9B+5=7A+2 →9B=7A+2-5=7A-3 →B=(7A-3)/9
X=5C+1 →5C+1=7A+2 →5C=7A+2-1=7A+1 →C=(7A+1)/5
由B=(7A-3)/9，算得：当A=3时，B=2，但A=3时，C=(7A+)/5=4.4。由于A、B、C只能是整数。所以 3、2、4.4这一组，不符合要求，要重算A。又由于B=(7A-3)/9的分母是9，所以下一个A，只能在3的基础上，增加一个9的倍数，所以A只能取12、21、30、39…有了A，再算B、C，当A、B、C全是整数时，才合格。结果如下：
A B C
3 2 4.4
12 9 17
21 16 29.6
…
可见，只能取A=12 、B=9 、C=17 ， 代入原式：
X=7A+2=7*12+2=86
X=9B+5=9*9+5=86
X=5C+1=5*17+1=86
得 X=86、通解为X=86+315K
三 、逐级满足法
这个方法的基本思路是：先解算出合符第一个方程的X1。再解算出合符第一、第二个方程的X2，令X2=X1+P1。关键是P1要保持第一个方程中的倍数要求，又要合符第二个方程中的剩余要求。再解算出合符第一、第二、第三个方程的X3，令X3=X2+P2，关键是P2要保持第一第二两个方程中的倍数要求，又要合符第三个方程中的剩余要求。这样逐级解算，满足全部条件。
这使我想起老本行测量，好比测量平差的分组平差。只是测量分组平差时，要改化方程式的系数，比较麻烦，而这里仅要调整倍数与余数就行了。
X=7A+2
X=9B+5
X=5C+1
先解第一方程 X=7A+2。最简，X1=2。
再解第二方程 X=9B+5 。令X2=X1+P1=2+P1。首先要求P1应是7的倍数7K，即P1只能=7、14、21、27…为什么呢，因为第一个方程X=7A+2中，有7A一项，所以X2最起码应是X2==X1+P1=2+P1=2+7K，即应是 9、16、23、30、…中的一个，才能满足第一个方程中的7倍数的要求。
但仅仅这样取P1，不一定满足第二个方程中的剩余5的要求。为此，要统一考虑第一第二方程的总的剩余要求。要将X1=2看作是第一第二两个方程的总的余数的一部份。现在要求剩余为5，而前面已经有余数2了，所以P1除以9后，余数应为5－2=3，才能使总余数为5。这样才满足第二个方程中的剩余5的要求。
总之，P1应是7的倍数、且P1÷9余3，这就是对P1的要求。
用方程表示为：7K÷9=N…3，或(7K－3)/9=整数N。
将K=1、2、3、4…代入，K=1时，N=0.44，非整数，不合符要求。再往下算，得K=3时，N=2，整数了，合符要求。所以P1=7K =7*3=21。这样，X2=X1+P1=2+21=23
注：请回头看看枚举法，当A=2、B=3时，也得XA=XB=23，凑两个方程容易。凑三个以上就难了。
再解第三方程 X=5C+1，前已得X2=23。
令X3=X2+P2=23+ P2。首先要求P2应是7*9=63的倍数63K，即P2只能=63、126、189…为什么呢，因为第一第二方程中有7A、9B，63是它们的最小公倍数。
同样，P2不一定满足第三个方程中的剩余1的要求。为此，要统一考虑第一第二第三方程的总的剩余要求。要将X2=23看作是第一第二第三方程的总的余数的一部份。现在要求剩余1，而前面已经有余数23了，所以P2除以5后，余数应为1－23=－22，这样才满足第三个方程中的剩余1的要求。但余数=－22不是很怪吗？实际上不怪，因为在数论中，不管除数的大小，可以把除数归入余数之中的。例如83÷5=16…3，可以表示为 83÷5=15…8，也可以表示为 83÷5=21…… －22，它们用同余表示为 83 ≡3 (mod 5 ) 、83 ≡8 (mod 5 ) 、83 ≡－22 (mod 5 )，是相同的。现在第三式中除数是5，现要求余数为－22，便可以改化为5*5－22=25－22=3，即余3。
这样，P2应是63的倍数、且P1÷5余3，这就是对P2的要求。
用方程表示为：63K÷5=N…3，或(63K－3)/5=整数N。
将K=1、2、3、4…代入，可得K=1时，N=12，合符要求。所以P2=63*1=63，即X3=X2+P2=23+63=86，这是最小解。通解为X=86+315K
四 、化为相同除数的同余式法
X≡2 (mod 7 )
X≡5 (mod 9 )
X≡1 (mod 5 )
这三个同余式，除数不同，分别为7、9、5，为了能利用同余式的和差特性，简化计算，先设法使它们的除数相同，为此：
X≡2 (mod 7 )两边都乘9*5，得X*45≡2*45 (mod 7*45 ) →45 X≡90 (mod 315 ) …(1)
X≡5 (mod 9 ) 两边都乘7*5，得X*35≡5*35 (mod 9*35 ) →35 X≡175 (mod 315 ) …(2)
X≡1 (mod 5 ) 两边都乘7*9，得X*63≡1*63 (mod 9*63 ) →63 X≡ 63 (mod 315 ) …(3)
根据同余式的加减性质，(1)－ (2)得：
(45-35) X≡(90-175) (mod 315 ) →10 X≡－85 (mod 315 ) →10 X≡230 (mod 315 )
而10 X≡230 (mod 315 )就意味着(10X－230)÷315=商N (整数)，由此解得X=86、N=2，合符整数要求，所以 X≡86 (mod 315 )
验算：X≡86 (mod 315 ) ，两边都乘63，得 63 *X≡86*63 (mod 315 )
→63 X≡5418 (mod 315 ) →63 X≡63 (mod 315 )正与(3)相同。没有算错。
所以 X=86是最小解。通解为 X=86+315K或X≡86 (mod 315 )
五、 典经的、不同除数的同余式组解法
X≡R1 (mod m1 ) X≡2 (mod 7 )
X≡R2 (mod m2) X≡5 (mod 9 )
X≡R3 (mod m3) X≡1 (mod 5 )
名词注释及计算步骤：
1 余数R：、R1=2、R2=5、R3=1
2 模，亦即除数m：例中m1=7、m2=9、m3=5
3 模的最小公倍数G：G=m1*m2*m3，例中M=7*9*5=315
4 衍数（局部公倍数）y：Y1=m2m3、Y2=m1m3，Y3=m1m2，例中Y1=9*5=45、Y2=7*5=35、Y3=7*9=63
5 乘率C：这是解算中国剩余定理的关键，而计算“乘率”的方法，是秦九韶在《数书九章》一书中首次提出 的，称之为“大衍求一术”。“求一”就是使(衍数*乘率)除以模(除数)，而余数为1。即：
衍数Y*乘率C≡1 (mod m)，乘率C可以经过反算而得到。例中Y1C1≡1 (mod 7 )、
Y2C2≡1 (mod 9 ) 、Y3C3≡1 (mod 5 )。
计算C1方法。由Y1C1≡1 (mod 7 )， →45C1≡1 (mod 7 ) →(45C1－1) / 7=整数N ，得C1=5。因为45*5=225，225－1=224，224÷7=32，32是整数，合符要求。C2、C3之计算也相仿。乘率C之计算见下表：
同余式 i
衍数Y
乘率C
余1
模m
检验 (Y*C-1)/m = 整数
1
45
5
1
7
(45*C-1)/7 =N (45*5-1)/7 = 32
2
35
8
1
9
(35*C-1)/9 =N (35*8-1)/9 = 31
3
63
2
1
5
(63*C-1)/5 =N (63*2-1)/5 = 25
6 最终结果，X≡R1Y1C 1+R2Y2C2+R3Y3C3 (mod G)
即X≡Σ余数*衍数*乘率 (mod G)，见下表计算：
i
余数R
衍数Y
乘率C
R*Y*C
1
2
45
5
450
2
5
35
8
1400
3
1
63
2
126
Σ
1976
X≡1976 (mod 315) 。1976 除去315的6倍后，剩下86，最终，
X≡86 (mod 315)
六 、用分组的逐级满足法解“韩信点兵”
陈景润 著《初等数论Ⅰ》例：
韩信点兵：有兵一队，若列成5行纵队，则末行1人。成6行纵队，则末行5人，成7行纵队，则末行4人，成11行纵队，则末行10人。求兵数。
设：X是兵数，依题意有：
X≡1 (mod 5)
X≡5 (mod 6)
X≡4 (mod 7)
X≡10 (mod11)
现将四式分为两大组，对每组的两个式，都用逐级满足法，分别求出两个X。再合并求出最终X。这是我独自想出的方法，正确性、简便性如何，请一试验证之。
第一组：
X≡1 (mod 5) → X1=1
X≡5 (mod 6) → X2= X1+P1=1+P1 →P1=5K。
关于余数，前已有1，现要求余5，则应余5－1=4，所以P1又应满足(5K－4)/6=整数N的要求。经电子表格凑算，当K=2时，N=1，行。这样，X2=1+5K=1+5*2=11，此两式最小公倍数5*6=30，所以 有X≡11 (mod 30) …(A)
第二组：
X≡4 (mod 7) → X3=4
X≡10 (mod 11) → X4=X3+P3=4+P3 →P3=7K。
关于余数，前已有4，现要求余10，则应余10－4=6，所以P3又应满足(7K－6)/11=整数N的要求。经电子表格凑算，当K=4时，N=2，行。这样，X4=4+7K=4+7*4=32，此两式最小公倍数7*11=77，所以 有
X≡32 (mod 77) ……(B)
经分批解算，得到两个新的同余式：
X≡11 (mod 30) ……(A)
X≡32 (mod 77) ……(B)
再用逐级满足法解。XA=11、XB=XA+PA=11+PA、PA=30K。
关于余数，前已有11，现要求余32，则应余32－11=21，所以PA又应满足(30K－21)/32=整数N的要求。经电子表格凑算，当K=70时，N=27，行。这样，XB=11+30K=11+30*70=2111，此两式最小公倍数30*77=2310，所以有：
X≡2111 (mod 2310) ，即X=2111+2310K
现再用第四节“化为相同除数的同余式法”来解算这两个新的同余式。
X≡11 (mod 30) ……(A)，乘77，得 77X≡847 (mod 2310)……(1)
X≡32 (mod 77) ……(B)，乘30，得 30X≡960 (mod 2310)……(2)
(1)－ (2) ，得 47X≡－113 (mod 2310) ……(3)，相当于要求(47X+113)/2310=N整数。由电子表格帮忙，算得X=2111，此时N=43，合符要求。所以也得到 X=2111+2310K。
真是路路通啊，有收获。
七 、写后感
2013年的国庆过得很忙，甚至还起了一个早床。感谢我的老伴，以她的勤劳与宽容，给了我闲暇与自由，使我能够安逸地做做算术、写写文章，自得其乐，有时间消磨我的时光。
我仰望深邃的数学天空，深感自己的渺小。我浅尝一滴数学的清泉，来润湿一下我干枯的灵感。