什么是中国剩余定理

 什么是中国剩余定理？

 

剩余定理详细解法

　　中国数学史书上记载：在两千多年前的我国古代算书《孙子算经》中，有这样一个问题及其解法：
　　今有物不知其数，三三数之剩二；五五数之剩三：七七数之剩二。问物几何？

　　意思 是说：现在有一堆东西，不知道它的数量，如果三个三个的数最后剩二个，如果五个五个的数最后剩三个，如果七个七个的数最后剩二个，问这堆东西有多少个？ 你知道这个数目吗？

　　《孙子算经》这道著名的数学题是我国古代数学思想“大衍求一术”的 具体体现，针对这道题给出的解法是： N=70×2＋21×3＋15×2-2×105＝23

　　如此巧妙的解法的关键是数字70、21和15的选择： 70是可以被5、7整除且被3除余1的最小正整数，当70×2时被3除余2 21是可以被3、7整除且被5除余1的最小正整数，当21×3时被5除余3 15是可以被3、5整除且被7除余1的最小正整数，当15×2时被7除余2 通过这种构造方法得到的N就可以满足题目的要求而减去2×105 后得到的是满足这一条件的最小正整数。

韩信点兵又称为中国剩余定理

　　韩信点兵又称为中国剩余定理，相传汉高祖刘邦问大将军韩信统御兵士多少，韩信答说，每3人一列余1人、5人一列余2人、7人一列余4人、13人一列余6人……。

　　刘邦茫然而不知其数。

　　我们先考虑下列的问题：假设兵不满一万，每5人一列、9人一列、13人一列、17人一列都剩3人，则兵有多少？

　　首先我们先求5、9、13、17之最小公倍数9945（注：因为5、9、13、17为两两互质的整数，故其最小公倍数为这些数的积），然后再加3，得9948（人）。

　　中国有一本数学古书「孙子算经」也有类似的问题：

　　「今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何？」答曰：「二十三」 术曰：「三三数之剩二，置一百四十，五五数之剩三，置六十三，七七数之剩二，置三十，并之，得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十，五五数之剩一，则置二十一，七七数之剩一，则置十五，即得。」

　　孙子算经的作者及确实着作年代均不可考，不过根据考证，着作年代不会在晋朝之后，以这个考证来说上面这种问题的解法，中国人发现得比西方早，所以这个问题的推广及其解法，被称为中国剩余定理。

　　中国剩余定理（Chinese Remainder Theorem）在近代抽象代数学中占有一席非常重要的地位。

中国剩余定理例题讲解1

中国剩余定理例题讲解2

一道中国剩余定理类型题（附两种解法）

　　一个三位数除以9余7，除以5余2，除以4余3，这样的三位数共有几个？

　　答案：

　　方法一：

　　用剩余定理做：

　　7*100+2*36+3*45=907

　　9、5、4的最小公倍数是：180 907/180=5。。。7

　　所以这样的三位数是：180*1+7=187 180*2+7=367 180*3+7=547 180*4+7=727 180*5+7=907

　　共有：五个

　　方法二：

　　枚举法： 类似题型若无特殊的条件，一般都通过枚举法找出符合条件的最小值，然后在此基础上加上各除数的最小公倍数，则可以得出相应的答案。

　　具体到此题，我们可以利用一些特殊条件缩小范围，减少枚举次数。

　　①因为除以4余3，因此该数为奇数；

　　②因为除以5余2，因此该数个位数为2或7，根据①，可知该数个位数应为7；

　　③因为除以9余7，结合②，该数最少应为97；结合①，经过尝试，得到符合条件的最小数值为187

　　④3个除数9、5、4的最小公倍数180，

　　因此符合条件的三位数有187、367、547、727、907共5个。

关于 中国剩余定理 的一道数学题

　　一条长长的阶梯，

　　如果每步跨 2 级，那么最后余 1 级；

　　如果每步跨 3 级，那么最后余 2 级；

　　如果每步跨 5 级，那么最后余 4 级；

　　如果每步跨 6 级，那么最后余 5 级；

　　如果每步跨 6 级，那么最后余 5 级；

　　只有当每步跨7级时，最后才刚好走完.

　　问这条台阶最少有 多少 级.

　　答案：

　　如果每步跨 2 级，那么最后余 1 级；

　　可知 是个奇数如果每步跨 3 级，那么最后余 2 级；

　　可知+1就是3的整数倍如果每步跨 5 级，那么最后余 4 级；

　　可知尾是4或9.但是是个奇数,所以是9如果每步跨 6 级，那么最后余 5 级；

　　可知+1就是6的整数倍只有当每步跨7级时，最后才刚好走完.

　　可知是7的整数倍7*7=49  7*17=119  49+1不是3的倍数,排除了.

　　119+1是3和6的整数倍,所以台阶有119级

 

