下载文档原格式
韩信点兵问题与中国剩余定理今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二.问物几何？这段文字翻译成现代数学语言其实并不难，就是一个数同时满足除以3余数是2，除以5余数是3，除以7余数是2，问这个数是多少？此类问题古人称为“韩信点兵问题”,据说是韩信不用过问兵的数量，只需让士兵变换方阵即可快速得出士兵的数量，也不知道是真是假，如果是真的，那韩信也算是一个数学过硬的将军了.上过小学的同学都知道，我们随便试几个数就可以很快发现，23就是第一个满足的数字.然而，你要找到更多的数字，那就有些难度了.要是换成更大的数字，例如一个数除以5余1，除以6余5，除以7余4，除以11余10，那这样的数如何去求呢？这就是今天小编要分享的是中国剩余定理.中国剩余定理是唯一一个以国家命名的定理，“韩信点兵问题”的记载最早出自南北朝数学名著《孙子算经》,中国剩余定理也叫孙子定理.这个问题放在现在肯定是不难求解的，接触过初等数论的同学就知道，只需解一个同余式组.)5(mod 3)3(mod 2N )7(mod 2{≡≡≡N N 的最小正整数解.方法一：大衍求一术公元13世纪，大数学家秦九韶集前法之大成，终于在一次同余式的研究上获得超越前人的辉煌成果，系统的阐述了“大衍求一术”，到了明代，著名大数学家程大位，在他的《算法统宗》中，还编写了四名歌诀：三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知.意思不难理解：三个人一同走路，70岁的老者很少，五棵梅花树上一共有21朵梅花，7个孩子在每月十五团圆，把这些数减去105便能得出答案.为什么？其中的原理还是让多数人摸不着头脑的,程大位数学家就更加详细了：①找出能被5与7整除而被3除1的数70，被3与7除而被5除余1的数21，被3与5整除而被7余1的数15；②把70、21、15这三个数字分别乘以它们的余数，再把三个积加起来是233，由于63与30都能被3整除，故233与140这两数被3除的余数相同，都是2.同理，233与63被5除余数是3；233与30被7除余数是2，所以233是满足题目的一个数；③而3，5，7的最小公倍数是105，故233加减105的整数倍后被3，5，7除的余数不会变，从而所得的数都能满足题目的要求.故105n+23就是问题的解.方法二：等差数列法学过小学奥数的同学或者学过高中数学数列的同学非常好理解，三三数之余二，即3n+2，穷举得2，5，8，11，14........，从这些数中找到除以5余数是3的数，第一个数是8，故15n+8满足前两条件；再从15n+8的数中找到23满足除以7余2，而15和7的最小公倍数为105，故105n+23即满足所有条件.是不是相当简单？方法三：不定方程法设这个数为n ，则有273523+=+=+=z n y n x n 消去n 可得,175135-=--=-z y x y ，再消去y 得z z z x 31237+==，而x 为整数，可令k =z 31，即有z =3k ,x =7k ，代入可得5y -21k =-1,可得y =21k ′+4，代入可得n =105k ′+23,此法亦不难理解，初中生学过方程的即可.当然，还是一个核心的问题，这类问题有没有固定的解法，一旦数字改变，那解法可能会变得复杂，甚至算不出来.其实是有的.古人也早就提出了解法，不过具体原因在哪里，很多人是不明白的.如下：三三数之剩二，置一百四十，五五数之剩三，置六十三，七七数之剩二，置三十，并之，得二百三十三，以二百一十减之，即得。
簡介：韓信點兵又稱為中國剩餘定理，乃由於相傳漢高祖劉邦問大將軍韓信統御兵士多少，韓信答說，每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。
韩信点兵的故事及数学知识
韩信点兵的故事是一个著名的数学问题，它在中国古代数学史上占有重要地位。
这个故事描述的是韩信在点兵时，通过利用余数的方法来判断士兵的数量。
故事背景是秦朝末年，楚汉相争时期。
韩信作为刘邦的部下，需要点兵迎战。
他让士兵们每排站3人，结果多出2名；每排站5人，结果多出3名；每排站7人，结果多出2名。
通过这一系列条件，韩信得知了总共有1073名士兵。
这个问题的核心是利用余数来判断士兵的数量。
当士兵们每排站3人时，多出2人，即士兵总数除以3的余数是2。
同样地，当每排站5人时，多出3人，即士兵总数除以5的余数是3。
当每排站7人时，多出2人，即士兵总数除以7的余数是2。
因此，我们可以使用中国剩余定理来解决这个问题。
中国剩余定理是指在整数系中，给定一组线性同余方程（组），存在一个整数n，使得n对这组同余方程（组）的余数均为0。
在这个问题中，我们可以设士兵总数为n，那么n对3、5、7的余数分别为2、3、2。
因此，我们可以得到一组线性同余方程：
n ≡ 2 (mod 3)
n ≡ 3 (mod 5)
n ≡ 2 (mod 7)
通过解这组方程，我们可以得到士兵的总数为1073。
这个故事展示了数学在古代中国的广泛应用。
通过数学方法来解决实际问题，不仅体现了数学的实用性，也展示了古代中国在数学领域的卓越成就。
韩信点兵——中国剩余定理韩信是中国古代一位有名的军事家，民间流传着许多他的故事，韩信点兵便是其中之一。
秦朝末年，楚汉相争。
一次，韩信率1500名将士与楚王大将李锋交战。
苦战一场，楚军不敌，败退回营，于是，韩信整顿兵马也返回大本营。
当行至一山坡，忽有后军来报，说有楚军骑兵追来。
只见远方尘土飞扬，杀声震天。
汉军本来已十分疲惫，这时队伍大哗，韩信兵马到坡顶，见来敌不足五百骑，便急速点兵迎敌。
韩信命令士兵3人一排，结果多出2名；接着命令士兵5人一排，结果多出3名；他又命令士兵7人一排，结果又多出2名。
韩信马上向将士们宣布：“我军有1073名勇士，敌人不足五百，我们居高临下，以众击寡，一定能打败敌人。
”一时间旌旗摇动，鼓声喧天，汉军步步逼近，楚军乱作一团。
交战不久，楚军大败而逃。
部将好奇地问韩信：“大帅是如何迅速地算出我军人马的呢？”韩信说：“根据编队时排尾的余数算出来的。
”韩信到底是怎么算出来的呢？这也是中国古代的一道趣味算术题。
有一首四句诗隐含了解题的思路：“三人同行七十稀，五树梅花廿一枝。
七子团圆正半月，除百零五便得知。
”诗里让人记住这几个数字：3与70，5与21，7与15，还有105（也就是3、5、7的公倍数）。
这些数是什么意思呢？题中3人一列多2人，用2×70；5人一列多3名，用3×21；7人一列多2人，用2×15，三个乘积相加：2×70+3×21+2×15=233用233除以3余2，除以5余3，除以7余1，符合题中条件。
但是，因为105是3、5、7的公倍数，所以233加上或减去若干个105仍符合条件。
这样一来，128、338、443、548、653……都符合条件。
总之，233加上或减去105的整数倍，都可能是答案。
韩信根据现场观察，得出了1073这个数字。
诗歌里的数字又是怎么得来的呢？70是5和7的公倍数，除以3余1；21是3和7的公倍数，除以5余1；15是3和5的公倍数，除以7余1。
“韩信点兵法”和中国剩余定理中国古代数学有几项研究曾经远远领先于世界，被西方称为“中国剩余定理”的算法就是其中之一。
定理中蕴含的数学思想，在世界近代数学的很多分支中都可以找到其身影。
韩信是西汉时期的名将，同时也是中国历史上排得上号的著名军事家。
关于他有各种各样或真或假的传说，其中就有一个跟数学有很密切的关系。
据说有一次韩信率领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。
中国剩余定理的应用实例——韩信点兵物不知其数问题出自一千六百年前我国古代数学名著《孙子算经》。
原题为："今有物不知其数，三三数之二，五五数之三，七七数之二，问物几何?"这道题的意思是：有一批物品，不知道有几件。
如果三件三件地数，就会剩下两件;如果五件五件地数，就会剩下三件;如果七件七件地数，也会剩下两件。
问：这批物品共有多少件?变成一个纯粹的数学问题就是：有一个数，用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除时余2，被5除时余3，被7除时余2，如果这数不超过100，求这个数。
” 《孙⼦算经》中给出这类问题的解法：“三三数之剩⼆，则置⼀百四⼗；五五数之剩三，置六⼗三；七七数之剩⼆，置三⼗；并之得⼆百三⼗三，以⼆百⼀⼗减之，即得。
凡三三数之剩⼀，则置七⼗；五五数之剩⼀，则置⼆⼗⼀；七七数之剩⼀，则置⼗五，⼀百六以上，以⼀百五减之，即得。
”⽤现代语⾔说明这个解法就是： ⾸先找出能被5与7整除⽽被3除余1的数70，被3与7整除⽽被5除余1的数21，被3与5整除⽽被7除余1的数15。
所求数被3除余2，则取数70×2＝140，140是被5与7整除⽽被3除余2的数。
中国剩余定律2010-05-25 19:15:29| 分类：Algorithm | 标签：|字号大中小订阅在中国数学史上，广泛流传着一个“韩信点兵”的故事：韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为汉朝的建立了卓绝的功劳。
据说韩信的数学水平也非常高超，他在点兵的时候，为了保住军事机密，不让敌人知道自己部队的实力，先令士兵从1至3报数，然后记下最后一个士兵所报之数；再令士兵从１至５报数，也记下最后一个士兵所报之数；最后令士兵从1至7报数，又记下最后一个士兵所报之数；这样，他很快就算出了自己部队士兵的总人数，而敌人则始终无法弄清他的部队究竟有多少名士兵。
这个故事中所说的韩信点兵的计算方法，就是现在被称为“中国剩余定理”的一次同余式解法。
它是中国古代数学家的一项重大创造，在世界数学史上具有重要的地位。
最早提出并记叙这个数学问题的，是南北朝时期的数学著作《孙子算经》中的“物不知数”题目。
这道“物不知数”的题目是这样的：“今有一些物不知其数量。
如果三个三个地去数它，则最后还剩二个；如果五个五个地去数它，则最后还剩三个；如果七个七个地去数它，则最后也剩二个。
问：这些物一共有多少？”用简练的数学语言来表述就是：求这样一个数，使它被３除余２，被５除余３，被７除余２。
《孙子算经》给出了这道题目的解法和答案，用算式表示即为：用现代的数学术语来说，这幅“开方作法本源图”实际上是一个指数为正整数的二项式定理系数表。
稍懂代数的读者都知道：《孙子算经》实际上是给出了这类一次同余式组的一般解：其中70、21、15和105这四个数是关键，所以后来的数学家把这种解法编成了如下的一首诗歌以便于记诵：“三人同行七十（７０）稀，五树梅花二一（２１）枝。
七子团圆正半月（１５），除百零五（１０５）便得知。
”《孙子算经》的“物不知数”题虽然开创了一次同余式研究的先河，但由于题目比较简单，甚至用试猜的方法也能求得，所以尚没有上升到一套完整的计算程序和理论的高度。
