中国剩余定理的应用详解

中国剩余定理又称孙子定理，数学著作《孙子算经》卷下第二十六题，叫做'物不知数'问题，原文如下：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。其实，南宋数学家秦九韶在其著作《数书九章》中，系统的提出并证明了这一类问题的解法，因此这个定理也可以称为孙子秦九韶定理。

明朝数学家程大位将解法编成易于上口的《孙子歌诀》：

三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五使得知

这个歌诀给出了模数为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。

例2、一个数被3除余1，被5除余2，被7除余3，被8除余4，这个数最少是多少？

解：第一步：判断3，5，7，8两两互余。

第二步：计算3，5，7，8的最小公倍数，得3×5×7×8=840。

第三步：计算各除数的逆元。将3去掉，计算5×7×8=280，280÷3=93……1，余数已经是1了，就不用扩大倍数了，或者说倍数是1，也就是逆元是1；将5去掉，计算3×7×8=168，168÷5=33……3，将余数3扩大适当的倍数，使除以5的余数是1，很显然这个倍数是2，也就是逆元是2；将7去掉，计算3×5×8=120，120÷7=17……1，余数已经是1了，就不用扩大倍数了，或者说倍数是1，也就是逆元是1；将8去掉，计算3×5×7=105，105÷8=13……1，余数已经是1了，就不用扩大倍数了，或者说倍数是1，也就是逆元是1；

第四步：将余数和逆元和最小公倍数除以该数的商相乘，然后将各个结果相加，再除以最小公倍数所得的余数即为所求。计算280×1×1+168×2×2+120×1×3+105×1×4=1732，1732÷840=52，因此这个最小的数是52。

例3、一个数被5除余1，被6除余5，被7除余4，被11除余9，这个数最小是多少？

解：第一步：判断5，6，7，11两两互余。

第二步：计算5，6，7，11的最小公倍数，得5×6×7×11=2310。

第三步：计算各除数的逆元。将5去掉，计算6×7×11=462，462÷5=92……2，将余数2适当的扩大倍数，使除以5的余数是1，很显然这个倍数是3，也就是逆元是3；将6去掉，计算5×7×11=385，385÷6=64……1，余数已经是1了，这样逆元就是1；将7去掉，计算5×6×11=330，330÷7=47……1，余数已经是1了，这样逆元就是1；将11去掉，计算5×6×7=210，210÷11=19……1，余数已经是1了，这样逆元就是1。

第四步：将余数和逆元和最小公倍数除以该数的商相乘，然后将各个结果相加，再除以最小公倍数所得的余数即为所求。计算462×3×1+385×1×5+330×1×4+210×1×9=6521，6521÷2310=2……1901，因此这个数就是1901。

总结：应用中国余数定理时，思路简单，按照题目所示步骤进行计算就可以了，但计算过程稍显复杂，若题目具有一定的特殊性，我们也可以采用其他的方法。