中国剩余定理的应用
中国剩余定理又称孙子定理，数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：
有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。其实，南宋数学家秦九韶在其著作《数书九章》中，系统的提出并证明了这一类问题的解法，因此这个定理也可以称为孙子秦九韶定理。
明朝数学家程大位将解法编成易于上口的《孙子歌诀》：
三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五使得知
这个歌诀给出了模数为3、5、7时候的同余方程的秦九韶解法。意思是：将除以3得到的余数乘以70，将除以5得到的余数乘以21，将除以7得到的余数乘以15，全部加起来后除以105（或者105的倍数），得到的余数就是答案。比如说在以上的物不知数问题里面，按歌诀求出的结果就是23。
中国剩余定理的理论证明比较复杂，这里就不做叙述，只就如何应用中国剩余定理做讲解。首先，中国剩余定理应用的题型必须要求除数两两互质，这样才能方便的用中国剩余定理，否则要做一些变化处理。
例1、一个数被5除余2，被6除余4，被7除余3，这个数最少是多少？
解：第一步：判断5，6，7两两互余。
第二步：计算5，6，7的最小公倍数，得5×6×7=210。
第三步：计算各除数的逆元。将5去掉，计算6×7=42，42÷5=8……2，将余数2适当的扩大倍数，使除以5的余数是1，很显然这个倍数是3，也就是逆元是3；将6去掉，计算5×7=35，35÷6=5……5，将余数5适当的扩大倍数，使除以6的余数是1，很显然这个倍数是5，也就是逆元是5；将7去掉，计算5×6=30，30÷7=4……2，将余数2适当的扩大倍数，使除以7的余数是1，很显然这个倍数是4，也就是逆元是4；
第四步：将余数和逆元和最小公倍数除以该数的商相乘，然后将各个结果相加，再除以最小公倍数所得的余数即为所求。计算42×3×2+35×5×4+30×4×3=1312，1312÷210=6……52，因此这个最小的数就是52。
