下载文档原格式
簡介：韓信點兵又稱為中國剩餘定理，乃由於相傳漢高祖劉邦問大將軍韓信統御兵士多少，韓信答說，每3人一列餘1人、5人一列餘2人、7人一列餘4人、13人一列餘6人……。
劉邦茫然而不知其數。
韓信點兵是一個很有趣的猜數遊戲，隨便抓一把蠶豆粒，假若3個一數餘1粒，5個一數餘2粒，7個一數餘2粒，那麼所抓的蠶豆有多少粒?這類題目看起來是很難計算的，可是中國古時卻流傳著一種算法，它的名稱也很多，宋朝周密叫它「鬼谷算」，又名「隔牆算」；楊輝叫它「剪管術」；而比較通行的名稱是「韓信點兵」。
最初記述這類算法的是一本名叫「孫子算經」的書，後來在宋朝經過數學家秦九韶的推廣，又發現了一種算法，叫做「大衍求一術」，流傳到西洋以後，外國化稱它是「中國剩餘定理」，在數學史上是極有名的問題。
至於它的算法，在「孫子算經」上就已經有了說明：“凡三三數之剩一，則置七十；五五數之剩一，則置二十一；七七數之剩一，則置十五”，而且還流傳著這麼一首歌訣：三人同行七十稀，五樹梅花廿一枝，七子團圓正半月，除百零五便得知。
這就是韓信點兵的計算方法，《孫子算經》中給出了其中關鍵的步驟是：但在《孫子算經》中並沒有說明求乘數的方法，直到1247年宋代數學家秦九韶在《數書九章》中才給出具體求法：70是5與7最小公倍的2倍，21、15分別是3與7、3與5最小公倍數的1倍。
秦九韶稱這2、1、1的倍數為“乘率”，求出乘率，就可知乘數，意思是說：凡是用3個一數剩下的餘數，將它用70去乘（因為70是5與7的倍數，而又是以3去除餘1的），5個一數剩下的餘數，將它用21去乘（因為21是 3與 7的倍數，又是以5去除餘1的），7個一數剩下的餘數，將它用15去乘（因為15是3與5的倍數，又是以 7去除餘 1的），最後將70、5、15這些數加起來，若超過105，就再減掉105，所得的數便是原來的數了。
根據這個道理，你就可以很容易地把前面一個題目列成算式：1×70＋2×21＋2×15－105＝142－105＝37。
“韩信点兵法”和中国剩余定理中国古代数学有几项研究曾经远远领先于世界，被西方称为“中国剩余定理”的算法就是其中之一。
定理中蕴含的数学思想，在世界近代数学的很多分支中都可以找到其身影。
韩信是西汉时期的名将，同时也是中国历史上排得上号的著名军事家。
关于他有各种各样或真或假的传说，其中就有一个跟数学有很密切的关系。
据说有一次韩信率领1500人与楚军大战，楚军败退，汉军也伤亡四五百人。
韩信率军回营途中，军士又报告楚军来袭，韩信马上命令整队迎战。
他先按3人一排列队，多出2人；又按5人列队，多出3人；再按7人列队，多出2人。
于是他鼓舞士兵们说，我们一共有1073人，而楚军不足500人，我们一定能战胜楚军。
汉军士气大振，果然大败楚军。
这就是所谓“韩信点兵法”。
在这个故事中关于列队方式有各种不同的说法，但在数学上这都属于数论中的余数问题。
这类问题对于同余理论的发展有重要的推动作用。
中国数学家在余数问题上有很多世界领先的研究成果。
例如古代数学名著《孙子算经》里有一个问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。
问物几何？”翻译成数学语言就是：求正整数N，使N除以3余2，除以5余3，除以7余2。
如何求符合上述条件的正整数N呢？《孙子算经》给出了一个非常有效的巧妙解法。
“三、三数之剩二，置一百四十；五、五数之剩三，置六十三；七、七数之剩二，置三十，并之，得二百三十三。
以二百一十减之，即得。
凡三、三数之剩一，则置七十；五、五数之剩一，则置二十一；七、七数之剩一，则置十五。
一百六以上，一百五减之，即得。
”这段文言读起来有点拗口，但如果读完本文下面的内容，再回头看就不难理解了，所以暂时先不解释。
《孙子算经》后的一千多年，十六世纪的数学家程大位在其所著的《算法统宗》里以歌谣的方式给出了这个问题的解法。
三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得之。
在歌谣的前三句中，每句给出一组数，分别是(3,70)，(5,21)，(7,15)。
中国剩余定理与韩信点兵例1：一个两位数，用它除58余2，除73余3，除85余1，这个两位数是多少？分析解答：用一个两位数除58余2，除73余3，除85余1，那么58-2=56，73-3=7 0，85-1=84能被这个两位数整除，这个两位数一定是56、70和84的公约数。
由可可见，56、70、84的两位数公约数是27=14，可见这个两位数是14。
例2：有一个数，除以3余数是1，除以4余数是3，这个数除以12余数是多少？分析解答：因为除以3余数是1的数是1，4，7，10，13，16，19，22，25，28，31，…除以4余数是3的数是3，7，11，15，19，23，27，31…所以，同时符合除以3余数是1，除以4余数是3的数有7，19，31，…这些数除以12余数均为7。
例3：学习委员收买练习本的钱，她只记下四组各交的钱，第一组2.61元，第二组3.19元，第三组2.61元，第四组3.48元，又知道每本练习本价格都超过1角，全班共有_____人。
分析解答：根据题意得319-261=练习本单价第二、一组人数之差，348-319=练习本单价第四、二组人数之差。
即练习本单价第二、一组人数之差=58，练习本单价第四、二组人数之差=29，所以，练习本单价是58与29的公约数，这样，练习本的单价是29分，即0.29元。
因此，全班人数是[注]这里为了利用练习本单价是总价的公约数这一隐含条件，将小数化成整数来考虑，为解决问题提供了方便。
这里也可直接找261、319和348的公约数，但比较困难。
上述解法从一定意义上说是受了辗转相除法的启示。
拓展训练营：1、有一盒乒乓球，每次8个8个地数，10个10个地数，12个12个地数，最后总是剩下3个。
这盒乒乓球至少有多少个?2、求被6除余4，被8除余6，被10除余8的最小整数。
3、一盒围棋子，三只三只数多二只，五只五只数多四只，七只七只数多六只，若此盒围棋子的个数在200到300之间，问有多少围棋子?4、求一数，使其被4除余2，被6除余4，被9除余8。
中国剩余定律2010-05-25 19:15:29| 分类：Algorithm | 标签：|字号大中小订阅在中国数学史上，广泛流传着一个“韩信点兵”的故事：韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为汉朝的建立了卓绝的功劳。
据说韩信的数学水平也非常高超，他在点兵的时候，为了保住军事机密，不让敌人知道自己部队的实力，先令士兵从1至3报数，然后记下最后一个士兵所报之数；再令士兵从１至５报数，也记下最后一个士兵所报之数；最后令士兵从1至7报数，又记下最后一个士兵所报之数；这样，他很快就算出了自己部队士兵的总人数，而敌人则始终无法弄清他的部队究竟有多少名士兵。
这个故事中所说的韩信点兵的计算方法，就是现在被称为“中国剩余定理”的一次同余式解法。
它是中国古代数学家的一项重大创造，在世界数学史上具有重要的地位。
最早提出并记叙这个数学问题的，是南北朝时期的数学著作《孙子算经》中的“物不知数”题目。
这道“物不知数”的题目是这样的：“今有一些物不知其数量。
如果三个三个地去数它，则最后还剩二个；如果五个五个地去数它，则最后还剩三个；如果七个七个地去数它，则最后也剩二个。
问：这些物一共有多少？”用简练的数学语言来表述就是：求这样一个数，使它被３除余２，被５除余３，被７除余２。
《孙子算经》给出了这道题目的解法和答案，用算式表示即为：用现代的数学术语来说，这幅“开方作法本源图”实际上是一个指数为正整数的二项式定理系数表。
稍懂代数的读者都知道：《孙子算经》实际上是给出了这类一次同余式组的一般解：其中70、21、15和105这四个数是关键，所以后来的数学家把这种解法编成了如下的一首诗歌以便于记诵：“三人同行七十（７０）稀，五树梅花二一（２１）枝。
七子团圆正半月（１５），除百零五（１０５）便得知。
”《孙子算经》的“物不知数”题虽然开创了一次同余式研究的先河，但由于题目比较简单，甚至用试猜的方法也能求得，所以尚没有上升到一套完整的计算程序和理论的高度。
第六章 游戏中的数学逻辑第一节 韩信点兵与中国剩余定理一、“韩信点兵”和《孙子算经》1、“韩信点兵”的故事这里面有什么秘密呢？2、《孙子算经》中的题目我国古代数学名著《孙子算经》中，有“物不知数”的题目：今有物不知其数，三三数之剩2，五五数之剩3，七七数之剩2，问物几何？答案是23，那么，这个23 是如何求得的呢？二、问题的解答1、换个问题入手1）同类问题今有物不知其数，二二数之剩1，三三数之剩2，四四数之剩3，五五数之剩4，六六数之剩5，七七数之剩6，八八数之剩7，九九数之剩8，问物几何？2）筛法启发我们想到，要解原问题，只要从上边筛选下的数中，继续挑出“用4 除余3”的数：11，23，⋯再挑“用5 除余4”的数，⋯一直筛选下去，舍得下功夫，就一定可得结果，并且看起来，解，还不是唯一的，可能有无穷多个解。
3）公倍数法那么，除了刚才的筛法外，还有没有巧妙的解法？我们考察上边两个方程的特点，发现，两个“带余除法”的式子，都是“余数比除数少1”。
于是想到，如果把被除数再加1，不是余数就为0 了吗？换句话说，不是就出现整除的情况了吗？于每个方程两边都加上1，成为。
这说明，x +1既是2 的倍数，又是3 的倍数，因此，它是2 与3的公倍数。
如果用[2，3]表示2 和3 的最小公倍数，那么，因为公倍数都是最小公倍数的倍数，就有：x +1 = k [2,3], k =1,2,3,4, ⋯。
注意到[2，3]=6，所以“只有前两个条件的简化题目”的解为即 x = 6k −1,k =1,2,3,4,…有无穷多个解，即 x = 5,11,17,23, … 与前一解法结果相同。
的。
三、中国剩余定理1221.32x n x x n =+⎧⎨=+⎩中的1212(1)13(1)x n x n +=+⎧⎨+=+⎩。
中国古代史上最完美和最值得骄傲的数学成果：中国剩余定理导言：本文将介绍中国古代最完美和最值得骄傲的数学成果“中国剩余定理”，希望能有更多的读者和学生能重视我们国家的传统文化，并通过对中国剩余定理的了解和学习喜欢上数论。
在中外几乎每一本基础数论的教课书中，都会介绍一个被称之为“中国剩余定理”（Chinese Remainder Theorem）的知识。
在我的印象里，自己是在小学四五年级的时候接触到这个知识的，并知道如何去应用它，但要等到初中后才真正明白其原理。
中国剩余定理是中国古代史上最完美和最值得骄傲的数学成果，它是中国对世界数学思想史的重要贡献。
但很遗憾，现在的孩子大部分都已经不学这部分知识。
距我当年学习这部分内容已经近三十年了，我不知道我们的数学教育到底出了什么问题。
那么，今天我们就来了解和学习一下这个数论中的著名定理“中国剩余定理”。
第一部分：问题的起源中国剩余定理起源于我国南北朝时期的数学著作《孙子算经》，因此又名“孙子剩余定理”。
《孙子算经》，中国南北朝数学著作，《算经十书》之一。
全书共分三卷：上卷详细的讨论了度量衡的单位和筹算的制度和方法；中卷主要是关于分数的应用题，包括面积、体积、等比数列等计算题，大致都在《九章》中论述的范围之内；下卷对后世的影响最为深远，如下卷第31题即著名的“鸡兔同笼”问题，后传至日本，被改为“鹤龟算”。
下卷第26题“物不知数”为后来的“大衍求一术”的起源，被看作是中国数学史上最有创造性的成就之一，称为“中国剩余定理”。
经考证，《孙子算经》的作者与《孙子兵法》的孙武并非同一人。
“中国剩余定理”在古代有“韩信点兵”、“鬼谷算”、“求一术”、“隔墙算”、“剪管术”、“秦王暗点兵”、“物不知数”、“孙子定理”之名，是数论中主要命题，它不仅在抽象代数理论中有相应的推广，也被应用到密码学、哥德尔不完全性定理的证明、快速傅里叶变换理论等。
首先，引述《孙子算经》中“物不知数”的原文：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？答曰：二十三。
被７除1；15是3中国的这从此，中国例：一个住校生，家里每星期给他36元生活费。
该生每天实际只用生活费5元，某天他小姨到学校看他并给了50元钱，他用此钱买了两本喜爱的课外读物花10元，买学习用具花2元，放假回家后说明情况并给家长交回55元。
问：该生带几个星期的生活费？实际在校住几天？一共有多少钱？花去多少钱？用方法二解：列式（36×□＋50－10－2）÷5＝□……55元｛36×（5＋55-50＋10＋2）＋50－10－2｝÷（5×36）＝（36×22＋50－10－2）÷180＝830÷180 (110)答; 1，（110－50＋10＋2）÷36＝2，（括号内□内最小数）2，（110－55）÷5＝11，（括号外□内最小数）3 36×2＋50＝122，4，122－55＝67。
答：该生带2个星期的生活费，实际住校11天，一共有122元，花去67元。
2008.08.08先提醒大家过去曾经有过的一个经验.如果整数a除以整数b所得余数是1，那么，整数a的2倍、3倍、4倍、……、（b-1）倍除以整数b所得的余数就分别是1×2=2，1×3=3，1×4=4，…………1×（b-1）=b-1.例如，15÷7=2……余1，即2×15÷7=4 (2)3×15÷7=6 (3)4×15÷7=8 (4)5×15÷7=10 (5)6×15÷7=12 (6)还请大家注意一条经验.从某数a中连续减去若干个b后，求所得的要求小于数b的差数，实际上就是求数a除以数b所得的余数.例如，从758里连续减去若干个105后，求所得的要求小于105的差数，实际上就是求758除以105所得的余数.即758÷105=7 (23)下面我们就来研究“孙子问题”.在我国古代算书《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”意思是，“一个数除以3余2，除以5余3，除以7余2.求适合这个条件的最小数.”这个问题称为“孙子问题”.关于孙子问题的一般解法，国际上称为“中国剩余定理”.实际上，上面的问题我们可以这样来想：分别写出除数3、5、7的两两公倍数.如下表：我们在第一组数中选出合乎“除以7余2”的较小数——30；在第二组数中选出合乎“除以5余3”的较小数——63；在第三组数中选出合乎“除以3余2”的较小数——35.根据和的整除性，可知30+63+35=128一定是一个同时合乎“被3除余2，被5除余3，被7除余2”的数（为什么？），但是不一定是最小的.要得到合乎条件的最小数，只要从中减去3、5、7的最小公倍数的若干倍，使得差数小于这个最小公倍数就是了.3、5、7的最小公倍数是3×5×7=105，因此，由于前面的经验二，可知128÷105=1 (23)这个余数23就是要求的合乎条件的最小数.有意义的是，虽然孙老先生的解法也是从对上表的思索得到的，但他的解法更具有一般性.亲爱的读者，你能猜想到孙子的一般解法吗？【规律】一个数除以3余2，除以5余3，除以7余2，求适合这个条件的最小数.孙子的解法是：先从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就是合乎条件的最小数.以上三个步骤适合于解类似“孙子问题”的所有问题.【练习】1.韩信点兵：有兵一队，若列成五行纵队，则末行一人，成六行纵队，则末行五人，成七行纵队，则末行四人，成十一行纵队，则末行十人.求兵数.2.有一堆棋子，三个三个地数剩下2个，五个五个地数剩下4个，七个七个地数剩下6个.问这堆棋子最少有多少个？（用两种方法解）3.某数除以7余3，除以8余4，除以9余5.从小到大求出适合条件的十个数.4.某数除以5余2，除以7余4，除以11余8.求适合条件的最小数.5.一猴子数一堆桃子.两个两个地数剩下1个，三个三个地数剩下1个，五个五个地数剩下3个，七个七个地数剩下3个.问这堆桃子最少是多少个？注释:此步又称为求"模逆"运算,利用扩展欧几里得法并借助计算机编程可比较快速地求得.当然,对于很小的数,可以直接死算你看一下吧孙子算经》中给出这类问题的解法：“三三数之剩二，则置一百四十；五五数之剩三，置六十三；七七数之剩二，置三十；并之得二百三十三，以二百一十减之，即得。
001在我国数学文化最早是哪一年提出的？•A、1990.0•B、1992.0•C、2005.0•D、2008.0正确答案： A 我的答案：A2数学文化这个词最早出现于：•A、1986.0•B、1990.0•C、1974.0•D、1996.0正确答案： B 我的答案：A3数学文化这门课2002年被评为国家精品课程。
正确答案：×我的答案：√4数学是和其他的自然学科在同一个层次上的科学。
正确答案：×我的答案：√5数学的研究可以用到不同的自然科学。
正确答案：√我的答案：√6对数学文化中文化一词的界定，更倾向于广义的解释。
（）正确答案：×我的答案：×7何时首推建立32个“国家大学生素质文化教育基地”•A、1997年•B、1998年•C、1999年•D、2000年正确答案： C 我的答案：D1数学素养不包括（）•A、从数学的角度看问题•B、控制问题中的因素•C、有条理地理性思考•D、解决问题时的逻辑能力正确答案： B 我的答案：B2数学素养不是与生俱来的，是在学习和实践中培养的正确答案：√我的答案：√3企业招考员工的题和数学推理往往有关正确答案：√我的答案：√4数学素养的高低决定一个人工作的成效正确答案：√我的答案：×5数学不仅是一些知识还是一种素质（素养）。
正确答案：√我的答案：√6专业“数学素养”有几点？（）•A、五点•B、两点•C、四点•D、三点正确答案： B 我的答案：D1数学文化主要是关于（）的课程。
•A、数学知识•B、数学理论•C、数学应用•D、数学思想正确答案： D 我的答案：D2一般数学课程试以（）为线索组织教材。
•A、数学问题•B、知识系统•C、数学方法•D、数学思路正确答案： B 我的答案：A3狭义的数学文化是指数学的思想、精神、方法、观点、语言以及它们的形成和发展正确答案：√我的答案：√4数学文化课与高等数学课程没有什么区别正确答案：×我的答案：×5学习数学文化课程只需要学习高中的课程即可正确答案：×我的答案：×6数学归纳法的证明有几个步骤•A、一•B、二•C、三•D、四正确答案： B 我的答案：B7数学文化课的用到的数学基础知识只有初等数学。
中国剩余定理的应用实例——韩信点兵物不知其数问题出自一千六百年前我国古代数学名著《孙子算经》。
原题为："今有物不知其数，三三数之二，五五数之三，七七数之二，问物几何?"这道题的意思是：有一批物品，不知道有几件。
如果三件三件地数，就会剩下两件;如果五件五件地数，就会剩下三件;如果七件七件地数，也会剩下两件。
问：这批物品共有多少件?变成一个纯粹的数学问题就是：有一个数，用3除余2，用5除余3，用7除余2.求这个数。
这个问题很简单：用3除余2，用7除也余2，所以用3与7的最小公倍数21除也余2，而用21除余2的数我们首先就会想到23;23恰好被5除余3，所以23就是本题的一个答案。
这个问题之所以简单，是由于有被3除和被7除余数相同这个特殊性。
如果没有这个特殊性，问题就不那么简单了，也更有趣儿得多。
我们换一个例子;韩信点一队士兵的人数，三人一组余两人，五人一组余三人，七人一组余四人。
问：这队士兵至少有多少人?这个题目是要求出一个正数，使之用3除余2，用5除余3，用7除余4，而且希望所求出的数尽可能地小。
如果一位同学从来没有接触过这类问题，也能利用试验加分析的办法一步一步地增加条件推出答案。
例如我们从用3除余2这个条件开始。
满足这个条件的数是3n+2，其中n是非负整数。
要使3n+2还能满足用5除余3的条件，可以把n分别用1，2，3，…代入来试。
当n=1时，3n+2=5，5除以5不用余3，不合题意;当n=2时，3n+2=8，8除以5正好余3，可见8这个数同时满足用3除余2和用5除余3这两个条件。
最后一个条件是用7除余4.8不满足这个条件。
我们要在8的基础上得到一个数，使之同时满足三个条件。
为此，我们想到，可以使新数等于8与3和5的一个倍数的和。
因为8加上3与5的任何整数倍所得之和除以3仍然余2，除以5仍然余3.于是我们让新数为8+15m，分别把m=1，2，…代进去试验。
当试到m=3时，得到8+15m=53，53除以7恰好余4，因而53合乎题目要求。
韩信点兵
韩信点兵又称为中国剩余定理，相传汉高祖刘邦问大将军韩信统御兵士多少，韩信答说，每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/ 1。
