模块重点学习内容韩信点兵与中国剩余定理

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第三模块重点学习内容,韩信点兵与中国剩余定理,1,韩信是中国古代一位有名的大元帅。他少年时就父母双亡，生活困难，曾靠乞讨为生，还经常受到某些泼皮的欺凌，胯下之辱讲的就是韩信少年时被泼皮强迫从胯下钻过的事。,后来他投奔刘邦，展现了他杰出的军事才能，为刘邦打败了楚霸王项羽立下汗马功劳，开创了刘汉皇朝四百年的基业。,民间流传着一些以韩信为主角的有关聪明人的故事，韩信点兵的故事就是其中的一个。,一、“韩信点兵”的故事与孙子算经中的题目,2,相传有一次，韩信将1500名将士与楚王大将李锋交战。双方大战一场，楚军不敌，败退回营。而汉军也有伤亡，只是一时还不知伤亡多少。于是，韩信整顿兵马也返回大本营，准备清点人数。当行至一山坡时，忽有后军来报，说有楚军骑兵追来。韩信驰上高坡观看，只见远方尘土飞扬，杀声震天。汉军本来已经十分疲惫了，这时不由得人心大乱。韩信仔细地观看敌方，发现来敌不足五百骑，便急速点兵迎敌。不一会儿，值日副官报告，共有1035人。他还不放心，决定自己亲自算一下。,1.“韩信点兵”的故事,3,韩信阅兵时，让一队士兵5人一行排队从他面前走过，他记下最后一行士兵的人数（1人）；再让这队士兵6人一行排队从他面前走过，他记下最后一行士兵的人数（5人）；再让这队士兵7人一行排队从他面前走过，他记下最后一行士兵的人数（4人），再让这队士兵11人一行排队从他面前走过，他记下最后一行士兵的人数（10人）。然后韩信就凭这些数，可以求得这队士兵的总人数。,思考题：,这里面有什么秘密呢？韩信好像非常重视作除法时的,余数,。,“数的除法运算以及余数”,是小学数学的内容。现在，每个学生都具有这样的基础，但能否会运用就有差别了，你能够分析它吗？,4,约成书于四、五世纪，作者生平和编写年代都不清楚。现在传本的孙子算经共三卷。卷上叙述,算筹,记数的纵横相间制度和筹算乘除法则，卷中举例说明筹算分数算法和筹算开平方法。卷下第31题，可谓是后世“,鸡兔同笼,”题的始祖，后来传到,日本,，变成“鹤龟算”。,2.孙子算经,书中是这样叙述的：“今有鸡兔同笼，上有三十五头，下有九十四足，问鸡兔各几何？这四句话的意思是：有若干只鸡兔同在一个笼子里，从上面数，有35个头；从下面数，有94只脚。求笼中各有几只鸡和兔？,孙子算经,5,我国古代数学名著孙子算经中有“物不知数”的题目：,今有物不知其数，,三三数之剩2，,五五数之剩3，,七七数之剩2，,问物几何？,孙子算经中的题目,这里面又有什么秘密呢？题目给出的条件，也仅仅是作除法时的,余数。,6,问题：,今有物不知其数，二二数之剩1，三三数之剩2，四四数之剩3，五五数之剩4，六六数之剩5，七七数之剩6，八八数之剩7，九九数之剩8，问物几何？,二、问题的解答,1先,从另一个问题入手,思考：,此问题是否比原问题简单些吗？,7,再从中挑“,用5除余4,”的数，,一直筛选下去，舍得下功夫，就一定可得结果。并且看起来，解，还不是唯一的；可能有无穷多个解。,1,3,5,7,9,11,13,15,17,19,21,23,（用2除余1）,5,11,17,23,（用3除余2）,11,23,（用4除余3）,1）筛法,思考一下：解题的思路是什么？,8,当问题中有很多类似的条件时，我们先只看其中两三个条件，这就是,化繁为简,。,一个复杂的问题，如果在简化时仍然,保留了原来问题的特点和本质,，那么简化就,“不失一般性”,。,学会“简化问题”与学会“推广问题”一样，是一种重要的数学能力。,化繁为简的思想,寻找规律的思想,把我们的解题方法总结为,筛法,，是重要的进步，是质的飞跃找到规律了。,筛法是一般性方法，还可以用来解决其他类似的问题。,9,化繁为简,我们还是先看只有前两个条件的简化题目。,1,3,5,7,9,11,13,15,17,19,21,23,25,（用2除余1）,5,11,17,23,（用3除余2）,上述筛选过程的第一步，得到:,1,3,5,7,9,11,13,15,17,19,21,23,25,其实是列出了“,用2除余1,”的数组成的数列。这个数列实际上是用,带余除法,的式子得到的。,2)公倍数法,10,对任意给定被除数,a,，不为零的除数,b,，必唯一存在商,q,和余数,r,，使,所谓“,带余除法,”，是指,整数,的如下“,除法,”：,当余数,r,=0时，则,a=bq,，称为“,a,被,b,整除”，或“,b,整除,a,”，这是通常除法“”的另一种表达形式。所以，带余除法是通常除法的推广。,11,就是“带余除法”的式子.,当取 时，用上式求得的,x,正好组成上述数列,1,3,5,7,9,11,13,15,17,19,21,23,25,设这样的数为,x,，则 。这里,x,是被除数，2是除数，是商，1是余数，且 。,回到求“用2除余1的数”的问题。,12,接着从中筛选出“用3除余2”的数，就是挑出符合下面“带余除法”表达式,的数，这里 可取0，1，2，3，4，,再继续做下去.,如果我们不分上面两步，而是一上来就,综合,考虑,两者,，则就是要解联立方程组,13,那么，为了解这个方程组，除了刚才的筛法外，还有没有更加巧妙的解法？,我们考察上边两个方程的特点，发现，两个“带余除法”的式子，都是“,余数比除数少1,”。,于是想到，如果,把被除数再加1,，不是余数就为0了吗？换句话说，不是就出现,整除,的情况了吗？,于是把上边每个方程两边都加上1，成为,14,这说明，,x+,1既是2的倍数，又是3的倍数，因此，它是2与3的公倍数。由此想到,对整个问题寻找规律。,再看问题：,今有物不知其数，二二数之剩1，三三数之剩2，四四数之剩3，五五数之剩4，六六数之剩5，七七数之剩6，八八数之剩7，九九数之剩8，问物几何？,对整个问题寻找规律,15,寻找规律,设问题中,需要求的数是,x,则被2,3,4,5,6,7,8,9去除，所得的余数都是比除数少1，于是我们把被除数,x,再加1,则,x,+1就可被2,3,4,5,6,7,8,9均整除.也就是说，,x+,1,是2,3,4,5,6,7,8,9的公倍数，从而是其最小公倍数2,3,4,5,6,7,8,9的倍数。,即,这就是原问题的全部解，有无穷多个解，其中第一个解是2519；我们只取正数解，因为“物体的个数”总是正整数。,16,思考题,：,求“用2除余1,3除余2,用,m,除余,m,-1”的数。,求“用,a,除余,a,-1,用,b,除余,b,-1,用,c,除余,c,-1”的数.（,a,b,c,是任意大于1的自然数）,求“用2,3,4,5,6,7,8,9除都余1”的数。,求“用5,7,11 除都余2”的数。,17,2.孙子算经中“有物不知其数”问题的解答,问题：,今有物不知其数，,三三数之剩2，,五五数之剩3，,七七数之剩2，,问物几何？,18,1）筛法:,2,5，8，11，14，17，20，,23,，26，29，,（用3除余2）,8，,23,，,（用5除余3）,23,，,（用7除余2）,由此得到，,23,是最小的一个解。,至于下一个解是什么，要把“”写出来才知道；,实践以后发现，是要费一点儿功夫的。,19,2）公倍数法,现在仿照上边用过的“公倍数法”，设要求的数为,x,，则依题意，得联立方程组,按上一问题中“公倍数法”解决问题的思路：把,方程两边同时加上或减去,一个什么样的数，就能使三个等式的右边分别是3，5，7的倍数，从而等式左边就是3，5，7的公倍数了。,20,一种试算的方法,从第三个等式入手，两边加5,（或减2）,则得,这要通过,反复,的试算去完成。,21,则右边是7的倍数了，但两边加5,（或减2）,并不能使前两式的右边分别是3的倍数和5的倍数，所以两边加5,（或减2）,并不能使右边成为3，5，7的公倍数。再继续从第三个等式入手，为使第三个等式右边仍然保持是7的倍数，可再加7l,（或再减7l），,（或 ）,最后发现，为达到目的（三个等式的右边分别是3,5,7的倍数）,最小的加数是82(,l,=11时,5+7,l,=82）,（或最小的减数是23，即,h,=3,2+7,h,=23）,。,将,代入试算、分析，,22,多了一个“”，因这时,x,也是正数，合要求。,用等式两边加82来求解，有,用等式两边减23来求解，有,23,这两组解是一样的，都是,“23，23+105，23+2105，”。,原因是82+23=105，故令 第一组解就成为,便转化成第二组解。,但是，这82和23来之不易；并且如果,题目中的余数,变了，就得重新试算，所以这方法缺少一般性，为使它具有一般性，要做根本的修改。,24,3）单因子构件凑成法,我们先对前几页（*）式作两个方面的简化:,一方面,是每次只考虑“一个除式”有余数的情况(即另两个除式都是整除的情况):,另一方面,是把余数都简化为最简单的1。这样得到三组方程。,25,（1）式意味着,在5和7的公倍数中（35,70,105,）寻找被3除余1的数；,（2）式意味着,在3和7的公倍数中（21,42,63,）寻找被5除余1的数；,（3）式意味着,在3和5的公倍数中（15,30,45，）寻找被7除余1的数。,对（1）式而言，这个数可以取70，对（2）式而言，这个数可以取21，对（3）式而言，这个数可以取15。,26,于是（1）式两边同减70变为这样：,第二式右边仍是5的倍数，第三式右边仍是7的倍数，而第一式右边因为减的70是“用3除余1”的数，正好原来也多一个1，减没了。第一式右边也成为了倍数，是3的倍数。,27,（2）式两边同减21变为,（3）式两边同减15变为,28,现在重复一下：所得的,x,是,被3除余1，被5和7除余0的数；,y,是,被5除余1，被3和7除余0的数；,z,是,被7除余1，被3和5除余0的数。,于是得到,那么，凑出,s=2x+3y+2z,s,不就是我们需要求的数吗？,29,因为用3去除,s,时，除,y,及除,z,均余0,除3,y,及除2,z,均余0，,又除,x,余1,除2,x,余2，用3除,s,时余2。,用5去除,s,时，除,x,及除,z,均余0,除2,x,及除2,z,均余0，,又除,y,余1 除3,y,余3，用5除,s,时余3。,用7去除,s,时，除,x,及除,y,均余0,除2,x,及除3,y,均余0，,又除z余1 除2z余2，用7除s时余2。,30,于是我们要求的数是,这就是孙子算经中“物不知其数”一题的解，有无穷多解，最小的正整数解是23（,k,=-2时）。,31,这里,(1),(2),(3)三式分别叫三个“单子因构件”,分别解得,每个单因子构件,都是用某一个数去除余1,用另两个数去除均余0的情况。再据题目要求余数分别是2,3,2的情况,凑成,再看由（*）式得到的下面三个式子：,32,所以，上述方法叫“,单因子构件凑成法,”,解决“由几个平行条件表述的问题”的方法,（也称“,孙子华方法,”）,这种方法的最大优点是，可以,任意改变余数,，加以,推广,：,问题：,有物不知其数，三三数之剩,a,，,五五数之剩,b,，七七数之剩,c,，问物几何？,答：,解为,（的选取应使 ）.,33,推广了的“物不知其数”问题的解为,明朝数学家程大位在算法统宗中把上式总结为一首通俗易懂的歌决：,三人同行七十稀，五树梅花廿一枝，,七子团圆正半月，除百零五便得知。,其中正半月是指15,这个口诀把3,5,7;70,21,15及105这几个关键的数都总结在内了。详细说,歌诀的含义是:用3除的余数乘70,5除的余数乘21,7除的余数乘15,相加后再减去（“除”当“减”讲）105的适当倍数,就是需要求的（最小）解了。,4）歌诀,34,当然，解，不是唯一的，每差105，都是另一个解答，但如果结合实际问题，答案往往就是唯一的了。例如一队士兵的大约人数，韩信应是知道的。,35,三、中国剩余定理,1247年南宋的数学家秦九韶把孙子算经中“物不知其数”一题的方法推广到一般的情况，得到称之为“大衍求一术”的方法，在数书九章中发表。