中国剩余定理

中国剩余定理

图片来自搜狐网

中国剩余定理，孙子定理是中国古代求解一次同余式组（见同余）的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。

目录

孙子算经

《孙子算经》是中国古代重要的数学著作，共三卷，成书约在四、五世纪，作者生平和具体编写年不详。

其卷下的第26题为：

今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？

答曰：‘二十三’。

术曰：三三数之剩二，置一百四十；五五数之剩三，置六十三，七七数之剩二，置三十，并之。得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一，则置十五；一百六以上以一百五减之即得。

（即—一个整数除以3余2、除以5余3、除以7余2，求这个整数。

答案：23

解法：由于除以3余2，因此加上一个140；由于除以5余3，因此加上一个63；由于除以7余2，因此加上一个30；这三个数的和是140+63+30=233，再减去210，就得到了23了。

这么说吧，只要是除以3余了一个1，就加上一个70；只要是除以5余了一个1，就加上一个21；只要是除以7余了一个1，就加上一个15。然后累加。超过了106就减去105就行了。该问题称之为“物不知数”问题。

文献

一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：

有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。

宋朝数学家秦九韶于1247年《数书九章》卷一、二《大衍类》对“物不知数”问题做出了完整系统的解答。明朝数学家程大位将解法编成易于上口的《孙子歌诀》：

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

这个歌诀给出了模数为3、5、7时候的同余方程的秦九韶解法。意思是：将除以3得到的余数乘以70，将除以5得到的余数乘以21，将除以7得到的余数乘以15，全部加起来后除以105（或者105的倍数），得到的余数就是答案。比如说在以上的物不知数问题里面，按歌诀求出的结果就是23。

设R是一个主理想整环，m1, m2, ... , mk是其中的k个元素，并且两两互质。令M

m1m2...mn为这些元素的乘积，那么可以定义一个从商环R/MR映射到环乘积R/m1R × … × R/mkR的同态：

并且 的逆映射也存在。而这个逆映射的构造方式就如同中国剩余定理构造一元线性同余方程组的解一样。由于mi和Mi=M/mi互质，所以存在si和ti使得而映射就是的逆映射。

一般的交换环

设R是一个有单位元的交换环，I1,I2, ... ,Ik是为环

数论相关

数论是纯粹数学的分支之一，主要研究整数的性质。

按研究方法来看，数论大致可分为初等数论和高等数论。初等数论是用初等方法研究的数论，它的研究方法本质上说，就是利用整数环的整除性质，主要包括整除理论、同余理论、连分数理论。高等数论则包括了更为深刻的数学研究工具。它大致包括代数数论、解析数论、计算数论等等。

初等数论主要就是研究整数环的整除理论及同余理论。此外它也包括了连分数理论和少许不定方程的问题。本质上说，初等数论的研究手段局限在整除性质上。

初等数论中经典的结论包括算术基本定理、欧几里得的质数无限证明、中国剩余定理、欧拉定理（其特例是费马小定理）、高斯的二次互反律， 勾股方程的商高定理、佩尔方程的连分数求解法等等。

例题解析

例一：一个数，除以5余1，除以3余2。问这个数最小是多少？

采用通用的方法：逐步满足法

把除以5余1的数从小到大排列：1，6，11，16，21，26，……

然后从小到大找除以3余2的，发现最小的是11.

所以11就是所求的数。

先满足一个条件，再满足另一个条件，所以称之为“逐步满足法”。

例二：一个数除以5余1，除以3也余1。问这个数最小是多少？（1除外）

特殊的方法：最小公倍法

除以5余1：说明这个数减去1后是5的倍数。

除以3余1：说明这个数减去1后也是3的倍数。

所以，这个数减去1后是3和5的公倍数。要求最小，所以这个数减去1后就是3和5的最小公倍数。即这个数减去1后是15，所以这个数是15+1=16.

例三：一个数除以5余4，除以3余2。问这个数最小是多少？

这种情况也可以用最小公倍法。

数除以5余4，说明这个数加上1后是5的倍数。

数除以3余2，说明这个数加上1后也是3的倍数。

所以，这个数加上1后是3和5的公倍数。要求最小，所以这个数加上1后就是3和5的最小公倍数。即这个数加上1后是15，所以这个数是15－1=14。

多个数的，比如3个数的，有时候其中两个可以用特殊法，那就先用特殊法，用特殊法求出满足两个条件的数后再用通用的方法求满足最后一个条件的数。

例四：有1个数，除以7余2．除以8余4，除以9余3，这个数至少是多少？

除以7余2的数可以写成7n+2。

7n+2这样的数除以8余4，由于2除以8余2，所以要求7n除以8余2。

7n除以8余2，7除以8余7，要求n除以8余6（乘数之余等于余数之乘），则n最小取6。

所以满足“除以7余2，除以8余4”的最小的数是7×6+2=44，

所有满足“除以7余2，除以8余4”的数都可以写成44+56×m。

要求44+56×m除以9余3，由于44除以9余8，所以要求56×m除以9余4。（加数之余等于余数之加）

56×m除以9余4，由于56除以9余2，所以要求m除以9余2（乘数之余等于余数之乘），则m最小取2。

所以满足“除以7余2，除以8余4，除以9余3”的最小的数是44+56×2=156。

例五：三三数之剩二，五五数之剩三，七七数之剩二。问物几何？

即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。

除以3余2和除以7余2的数可以写成21n+2。

21n+2除以5余3，要求21n除以5余1。

21n除以5余1，21除以5余1，要求n除以5余1（乘数之余等于余数之乘），则n最小取1。

所以满足“除以3余2，除以5余3，除以7余2”的最小的数是21×1+2=23。

标准解法：先从3和5、3和7、5和7的公倍数中相应地找出分别被7、5、3除均余1的较小数15、21、70 ( 注释:此步又称为求"模逆"运算,利用扩展欧几里得法并借助计算机编程可比较快速地求得.当然,对于很小的数,可以直接死算 )。即

15÷7=2……余1，

21÷5=4……余1，

70÷3=23……余1.

再用找到的三个较小数分别乘以所要求的数被7、5、3除所得的余数的积连加，

15×2+21×3+70×2=233. (将233处用i代替，用程序可以求出)

最后用和233除以3、5、7三个除数的最小公倍数.

233÷105=2……余23，

这个余数23就是合乎条件的最小数.

例六：一个数被5除余2，被6除少2，被7除少3，这个数最小是多少?

题目可以看成，被5除余2，被6除余4，被7除余4 。看到那个“被6除余4，被7除余4”了么，有同余数的话，只要求出6和7的最小公倍数，再加上4，就是满足后面条件的数了，6X7+4=46。

下面一步试下46能不能满足第一个条件“一个数被5除余2”。不行的话，只要再46加上6和7的最小公倍数42，一直加到能满足“一个数被5除余2”。这步的原因是，42是6和7的最小公倍数，再怎么加都会满足“被6除余4，被7除余4”的条件。

46+42=88

46+42+42=130

46+42+42+42=172

例7：一个班学生分组做游戏，如果每组三人就多两人，每组五人就多三人，每组七人就多四人，问这个班有多少学生?

题目可以看成，除3余2，除5余3，除7余4。没有同余的情况，用的方法是“逐步约束法”，就是从“除7余4的数”中找出符合“除5余3的数”，就是再7上一直加7，直到所得的数除5余3。得出数为18，下面只要在18上一直加7和5得最小公倍数35，直到满足“除3余2”

4+7=11

11+7=18

18+35=53