《韩信点兵》公式

简介：韩信点兵又称为中国剩余定理，乃由于相传汉高祖刘邦问大将军韩信统御兵士多少，韩信答说，每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人一列餘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。

[阅读材料]世界名题与小升初之：韩信点兵问题在各类竞赛中，各类小升初考试中相关的世界名题出现的概率极高，这是由小升初与数学竞赛的特点决定，这特点便是：知识性，趣味性，思想性相结合。

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

刘邦茫然而不知其数。

我们先考虑下列的问题：假设兵不满一万，每5人一列、9人一列、13人一列、17人一列都剩3人，则兵有多少？首先我们先求5、9、13、17之最小公倍数9945（注：因为5、9、13、17为两两互质的整数，故其最小公倍数为这些数的积），然後再加3，得9948（人）这个数就满足要求。

韩信点兵问题，是后人对物不知其数问题的一种故事化。

这个问题俗为［韩信点兵］，又叫做「秦王暗点兵」、「鬼谷算」、「隔墙算」、「剪管术」、「神奇妙算」、「大衍求一术」等等），它属于数论(Number theory) 中的「不定方程问题」(Indeterminate equations)。

例2：物不知其数问题出自一千六百年前我国古代数学名著《孙子算经》。

在《孙子算经》里（共三卷，据推测约成书于公元400年左右），下卷的第26题，就是鼎鼎有名的「孙子问题」原题为："今有物不知其数，三三数之二，五五数之三，七七数之二，问物几何？"这道题的意思是：有一批物品，不知道有几件。

如果三件三件地数，就会剩下两件；如果五件五件地数，就会剩下三件；如果七件七件地数，也会剩下两件。

问：这批物品共有多少件？变成一个纯粹的数学问题就是：有一个数，用3除余2，用5除余3，用7除余2。

求这个数。

这个问题很简单：用3除余2，用7除也余2，所以用3与7的最小公倍数21除也余2，而用21除余2的数我们首先就会想到23；23恰好被5除余3，所以23就是本题的一个答案。

这个问题之所以简单，是由于有被3除和被7除余数相同这个特殊性。

【2017年整理】韩信点兵问题的初等解法“韩信点兵”问题的初等解法研究王晓东河北省卢龙县燕河营镇中学 066407韩信，是我国汉代刘邦手下的一员能征善战，智勇双全的大将。

历史上流传着一个关于他运用奇特方法点兵的传说。

有一天，韩信来到操练场，检阅士兵操练。

他问部将，今天有多少士兵操练，部将回答:“大约两千三百人。

”韩信走上点兵台，他先命全体士兵排成7路纵队，问最后一排剩几人，部将说，剩2人;他又命全体士兵排成5路纵队，问最后一排剩几人，部将说，剩3人;最后，他又让全体士兵排成3路纵队，问最后一排剩几人，部将说，剩2人。

韩信告诉部将，今天参加操练的士兵有2333人。

从现代数学的观点来看，解决韩信点兵问题，可以这样思考:设操练士兵的总数为M，则M=3x+2=5y+3=7z+2其中，x，y，z分别表示排成3路纵队，5路纵队，7路纵队的纵队数目。

求出了x，y，z以后，M也求求出来了。

而求x，y，z可以看成求方程组3x+2=5y+33x+2=7z+2的正整数解。

在上面的方程组中，未知数的个数多于方程的个数，则把这种方程(组)叫做不定方程(组)。

不定方程(组)的解是不确定的，一般不定方程总有无穷多个组解，但若加上整数(或正整数)解的特定限制，则不定方程(组)的解有三种可能:有无限组解，有限组解，或无解。

我国古代人民对于不定方程(组)这类问题解法的探讨有着悠久的历史，在中国古代的《孙子算经》中曾作为一个典型问题进行论述。

其中的一个经典例题是:今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物有几何,答曰:二十三。

术曰:三三数之剩二，则置一百四十;五五数之剩三，则置六十三;七七数之剩二，则置三十;并之得二百三十三，以二百一十减之，即得。

凡三三数之剩一，则置七十;五五数之剩一，则置二十一;七七数之剩一，则置十五。

一百(零)六以上，以一百(零)五减之，即得。

在中国民间还广为流传着一个口诀:三人同行七十稀，五树梅花二十一。

韩信点兵算法及其原理【问题】求最小非负整数N，使他在除以3,5,7以后所得余数分别是a,b,c。

【韩信点兵法的口诀】三人同行七十稀，五树梅花廿一枝，七子团圆整半月，除百零五便得知。

【韩信点兵法口诀的释义】前三句意思较为明确，假如说一个非负整数N，在除以3,5,7以后所得余数分别是a,b,c。

那么70a+21b+15c 一定是符合题意要求的数。

第四句“除”字作“减”字解。

因为符合要求的最小数N必满足0≤N＜105，但是70a+21b+15c 却有可能大于105，甚至大于210，所以还不一定是符合要求的最小数。

那么当他大于或等于105时，还必须减去105，可能还要再减去105，直到比105小为止，才可以得到符合题意要求的最小数。

【说明】这里105是3,5,7的最小公倍数，70a+21b+15c + 105k 也一定满足“除以3,5,7以后所得余数分别是a,b,c”。

【例如】a=b=c=2，70a+21b+15c=212，70a+21b+15c-105=107＞105。

