中职教育二年级下学期数学《韩信点兵与中国剩余定理》课件

韩信点兵与中国剩余定理韩信点兵的故事

韩信是西汉时期的名将，也是我国著名的军事家，“汉初三杰”，“兵家四圣”，古代军事思想“兵权谋家”的代表人物。关于他有各种各样或真或假的传说，其中就有一个跟数学有很密切的关系。韩信点兵的故事3人一排，多出2人5人一排，多出3人7人一排，多出2人韩信点兵的故事韩信据此很快说出人数：1073人。汉军本来就十分信服韩信大将军，经此之后就更加相信韩信是“天神下凡，神机妙算"，于是士气大振，鼓声喧天，在接下来的战役中汉军步步紧逼，楚军乱作一团，大败而逃。韩信由此名扬天下，被后世誉为“兵仙“，“神帅”。那么韩信是如何快速算出士兵人数的呢？

我们先把韩信点兵问题转化为数学语言：一个数除以3余2，除以5余３，除以7余２。用“筛法”解决韩信点兵问题

把所有正整数过第一遍筛子，筛选出“三三数之剩2”的数，即“用3除余2”的数，有2，5，8，11，14，17，20，23，26，29，……

再把这些数过第二遍筛子，筛选出“五五数之剩3”的数，即“用5除余3”的数，有8，23……

再把这些数过第三遍筛子，筛选出“七七数之剩2”的数，即“用7除余2”的数，有23……

由此得到23是最的１个解。筛法

把这里的解题方法总结为“筛法”，筛法就成为一般性方法，还可以用来解决其他类似问题。由于每次筛选后，都还有无穷多个数，所以解可能不是唯一的，很可能有无穷多个解。至于下一个解是什么，要把……写出来才知道。实践发现这是要费一点功夫的。那有没有简单的方法来解决这个问题呢？用“歌谣”解决韩信点兵问题明朝，我国著名的数学家程大位在《算法统宗》里以歌谣的方式给出了这个问题的解法。

三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得之。在歌谣的前三句中，每句给出一组数，分别是(3,70)，(5,21)，(7,15)。在这三组数中，每一组的前一个数就是“韩国点兵”问题中出现的三个除数3、5、7，那么后一个数呢？先来看70，这个数是除以3余1且被5和7整除的最小的数。类似地，21是除以5余1且被3和7整除的最小的数，15是除以7余1且被3和5整除的最小的数。用“歌谣”解决韩信点兵问题现在来看下面这个数：M=2×70+3×21+2×15我们检验一下M除以3、5、7的余数。注意到M是三个乘积的和，由于70被3除余1，所以第一个乘积2×70被3除余2。而后两个乘积都能被3整除，因此M被3除余2。再来看M除以5的余数。由于第一和第三个乘积都被5整除，而第二个乘积被5除余3，所以M被5除余3。类似地可以推出M被7除余2。综上所述，M被3除余2，被5除余3，被7除余2，正好是故事《韩信点兵》中所提问题的答案。容易算出M的值是233。用“歌谣”解决韩信点兵问题我们利用歌谣的前三句已经给出了问题的答案，最后一句“除百零五便得知”有什么作用呢？是不是只为了凑足四句话？非也。上面虽然给出了满足三个余数条件的一个数，但这样的数是无穷多的。这些数有一个特点，即任两个数的差都是3、5、7的公倍数。当问题的解不唯一时，数学家通常对最小解比较感兴趣。歌谣的最后一句话，意思就是用233减去若干个3、5、7的最小公倍数105，余数23就是答案。在“韩信点兵”的故事中要求的是大于1000且满足三个余数条件的数，所以要用23加上105的10倍，答案即为1073。

程大位通过构造三个特殊的数70,21,15，解决了一般的以3、5、7为除数的余数问题——为构造被3除余a、被5除余b、被7除余c的数，只需计算N=a×70+b×21+c×15N必定满足所有余数条件，而满足条件的最小数则是N减去若干个105后的数。单因子构件凑成法如果直接套用程大位的歌谣公式，只能限于解决除数为3、5、7的余数问题。当除数换成其他数时，在解法中需要做相应的调整。例如，当三个除数分别为3、7、11时，我们首先要构造被3除余1且被7、11整除的数。列出7和11的公倍数77,154,231,……，其中被3除余1的最小的数是154。其次求被7除余1且被3、11整除的数，最小的是99。最后求被11除余1且被3、7整除的数，最小的是210。于是，被3除余a、被7除余b、被11除余c的数就是

Ｎ＝a×154+b×99+c×210如果要找满足所有余数条件的最小的数，只需再用这个数减去若干个3、7、11的最小公倍数231即可。试一试：一个数被3除余2，被7除余4，被11除余5，那这个数最小是多少？Ｎ＝2×154+4×99+5×210＝1754，1754-231×7=137单因子构件凑成法

在上面的算法流程中，唯一需要变化调整的是三个具有特殊余数的数。当除数为(3，5，7)时，它们是(70，21，15)；当除数为(3，7，11)时，它们是(154，99，210)。无论除数是什么，第一个数关于三个除数的余数为1，0，0，第二个数关于三个除数的余数为0，1，0，第三个数关于三个除数的余数为0，0，1。

同学，你通过观察，会发现这个两个问题在数学思想上两者根本就是一回事。如果理解清楚了这个思想，就很容易明白如果问题中涉及四个、五个甚至更多余数条件，这个算法仍然适用。

例如，要求被2，3，5，7除的余数分别为a,b,c,d的数，我们只需相应构造四个数。第一个数是3,5,7的公倍数且被2除余1，容易求得是105。第二个数是2,5,7的公倍数且被3除余1，是70。第三个数是2,3,7的公倍数且被5除余1，是126。第四个数是2,3,5的公倍数且被7除余1，是120。所以a×105+b×70+c×126+d×120。除以2,3,5,7的余数恰好分别是a，b，c，d。孙子定理

由于余数问题最早出自《孙子算经》，所以上面的算法在中国被称为“孙子定理”。美国计算机科学的泰斗高德纳在其著作《计算机程序设计艺术》中也专门介绍了这个算法。“孙子定理”的重要意义，远远不止是对一类余数问题给出了统一的算法。在余数问题中除数可能有三个、四个甚至更多，余数的值也有很多变化。而“孙子定理”只需要求解几个余数很特殊的问题的解，就能把一般问题的解完全表示出来，即用“特解”表示出“通解”。这样的思想在近代数学很多重要分支的发展中都被广泛使用。中国剩余定理

不过“孙子定理”在解决余数问题时还是留了个小尾巴——如何求“特解”？虽然来自实际应用的余数问题通常只涉及三四个余数，特解很容易找到，但数学家解决问题都追求一般性，他们想解决的不仅是包含三四个除数的余数问题，也不是三四十个除数，而是任意多个除数。

1247年南宋的数学家秦九韶把《孙子算经》中“物不知数”一题的方法推广到一般的情况，称为“大衍求一术”，在《数书九章》中发表。这个结论在欧洲要到十八世纪才由数学家高斯和欧拉发现。所以世界公认这个定理是中国人最早发现的，特别称之为“中国剩余定理”。中国剩余定理

中国剩余定理不仅有光辉的历史意义，直到现在还是一个非常重