剩余定理，什么是剩余定理

本文目录一览

1，什么是剩余定理
2，什么叫中国剩余定理
3，中国数学剩余定理

1，什么是剩余定理

我国古代算书《孙子算经》中，有这样一个问题：“今有物不知其数：三三数之剩二，五五数之剩三，七七数之剩二，问物几何．”这个问题一般称孙子问题．这个问题可译成：求被3除余2，被5除余3，被7除余2的最小正整数．《孙子算经》中记载了这个问题的解法，有人将其解法编成歌诀：“三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五便得知．”它的意思是用3除的剩余数乘70，用5除的剩余数乘21，用7除的剩余数乘15，将所得的结果相加再减去105的倍数，即可得所求数．算式是2×70＋3×21＋2×15=233，233－105×2＝23，所以，最小的正整数解是23．这种解法，实际上是特殊的一次同余式组的求解定理．1801年，德国数学家高斯在《算术探究》中明确提出一次同余式组的求解定理．西方数学著作中将一次同余式的求解定理称为中国剩余定理．

什么是剩余定理

2，什么叫中国剩余定理

中国剩余定理释义：又称“孙子定理”。1852年，英国来华传教士伟烈亚力将《孙子算经》中“物不知数”问题的解法传至欧洲。1874年，英国数学家马西森指出此法符合1801年由高斯得出的关于同余式解法的一般性定理，因而西方称之为“中国剩余定理”。孙子定理是中国古代求解一次同余式组（见同余）的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。扩展资料：中国剩余定理说明：假设整数m1,m2, ... ,mn两两互质，则对任意的整数：a1,a2, ... ,an，方程组有解，并且通解可以用如下方式构造得到：设是整数m1,m2, ... ,mn的乘积，并设是除了mi以外的n- 1个整数的乘积。方程组的通解形式为一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题，原文如下：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数。《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。宋朝数学家秦九韶于1247年《数书九章》卷一、二《大衍类》对“物不知数”问题做出了完整系统的解答。明朝数学家程大位将解法编成易于上口的《孙子歌诀》：三人同行七十稀，五树梅花廿一支，七子团圆正半月，除百零五使得知这个歌诀给出了模数为3、5、7时候的同余方程的秦九韶解法。意思是：将除以3得到的余数乘以70，将除以5得到的余数乘以21，将除以7得到的余数乘以15，全部加起来后减去105（或者105的倍数），得到的余数就是答案。比如说在以上的物不知数问题里面，按歌诀求出的结果就是23。参考资料：百度百科---孙子定理

什么叫中国剩余定理

3，中国数学剩余定理

中国剩余定理，又叫中国余数定理，是数论中的一个关于一元线性同余方程组的定理，说明了一元线性同余方程组有解的准则以及求解的方法。也称为孙子定理，古有"韩信点兵"，"孙子定理"，"求一术"(宋沈括)，"鬼谷算"，"隔墙算"，"剪管术"(宋杨辉)，"秦王暗点兵"之名。原文如下：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？即，一个整数除以三余二，除以五余三，除以七余二，求这个整数解答方法：三人同行七十希，五树梅花廿一枝，七子团圆正半月，除百零五便得知。意思是:将除以3得余数乘以70，将除以5得余数乘以21，将除以7得余数乘以15，全部加起来后再减去105或105的整倍数，得到的数就是答案。70X2+21x3+15x2=233=105x2+23，结果就是23。解法举例：例一：一个数，除以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=8846+42+42=13046+42+42+42=172这个数最小是172.

中国数学剩余定理