在中国数学史上，广泛流传着一个“韩信点兵”的故事：
    韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为汉朝的建立了卓绝的功劳。据说韩信的数学水平也非常高超，他在点兵的时候，为了保住军事机密，不让敌人知道自己部队的实力，先令士兵从1至3报数，然后记下最后一个士兵所报之数；再令士兵从１至５报数，也记下最后一个士兵所报之数；最后令士兵从1至7报数，又记下最后一个士兵所报之数；这样，他很快就算出了自己部队士兵的总人数，而敌人则始终无法弄清他的部队究竟有多少名士兵。
    这个故事中所说的韩信点兵的计算方法，就是现在被称为“中国剩余定理”的一次同余式解法。它是中国古代数学家的一项重大创造，在世界数学史上具有重要的地位。
    最早提出并记叙这个数学问题的，是南北朝时期的数学著作《孙子算经》中的“物不知数”题目。这道“物不知数”的题目是这样的：
   “今有一些物不知其数量。如果三个三个地去数它，则最后还剩二个；如果五个五个地去数它，则最后还剩三个；如果七个七个地去数它，则最后也剩二个。问：这些物一共有多少？”
    用简练的数学语言来表述就是：求这样一个数，使它被３除余２，被５除余３，被７除余２。《孙子算经》给出了这道题目的解法和答案，用算式表示即为：

                    

用现代的数学术语来说，这幅“开方作法本源图”实际上是一个指数为正整数的二项式定理系数表。稍懂代数的读者都知道：

《孙子算经》实际上是给出了这类一次同余式组

   

的一般解：

其中70、21、15和105这四个数是关键，所以后来的数学家把这种解法编成了如下的一首诗歌以便于记诵：

                 “三人同行七十（７０）稀，
                   五树梅花二一（２１）枝。
                   七子团圆正半月（１５），
                   除百零五（１０５）便得知。”

《孙子算经》的“物不知数”题虽然开创了一次同余式研究的先河，但由于题目比较简单，甚至用试猜的方法也能求得，所以尚没有上升到一套完整的计算程序和理论的高度。真正从完整的计算程序和理论上解决这个问题的，是南宋时期的数学家秦九韶。秦
九韶在他的《数书九章》（见图１一７一１）中提出了一个数学方法“大衍求一术”，系统地论述了一次同余式组解法的基本原理和一般程序。
     秦九韶为什么要把他的这一套计算程序和基本原理称为“大衍求一术”呢？这是因为其计算程序的核心问题是要“求一”。所谓“求一”，通俗他说，就是求“一个数的多少倍除以另一个数，所得的余数为一”。那么为什么要“求一”呢？我们可以从“物不知数”题的几个关键数字７０、２１、１５中找到如下的规律：

其中70是5和7的倍数，但被3除余1；21是3和7的倍数，但被5除余1；15是3和5的倍数，但被7除余1，任何一个一次同余式组，只要根据这个规律求出那几个关键数字，那么这个一次同余式组就不难解出了。为此，秦九韶提出了乘率、定数、衍母、衍数等一系列数学概念，并详细叙述了“大衍求一术”的完整过程。（由于解法过于繁细，我们在这里就不展开叙述了，有兴趣的读者可进一步参阅有关书籍。）直到此时，由《孙子算经》“物不知数”题开创的一次同余式问题，才真正得到了一个普遍的解法，才真正上升到了
“中国剩余定理”的高度。
    从《孙子算经》到秦九韶《数书九章》对一次同余式问题的研究成果，在１９世纪中期开始受到西方数学界的重视。１８５２年，英国传教士伟烈亚力向欧洲介绍了《孙子算经》的“物不知数”题和秦九韶的“大衍求一术”；１８７６年，德国人马蒂生指出，中国的这一解法与西方１９世纪高斯《算术探究》中关于一次同余式组的解法完全一致。从此，中国古代数学的这一创造逐渐受到世界学者的瞩目，并在西方数学史著作中正式被称为“中国剩余定理”。

孙子剩余定理-正文

    

　　中国南北朝时期（5～6世纪）著名的著作《孙子算经》中“物不知数”问题所阐述的定理。物不知数问题的原题是：“今有物，不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”这属于数论的一次同余方程组问题。用现代数学符号可表为求下列同余方程的整数解：

式中

　　《孙子算经》中使用一种适合解一般的一次同余方程组的方法，求得此特殊问题的最小整数解N=23。解题步骤是：选定5×7的一个倍数，被3除余1，即70；选定3×7的一个倍数，被5除余1，即21；选定3×5的一个倍数，被7除余1，即15。然后按下式计算

式中105为3,5,7的最小公倍数，p为适当选取的整数,使得0＜N ≤105，这里取p=2。
　　上述问题和解法，可直接推广为定理：设α₁,α₂,…,α_n两两互素， 则

, (1)