而符合题意要求的最小数是 2，即 212-105-105=2.【再如】a=2,b=4,c=6，70a+21b+15c=314，314-105=209＞105。

而符合题意要求的最小数是 104，即 314-105-105=104.【韩信点兵法口诀的原理】①能被5,7除尽数是35k,其中k=2，即70除3正好余1，70a 除3正好余a。

②能被3,7除尽数是21k,其中k=1，即21除5正好余1，21b 除5正好余b。

③能被3,5除尽数是15k,其中k=1，即15除7正好余1，15c 除7正好余c。

这样——根据①可知 70a+21b+15c 除3正好余a。

根据②可知 70a+21b+15c 除5正好余b。

根据③可知 70a+21b+15c 除7正好余c。

【韩信点兵法口诀的局限性】只适宜于如题所示的一个极为特殊的问题，要推广到同类问题必须另行制作口诀（即公式）。

韩信点兵问题的神解法定理1：一个数除以a余数x，除以b余数y，a、b互质且a<b，求这个数的最小值。

设这个数为z，则z=b(an+x-y)/(b-a)+y (1)或z=a(bn+x-y)/(b-a)+x (2)其中n为使(bn+x-y)/(b-a)为正整数的最小值。

证明：设z=al+x=bm+y 则：al+x-y-am=(b-a)m所以m=(a(l-m)+x-y)/(b-a)将变量l-m用独立变量n代替：m= (an+x-y)/(b-a)将m代入以上等式得到：z=b(an+x-y)/(b-a)+y同理可以证明等式2定理2：在定理1等式中，0<=n<=b-a。

证明：从定理1等式中可知n=l-m，因为a<b，所以l>=m，故n>=0假设n=h(b-a)+k，k<=b-a 代入以上算式z=b(ah(b-a)+ak+x-y)/(b-a)+y=ahb+b(ak+x-y)/(b-a)，由此可知，n可以取值为k。

根据以上两个定理来计算韩信点兵问题，具有两个方面的优点：1、将两个变量合并成了一个变量，从而只需要尝试一个变量即可。

2、这一个变量的范围被两个除数的值界定，需要尝试的最多次数是确定的。

例1：一个数除以9余5，除以13余4，求这个数的最小值列出算式：13*(9n+5-4)/(13-9)+4=13*(9n+1)/4+4显然能让相除结果为整数的n的最小值为3，代入则得：13*(9*3+1)/4+4=95。

例2：一个数除以13余10，除以17余5，求这个数的最小值列出算式：17*(13n+10-5)/(17-13)+5=17*(13n+5)/4+5显然能让相除结果为整数的n的最小值也为3，代入则得：17*(13*3+5)/4+5=192以上算法比传统算法更简便，但依然有缺陷，即如果除数的值比较大时，要获得满足条件的n的值尝试的次数也会相应增大，从而对于大数相除时也会计算量太大，无法手算，用计算机计算也会比较耗时。

韩信点兵【历史故事】
韩信点兵⼜称为中国剩余定理，相传汉⾼祖刘邦问⼤将军韩信统御兵⼠多少，韩信答说，每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）在近代抽象代数学中占有⼀席⾮常重要的地位。

韩信点兵算法原理韩信点兵算法，又称为“鸡兔同笼”问题，是一个古老而经典的数学问题。

传说在韩信率领军队作战时，曾遇到一只笼子里面关着鸡和兔，但是不知道究竟有多少只。

为了解决这个问题，韩信便想出了一个巧妙的算法，从而得以知道笼子里究竟有多少只动物。

这个算法被后人称为“韩信点兵算法”，成为了解决类似问题的经典方法。

韩信点兵算法的原理其实并不复杂，它主要是利用了数学的思维和逻辑推理。

首先，我们需要知道鸡和兔的特点，鸡有两只脚，兔有四只脚。

基于这一特点，韩信想到了一个巧妙的方法来解决问题。

他首先让笼子里的动物全部跑出来，然后让它们排成一队。

接着，韩信开始数脚，他一共数到了n只脚。

接下来，他就可以根据这个数字n来推算出笼子里究竟有多少只动物了。

具体的推算方法是这样的，假设鸡有x只，兔有y只，那么根据鸡和兔的脚的数量，我们可以得到一个方程组，2x + 4y = n，而且x + y = n。

通过解这个方程组，就可以得到鸡和兔的数量了。

这个算法的精髓在于，通过观察问题的特点，找到了一个可以描述问题的数学模型，然后通过求解这个数学模型，就可以得到问题的解。

这种思维方式，体现了数学在解决实际问题中的巨大力量。

除了解决鸡兔同笼问题之外，韩信点兵算法还可以应用到其他类似的问题当中。

比如，在日常生活中，我们经常会遇到一些关于数量和关系的问题，而韩信点兵算法正是一个非常好的思路和方法，可以帮助我们解决这类问题。

总的来说，韩信点兵算法是一个非常巧妙而经典的数学问题解决方法。

它通过观察问题的特点，建立数学模型，然后通过数学方法求解，最终得到问题的解。

这种思维方式不仅在数学领域有着广泛的应用，而且在日常生活中也能够帮助我们解决一些实际问题。

因此，学习和掌握韩信点兵算法的原理和方法，对我们提高数学思维能力，解决实际问题都有着重要的意义。