韩信点兵与中国剩余定理.ppt

1,第五节 韩信点兵与中国剩余定理,2,一、“韩信点兵”的故事和孙子算经中的题目 1.“韩信点兵”的故事 韩信阅兵时，让一队士兵5人一行排队从他面前走过，他记下最后一行士兵的人数（1人）；再让这队士兵6人一行排队从他面前走过，他记下最后一行士兵的人数（5人）；再让这队士兵7人一行排队从他面前走过，他记下最后一行士兵的人数（4人），再让这队士兵11人一行排队从他面前走过，他记下最后一行士兵的人数（10人）。 然后韩信就凭这些数，可以求得这队士兵的总人数。,3,这里面有什么秘密呢？ 韩信好像非常重视作除法时的余数,4,2.孙子算经中的题目 我国古代数学名著孙子算经中有“物不知数”的 题目： 今有物不知其数， 三三数之剩2， 五五数之剩3， 七七数之剩2， 问物几何？,5,这里面又有什么秘密呢？ 题目给出的条件， 也仅仅是作除法时的余数,6,孙子算经,7,二问题的解答 1从另一个问题入手 问题：今有物不知其数，二二数之剩1，三三数之剩2，四四数之剩3，五五数之剩4，六六数之剩5，七七数之剩6，八八数之剩7，九九数之剩8，问物几何？,8,1）筛法 1，3，5，7，9，11，13，15，17，19， 21，23，25， （ 用2除余1） 5， 11， 17， 23， （ 用3除余2） 11， 23， （ 用4除余3）,9,再从中挑“用5除余4”的数， 一直筛选下去，舍得下功夫，就一定可得结果。 并且看起来，解，还不是唯一的；可能有无穷多个解。,10,化繁为简的思想 当问题中有很多类似的条件时，我们先只看其中两三个条件，这就是化繁为简。 一个复杂的问题，如果在简化时仍然保留了原来问题的特点和本质，那么简化就“不失一般性”。 学会“简化问题”与学会“推广问题”一样，是一种重要的数学能力。 寻找规律的思想 把我们的解题方法总结为筛法，是重要的进步，是质的飞跃： 找到规律了。 筛法是一般性方法，还可以用来解决其他类似的问题。,11,2）公倍数法 化繁为简 我们还是先看只有前两个条件的简化题目。 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”的数组成的数列。这个数列实际上是用带余除法的式子得到的。,12,所谓“带余除法”，是指整数的如下 “除法”： 被除数 ，除数 , 必唯一存在商 和余 ，使,13,当余 时，则 ，称为 “ 整除”，或 “ 整除 ”，这是通常除法“ ” 的另一种表达形式。所以，带余 除法是通常除法的推广。,14,回到求“用2除余1的数”的问题。设这 样的数为 ，则 。这里 是 被除数，2是除数， 是商，1是余， 且 。,这就是“带余除 法”的式子。当取 时， 用上式求得的 正好组成上述数列 1，3，5，7，9，11，13，15， 17，19，21，23，25，,16,接着从中筛选出“用3除余2”的 数，就是挑出符合下面“带余除法”表达式 的数，这里 可取0，1，2，3，4， 再继续做下去。,17,如果我们不分上面两步，而是一上来就综合考虑两者，则就是要解联立方程组,18,那么，为了解这个方程组，除了刚才的筛法外，还有没有更加巧妙的解法？ 我们考察上边两个方程的特点，发现，两个“带余除法”的式子，都是“余数比除数少1”。 于是想到，如果把被除数再加1，不是余数就为0了吗？换句话说，不是就出现整除的情况了吗？,19,于是把上边每个方程两边都加上1，成为 这说明， 既是2的倍数，又是3的 倍数，因此，它是2与3的公倍数。由此想到,20,对整个问题寻找规律,问题： 今有物不知其数，二二数之剩1，三三数之剩2，四四数之剩3，五五数之剩4，六六数之剩5，七七数之剩6，八八数之剩7，九九数之剩8，问物几何？,21,寻找规律 设问题中，需要求的数是 ，则 被2，3，4，5，6，7，8，9去除，所得的余数都是比除数少1，于是我们把被除数 再加1， 则 就可被2，3，4，5，6，7，8，9均整除。也就是说， 是2,3,4,5,6,7,8,9的公倍数，从而是其最小公倍数2,3,4,5,6,7,8,9的倍数。,22,即 这就是原问题的全部解，有无穷多个解，其中第一个解是2519；我们只取正数解，因为“物体的 个数”总是正整数。,23,思： 求“用2除余1，3除余2， 用m除余 m 1”的数。 求“用a除余a 1，用b除余b1，用c除余c1”的数。 （a,b,c是任意大于1的自然数） 求“用2，3，4，5，6，7，8，9除 都余1”的数。 求“用5，7，9，11 除都余2”的数。,24,2孙子算经中“有物不知其数” 问题的解答 问题：今有物不知其数， 三三数之剩2， 五五数之剩3， 七七数之剩2， 问物几何？,25,1）筛法. 2，5，8，11，14，17，20，23，26，29，（用3除余2） 8，23， （用5除余3） 23， （用7除余2） 由此得到，23是最小的一个解。 至于下一个解是什么，要把“”写出来才知道； 实践以后发现，是要费一点儿功夫的。,26,2）公倍数法 现在仿照上边用过的“公倍数法”，设要求的数为 ，则依题意，得联立方程组,27,按上一问题中“公倍数法”解决问题的思路：把方程两边同时加上或减去一个什么样的数，就能使三个等式的右边分别是3，5，7的倍数，从而等式左边就是3，5，7的公倍数了。 这要通过反复的试算去完成。,28,一种试算的方法,29,从第三个等式入手，两边加5（或减2）则 得,30,则右边是7的倍数了，但两边加5（或减2）并不能使前两式的右边分别是3的倍数和5的倍数，所以两边加5（或减2）并不能使右边成为3，5，7的公倍数。再继续从第三个等式入手，为使第三个等式右边仍然保持是7的倍数，可再加 （或再减 ），则 （或 ） 将 代入试算、分 析，,31,最后发现，为达到目的 （三个等式的右边分别是3，5，7的倍 数），最小的加数是82（ 时 ）（或最小的减数是23，即 时 ）。,32,用等式两边加82来求解，有 用等式两边减23来求解，有 多了一个“ ” ，因这时 也是正数，合 要求。,33,这两组解是一样的，都是“23，23+105，23+2105，”。 原因是82+23=105，故令 第一组解就成为 便转化成第二组解。,34,但是，这82和23来之不易；并且如果 题目中的余数变了，就得重新试算，所以 这方法缺少一般性，为使它具有一般性， 要做根本的修改。,35,3）单因子构件凑成法 我们先对前几页（*）式作两个方面的简化：一方面是每次只考虑“一个除式”有余数的情况（即另两个除式都是整除的情况）；另一方面是把余数都简化为最简单的1。这样得到三组方程。,36,（1）式意味着，在5和7的公倍数中（35，70，105，）寻找被3除余1的数； （2）式意味着，在3和7的公倍数中（21，42，63，）寻找被5除余1的数； （3）式意味着，在3和5的公倍数中（15，30，45，）寻找被7除余1的数。,37,对（1）式而言，这个数可以取70，对（2）式而言，这个数可以取21，对（3）式而言，这个数可以取15。 于是（1）式两边同减70变为这样：第二式右边仍是5的倍数，第三式右边仍是7的倍数，而第一式右边因为减的70是“用3除余1”的数，正好原来也多一个1，减没了。第一式右边也成为了倍数，是3的倍数。,38,（2）式两边同减21变为,39,（3）式两边同减15变为 于是得到,40,现在重复一下：所得的x是被3除余1，被5和7除余0的数；y是被5除余1，被3和7除余0的数；z是被7除余1，被3和5除余0的数。,41,那么，凑出 ， s 不就是我们需要求的数吗？,42,因为，用3去除s时，除y及除z均余0 除3y及除2z均余0， 又除x余1 除2x余2，用3除s时余2。 用5去除s时，除x及除z均余0 除2x及除2z均余0， 又除y余1 除3y余3，用5除s时余3。 用7去除s时，除x及除y均余0 除2x及除3y均余0， 又除z余1 除2z余2， 用7除s时余2。,43,于是我们要求的数是 这就是孙子算经中“物不知其数” 一题的解，有无穷多解，最小的正整数解是 23（ 时）。,44,这里，（1），（2），（3）三式分别叫三个“单子因构件”，分别解得 每个单因子构件，都是用某一个数去除余1，用另两个数去除均余0的情况。再据题目要求余数分别是2，3，2的情况，凑成,45,所以，上述方法叫“单因子构件凑成法” 解决“由几个平行条件表述的问题”的方法 （ 也称“孙子华方法”） 这种方法的最大优点是，可以任意改变余数，加以推广： 题： 有物不知其数，三三数之剩a，五五数 之剩b，七七数之剩c，问物几何？ 答：解为 （ 的选取应使 ）.,46,4）歌诀 推广了的“物不知其数”问题的解为 明朝数学家程大位在算法统宗中把上式总结为一首通俗易懂的歌决： 三人同行七十稀，五树梅花廿一枝， 七子团圆正半月，除百零五便得知。 其中正半月是指15，这个口诀把3，5，7；70，21，15及105这几个关键的数都总结在内了。详细说，歌诀的含义是：用3除的余数乘70，5除的余数乘21，7除的余数乘15，相加后再减去（“除”当“减”讲）105的适当倍数，就是需要求的（最小）解了。,47,当然，解，不是唯一的，每差105， 都是另一个解答，但如果结合实际问题， 答案往往就是唯一的了。例如一队士兵的 大约人数，韩信应是知道的。,48,三、中国剩余定理 1247年南宋的数学家秦九韶把孙子算经中“物不知其数”一题的方法推广到一般的情况，得到称之为“大衍求一术”的方法，在数书九章中发表。这个结论在欧洲要到十八世纪才由数学家高斯和欧拉发现。所以世界公认这个定理是中国人最早发现的，特别称之为“中国剩余定理”（Chinese remainder theorem）。,49,该定理用现在的语言表达如下： 设 两两互素，设 分别被 除所得的余数为 ，则 可表示为下式 其中 是 的最小公倍数； 是 的公倍数，而且被 除所得 余数为1； 是任意整数。,50,要注意的是，用上述定理时， 必须两两互素。前面的问题中，3，5，7是两 两互素的，所以“三三数，五五数，七七数”得 余数后可用此公式。但“四四数，六六数，九 九数”得余数后就不能用此公式，因为4、6、9 并不是两两互素的。,51,“中国剩余定理”不仅有光辉的历史意义，直到现在还是一个非常重要的定理。1970年，年轻的苏联数学家尤里.马季亚谢维奇（）（28岁）解决了希尔伯特提出的23个问题中的第10个问题，轰动了世界数学界。他在解决这个问题时，用到的知识十分广泛，而在一个关键的地方，就用到了我们的祖先一千多年前发现的这个“中国剩余定理”。,52,希尔伯特的第10个问题： 丢番图方程的可解性 能求出一个整系数方程的整数根，称为丢番图方程可解。希尔伯特问，能否用一种由有限步构成的一般算法判断一个丢番图方程的可解性？1970年，苏联的IO.B.马季亚谢维奇证明了希尔伯特所期望的算法不存在。,希尔伯特,53,四、有趣的应用 某单位有100把锁，分别编号为1，2，3，100。现在要对钥匙编号，使外单位的人看不懂，而本单位的人一看见锁的号码就知道该用哪一把钥匙。,54,能采用的方法很多，其中一种就是利用中国剩余定理，把锁的号码被3，5，7去除所得的三个余数来作钥匙的号码（首位余数是0时，也不能省略）。 这样每把钥匙都有一个三位数编号。 例如23号锁的钥匙编号是232号，52号锁的钥匙编号是123号。,55,8号锁231 19号锁145 45号锁003 52号锁123 因为只有100把锁，不超过105，所以锁的号与钥匙的号是一一对应的。 如果希望保密性再强一点儿，则可以把刚才所说的钥匙编号加上一个固定的常数作为新的钥匙编号系统。甚至可以每过一个月更换一次这个常数。这样，仍不破坏锁的号与钥匙的号之间的一一对应，而外人则更难知道了。,56,趣题找次品：,1）有5个外形相同的乒乓球，其中只有 1个重量不标准的次品乒乓球。 现再给你一个标准球；请用一架不带砝码的天平，最多两次使用该天平，找出上述次品乒乓球。,57,最优化思想,最少次数完成预定任务 最大限度发挥该天平的作用,58,思考题,59,趣题找次品：,2）有12个外形相同的乒乓球，其中只有 1个重量不标准的次品乒乓球。请用一架不带砝码的天平，最多三次使用该天平，找出上述次品乒乓球，并判断它是重于标准球，还是轻于标准球。,60,本节结束 谢谢！,61,62,思考题解答,63,思： 求“用2除余1，用3除2， 用m除余m 1”的数。 答：,64, 求“用a除余a 1，用b除余b 1，用c除余c1”的数（a,b,c是任意 大于1的自然数） 答：,65, 求“用2，3，4，5，6，7，8，9除都余1”的数。 答：,66, 求“用5，7，9，11 除都余2”数。 答：,67,68,69,2）筛法 先只看前两个条件 用2除余1，用3除余2，求这样的数，一种普