有整数解,且对模M是惟一的。若记最小正整数解为N,则

,

式中k_j满足

。

p为适当选取的整数,使得N≤M。“物不知数”问题,在欧洲是一个知名的问题，C.F.高斯于19世纪初给出了它的一般性定理。因此国际上称上述《孙子算经》中的问题为孙子剩余定理或中国剩余定理。
　　《孙子算经》没有给出求k_j的具体算法。宋代秦九韶在《数书九章》中第一次详细地、完整地阐述了求解一次同余方程组的算法，他称做“大衍总数术”，其中包括求k_j的一种机械化算法──大衍求一术。
　　秦九韶称α_j为“定数”，k_j为“乘率”,由 中屡减α_j所得的余数G_j(<α_j)为“奇数”。“大衍求一术云：置奇右上，定居右下,立天元一于左上(图1 )。先以右上除右下，所得商数与左上一相生(即相乘)入左下。然后乃以右行上下以少除多，递互除之，所得商数随即递互累乘归左行上下，须使右上末后奇一而止。乃验左上所得，以为乘率。”秦九韶在例题中曾以G_j=3,α_j=4为例，列出求k_j的算草布式：

此时右上余1，故左上即为乘率k_j=3。
　　秦九韶还在历史上首次提出了当 α₁,α₂,…,α_n并非两两互素时, 求解(1)的方法。他设计了“两两连环求等,约奇弗约偶”，"复乘求定"等算法,先约去诸模数α₁,α₂,…,α_n中包含的多余的因子,得到新的一组 ,使 恰为 α₁,α₂,…,α_n的最小公倍数。再对 ,中的因子重新归并，得到 使 仍为α₁,α₂,…,α_n的最小公倍数，且它们两两互素。这样便将问题化约为模数两两互素的情形。秦九韶尚未提及当α₁,α₂,…,α_n并非两两互素时，方程(1)可解的条件。但从他所举八道例题中有七道的模数满足可解条件这一事实分析，许多人认为秦九韶已知道该条件。

 

例1、一个数除以3余2，除以5余3，除以7余2，求符合条件的最小数.
解：（1）先列出除以3余2的数：2， 5， 8， 11， 14， 17， 20， 23， 26，…，
（2）再列出除以5余3的数：3， 8， 13， 18， 23， 28，….
这两列数中，首先出现的公共数是8。
3与5的最小公倍数是15.两个条件合并成一个就是8＋15×整数，
（3）列出这一串数是8， 23， 38，…，
（4）再列出除以7余2的数 2， 9， 16， 23， 30，…，
就得出符合题目条件的最小数是23.

 

例2、有一个数，除以3余2，除以4余1，问这个数除以12余几？

解：（1）除以3余2的数有：2， 5， 8， 11，14， 17， 20， 23….
（2）除以4余1的数有：1， 5， 9， 13， 17， 21， 25， 29，….
（3）这两列数中，首先出现的公共数是5。
3和4的最小公倍数是12，两个条件合并成一个就是5＋12×整数
同时满足两个条件的数是5、17、29、……（依次增加12）
因此这个数除以12的余数是5.

例3、今有物不知其数，二二数之余一，四四数之余三，五五数之余二，七七数之余三，九九数之余四，问物几何？

解：（1）九九数之余四,可能的数是：13，22，31，40，49，58，……
（2）七七数之余三,可能的数是：10，17，24，31，……
（3）这两列数中，首先出现的公共数是31。
9和7的最小公倍数是63，两个条件合并成一个就是31＋63×整数
（4）同时满足上两个条件的数有：31，94，157，220，283，346，409，472，535，598，661，724，787，……
（5）上列的数中，只有157满足五五数之余二,
    5、7、9的最小公倍数是315，
（6）满足上面三个条件的数有：157，472，787，……
（7）只有787满足二二数余一，四四数余二。
所以，满足条件的数最小的是787。

练习：
1、一个数除以3余2，除以5余3，除以7余2，求满足条件的最小数？
2、满足除以5余1，除以7余3，除以8余5的最小自然数。
3、在10000以内，除以3余2，除以7余3，除以11余4的数有多少个？
4、求满足除以6余3，除以8余5，除以9余6的最小自然数。
5、一卷彩带，如果剪成2分米或3分米或5分米或6分米都剩1分米，如剪成每段为7分米正好不剩。这卷彩带至少多少米？
6、一个数除以5余4，除以8余3，除以11余2，求满足条件的最小的自然数。
7、有一堆苹果，3个3个数余1个，5个5个数余2个，6个6个数余4个。这堆苹果至少有多少个？
8、在小于1000的自然数中，除以4余3，除以5余2，除以7余4的最大自然数是多少？
9、在5000以内，除以3余1，除以5余2，除以7余3的自然数有多少个
10、有一个两位数，除以2与除以3都余1，除以4与除以5都余3，求这个数