中国剩余定理
一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。
宋朝数学家秦九韶于1247年《数书九章》卷一、二《大衍类》对“物不知数”问题做出了完整系统的解答。明朝数学家程大位将解法编成易于上口的《孙子歌诀》：
三人同行七十希，五树梅花廿一支，七子团圆正半月，除百零五使得知
这个歌诀给出了模数为3、5、7时候的同余方程的秦九韶解法。意思是：将除以3得到的余数乘以70，将除以5得到的余数乘以21，将除以7得到的余数乘以15，全部加起来后除以105，得到的余数就是答案。比如说在以上的物不知数问题里面，按歌诀求出的结果就是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(mod7 )
X≡5(mod9 )
X≡1(mod5 )求X
一 枚举法
X≡2(mod7 )X÷7=A…2X=7A+2
X≡5(mod9 )相当于X÷9=B…5→X=9B+5
X≡1(mod5 )X÷5=C…1X=5C+1
枚举法就是按A=0、1、2、3、4…B=0、1、2、3、4…C=0、1、2、3、4…
代入各式，计算各式的X，当三个X相同时，就是一个解。
A、B、C0 1234 … 9101112 …1617 18…
XA 2 91623 30…65727986…
XB5 1423 32 41 …86 …
XC1611 1621 … 46515661 …8186 …
即，当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全是整数时，才合格。结果如下：
ABC
324.4
12917
2116 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得X=86、通解为X=86+315K。实际上，这仍然是枚举法，只是枚举个数减少一些而已。
三 逐级满足法
这个方法的基本思路是：先解算出合符第一个方程的X1。再解算出合符第一、第二个方程的X2，令X2=X1+P1。关键是P1要保持第一个方程中的倍数要求，又要合符第二个方程中的剩余要求。再解算出合符第一、第二、第三个方程的X3，令X3=X2+P2，关键是P2要保持第一第二两个方程中的倍数要求，又要合符第三个方程中的剩余要求。这样逐级解算，满足全部条件。
P要同时考虑两个方程的倍数关系如7A、9B，又要考虑两个余数关系，如余2、余5，方程数一多，处理时要拐几个弯，方法不易理解。
最近，我在作《数论—余数习题集》时，对“逐级满足法”作了改进。把第一个方程的通解，直接作为第二个方程的初值，不作任何转弯，就同时解决了两个方程之间的相关关系及余数关系，变得容易理解，容易操作、便于列式。这可以说是我的又一个心得罢。
仍按原例： X除以7余2、除以9余5、除以5余1，求最小X。
答：最小X=86通解 X =86 ＋315 N ( N=1、2、3 … )
已知：
X≡2(mod7 )X÷7=A…2X=7A＋2
X≡5(mod9 )相当于 X÷9=B…5→ X=9B＋5
X≡1(mod5 )X÷5=C…1X=5C＋1
A、B、C都是整数，可用K统一表示，且不论其具体数值。
解算步骤：
1、 先解第一个方程X÷7余2的通解X1。一般都很容易，即：
通解X1＝余数＋除数的倍数，例中X1=2＋7A 。其中余数就是最小解X0=2，加上7的最小公倍数的A倍，就是通解X1=2＋7A 。
X1是一个数列，其中总有一个数能满足所有方程，关键在于A是多少，又怎样定？A怎样定呢？现在不能定。因为要考虑到它能满足第二个方程，所以到那时才能定下来。
2、第二个方程。X÷9余5，此时的X首先应满足本方程要求： (X－5)÷9 = K(K是整数)。但同时又要满足第一个方程，既然X1可以满足所有方程，所以就干脆用第一方程的通解X1代替第二方程的未知数X ，即用(X1)取代X。即应满足 (X1－5)÷9 = K，才顾及了两式。
注意，(X1－5)÷9 =K这种形式的方程，是有规律的，即：
(第一方程的通解X1（=2＋7A ） 减 第二方程的余数5 )÷第二方程的除数9＝整数K，且以下各方程也都是这样的规律，亦即：
( 上一个方程的通解 减 本方程的余数 )÷本方程的除数 应 ＝ 整数K
现在有了 (2＋7A－5)÷9 =K ，就整理为(7A－3)÷9 = K。这时两个余数就自动合并了。
解此 (7A－3)÷9 = K方程，便得A=3 、 K＝2。
于是 X1=2＋7A=2＋7×3=23。此时，就把X1＝23作为第二个方程的最小解，转为X2，即X2＝23。再加上7与9的最小公倍数7×9=63的倍数，得通解X2＝23＋63M。这个X2，既满足第一个方程又满足第二个方程。
X2也是一个数列，其中总有一个数，能满足所有方程，所以就是下一个方程的未知数初值了。关键在于M是多少。M怎样定呢？现在不能定。要考虑到它能满足第三个方程。到那时才能定下来。
至此，得到一个同余式 X2≡23(mod63 )，实际上它是
X≡2(mod7 )
X≡5(mod9 )二个同余式的共同解。
至于用什么方法来解 (7A－3)÷9 = K 这个二元一次不定方程呢？(7A－3)÷9 = K也就是7A－9K = 3，在陈景润所著《初等数论Ⅰ》中，有一个手算方法，先用“辗转相除法”得到各次余数，直到余数为“ 1 ”，再反求出满足余数“ 1 ”时的X、K的新系数，再通过“同余式”的转换，转换成己知余数(如本例的3)，才得到最终的X的系数A。整个过程步骤多。反求X、K的新系数时、转换成己知余数时，都颇费工夫，我见了生畏。还不如老老实实的试算、凑数。
(7A－3)÷9 = K 求A与K的整数解，
列表凑罢：
A7A(7A－3)K＝ (7A－3)÷9
00－3－ 0.33
1740.44
321182好了，K是整数了
4… … 不必算了。
得A＝3、K＝2 。其实K仅起检验作用，是整数就行了，没有其他用处。
解二元一次不定方程最好的方法，当然是编个电脑程序。我已经编就了，请用吧
3、第三个方程。X÷5余1，此时X首先应满足本方程要求： (X－1)÷5 = K，又要满足第一、第二个方程。既然X2可以满足所有方程，所以就干脆用第二方程的通解X2代替第三方程的未知数X ，即用(X2)取代X。即应满足：
(X2－1)÷5 = (23＋63M －1)÷5=K，→ (63M＋22)÷5 = K。才顾及了三个方程。
解此二元不定方程 M=1 、 K＝17。把M代入X2，
于是 X2=23＋63M=23＋63×1=86，就把X2＝86作为第三个方程的最小解，转为X3
即X3＝86。再加上63与5的最小公倍数63×5=315的倍数，得通解
X3＝86＋315P。(P=1、2、3 … )
验算 86÷7 =12… 2
86÷9 = 9… 5
86÷5=17… 1
*****
“逐级满足法”解法有规律了，容易操作了。但也有两点麻烦：
1、组成形如 (AX±B)÷C＝K的不定方程，要一个个顺序进行，虽有规律，但还是比较麻烦。
2、解算(AX±B)÷C＝K方程，求待定量X、K，无论用手算，或是电子表格算，要解(N－1)次。也很烦人，特别是大数相除更麻烦。
为了加快计算，我编了一个VB程序，不用烦心，输入完数据，↙，就出结果了。
上述算题：
输入方程个数N = 3
输入各方程的除数与余数 729551↙
结果为：
通解 X =86＋ 315 N ( N=1、2、3 … )
还有一例：我曾靠电子表格算了一天，才得结果的，现在包括输入在内，仅15秒就搞定。
输入方程个数N = 6
输入各方程的除数与余数 32537211913743↙
结果为：
通解 X =20183＋ 60060N ( N=1、2、3 … )
四、化为相同除数 法
X≡2(mod7 )
X≡5(mod9 )
X≡1(mod5 )
这三个同余式，除数不同，分别为7、9、5，为了能利用同余式的和差特性，简化计算，先设法使它们的除数相同，为此：
X≡2(mod7 )两边都乘9*5，得X*45≡2*45(mod 7*45 )→45 X≡90(mod 315 ) …(1)
X≡5(mod9 ) 两边都乘7*5，得X*35≡5*35(mod 9*35 )→35 X≡175(mod 315 ) …(2)
X≡1(mod5 ) 两边都乘7*9，得X*63≡1*63(mod 9*63 )→63 X≡ 63(mod 315 ) …(3)
(1)＋(2)＋(3)＝ (4)→ 143 X≡328(mod 315 ) …4)
根据同余式的加减性质，(1)＋(2)＋(3)得：
143 X≡328(mod 315 )即 143 X≡13(mod 315 )，化为带余除式为：
143 X÷315=K …13亦即 143X－13=315 K ，有(143X－13)÷315＝K(整数)
(143X－13)÷315＝K(整数)用通式表示为 (AX－B)÷S＝K
解得 X=86、K=38(实际上不用它，在此仅确认它是整数就行了)，
通解为 X＝86+315 N( N＝ 1、2、3 … )
或 X≡86(mod 315 )
数论是纯粹数学的分支之一，主要研究整数的性质。
按研究方法来看，数论大致可分为初等数论和高等数论。初等数论是用初等方法研究的数论，它的研究方法本质上说，就是利用整数环的整除性质，主要包括整除理论、同余理论、连分数理论。高等数论则包括了更为深刻的数学研究工具。它大致包括代数数论、解析数论、计算数论等等。
初等数论主要就是研究整数环的整除理论及同余理论。此外它也包括了连分数理论和少许不定方程的问题。本质上说，初等数论的研究手段局限在整除性质上。
初等数论中经典的结论包括算术基本定理、欧几里得的质数无限证明、中国剩余定理、欧拉定理（其特例是费马小定理）、高斯的二次互反律， 勾股方程的商高定理、佩尔方程的连分数求解法等等
