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

《三模块重点学习内容韩信点兵与中国剩余定理.ppt》由会员分享，可在线阅读，更多相关《三模块重点学习内容韩信点兵与中国剩余定理.ppt（44页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、三模块重点学习内容韩信点兵与中国剩余定理 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望u韩信是中国古代一位有名的大元帅。他少年时韩信是中国古代一位有名的大元帅。他少年时就父母双亡，生活困难，曾靠乞讨为生，还经就父母双亡，生活困难，曾靠乞讨为生，还经常受到某些泼皮的欺凌，胯下之辱讲的就是韩常受到某些泼皮的欺凌，胯下之辱讲的就是韩信少年时被泼皮强迫从胯下钻过的事。信少年时被泼皮强迫从胯下钻过的事。u后来他投奔刘邦，展现了他杰出的军事才能，后来他投奔刘邦，展现了他杰出

2、的军事才能，为刘邦打败了楚霸王项羽立下汗马功劳，开创为刘邦打败了楚霸王项羽立下汗马功劳，开创了刘汉皇朝四百年的基业。了刘汉皇朝四百年的基业。u民间流传着一些以韩信为主角的有关聪明人的民间流传着一些以韩信为主角的有关聪明人的故事，韩信点兵的故事就是其中的一个。故事，韩信点兵的故事就是其中的一个。一、一、“韩信点兵韩信点兵”的故事与孙子算经中的题目的故事与孙子算经中的题目2 相传有一次，韩信将相传有一次，韩信将15001500名将士与楚王大将李锋交战。名将士与楚王大将李锋交战。双方大战一场，楚军不敌，败退回营。而汉军也有伤亡，双方大战一场，楚军不敌，败退回营。而汉军也有伤亡，只是一时还不知伤亡多少

3、。于是，韩信整顿兵马也返回大只是一时还不知伤亡多少。于是，韩信整顿兵马也返回大本营，准备清点人数。当行至一山坡时，忽有后军来报，本营，准备清点人数。当行至一山坡时，忽有后军来报，说有楚军骑兵追来。韩信驰上高坡观看，只见远方尘土飞说有楚军骑兵追来。韩信驰上高坡观看，只见远方尘土飞扬，杀声震天。汉军本来已经十分疲惫了，这时不由得人扬，杀声震天。汉军本来已经十分疲惫了，这时不由得人心大乱。韩信仔细地观看敌方，发现来敌不足五百骑，便心大乱。韩信仔细地观看敌方，发现来敌不足五百骑，便急速点兵迎敌。不一会儿，值日副官报告，共有急速点兵迎敌。不一会儿，值日副官报告，共有10351035人。人。他还不放心，决

4、定自己亲自算一下。他还不放心，决定自己亲自算一下。1.“韩信点兵韩信点兵”的故事的故事3 韩信阅兵时，让一队士兵韩信阅兵时，让一队士兵5 5人一行排队从他面前走过，人一行排队从他面前走过，他记下最后一行士兵的人数（他记下最后一行士兵的人数（1 1人）；再让这队士兵人）；再让这队士兵6 6人一人一行排队从他面前走过，他记下最后一行士兵的人数（行排队从他面前走过，他记下最后一行士兵的人数（5 5人）；人）；再让这队士兵再让这队士兵7 7人一行排队从他面前走过，他记下最后一行人一行排队从他面前走过，他记下最后一行士兵的人数（士兵的人数（4 4人），再让这队士兵人），再让这队士兵1111人一行排队从他

5、面前人一行排队从他面前走过，他记下最后一行士兵的人数（走过，他记下最后一行士兵的人数（1010人）。然后韩信就人）。然后韩信就凭这些数，可以求得这队士兵的总人数。凭这些数，可以求得这队士兵的总人数。思考题：思考题：这里面有什么秘密呢？韩信好像非常重视作这里面有什么秘密呢？韩信好像非常重视作除法时的除法时的余数余数。“数的除法运算以及余数数的除法运算以及余数”是小学数学的是小学数学的内容。现在，每个学生都具有这样的基础，但能否会运用内容。现在，每个学生都具有这样的基础，但能否会运用就有差别了，你能够分析它吗？就有差别了，你能够分析它吗？4 约成书于四、五世纪，作者生平和编写年代都不清楚。约成书于

6、四、五世纪，作者生平和编写年代都不清楚。现在传本的孙子算经共三卷。卷上叙述现在传本的孙子算经共三卷。卷上叙述算筹算筹记数的纵记数的纵横相间制度和筹算乘除法则，卷中举例说明筹算分数算法横相间制度和筹算乘除法则，卷中举例说明筹算分数算法和筹算开平方法。卷下第和筹算开平方法。卷下第3131题，可谓是后世题，可谓是后世“鸡兔同笼鸡兔同笼”题的始祖，后来传到题的始祖，后来传到日本日本，变成，变成“鹤龟算鹤龟算”。2.2.孙子算经孙子算经 书中是这样叙述的：书中是这样叙述的：“今有鸡兔今有鸡兔同笼，上有三十五头，下有九十四足，同笼，上有三十五头，下有九十四足，问鸡兔各几何？这四句话的意思是：问鸡兔各几何？

7、这四句话的意思是：有若干只鸡兔同在一个笼子里，从上有若干只鸡兔同在一个笼子里，从上面数，有面数，有3535个头；从下面数，有个头；从下面数，有9494只只脚。求笼中各有几只鸡和兔？脚。求笼中各有几只鸡和兔？孙子算经孙子算经5 我国古代数学名著孙子算经中有我国古代数学名著孙子算经中有“物不知数物不知数”的的题目：题目：今有物不知其数，今有物不知其数，三三数之剩三三数之剩2 2，五五数之剩五五数之剩3 3，七七数之剩七七数之剩2 2，问物几何？问物几何？孙子算经中的题目孙子算经中的题目 这里面又有什么秘密呢？题目给出的条件，也仅仅是这里面又有什么秘密呢？题目给出的条件，也仅仅是作除法时的作除法时的

8、余数。余数。6 问题：问题：今有物不知其数，二二数之剩今有物不知其数，二二数之剩1 1，三三数之剩，三三数之剩2 2，四，四四数之剩四数之剩3 3，五五数之剩，五五数之剩4 4，六六数之剩，六六数之剩5 5，七七数之剩，七七数之剩6 6，八八数之剩，八八数之剩7 7，九九数之剩，九九数之剩8 8，问物几何？，问物几何？二、问题的解答二、问题的解答1 1先从另一个问题入手先从另一个问题入手思考：思考：此问题是否比原问题简单些吗？此问题是否比原问题简单些吗？7 再从中挑再从中挑“用用5 5除余除余4 4”的数，的数，一直筛选下去，舍得下功夫，就一定可得结果。并且一直筛选下去，舍得下功夫，就一定可得

9、结果。并且看起来，解，还不是唯一的；可能有无穷多个解。看起来，解，还不是唯一的；可能有无穷多个解。1,3,5,7,9,11,13,15,17,19,21,23,1,3,5,7,9,11,13,15,17,19,21,23,（用（用2 2除余除余1 1）5,11,17,23,5,11,17,23,（用（用3 3除余除余2 2）11,23,11,23,（用（用4 4除余除余3 3）1 1）筛法）筛法思考一下：解题的思路是什么？思考一下：解题的思路是什么？8 当问题中有很多类似的条件时，我们先只看其中两三当问题中有很多类似的条件时，我们先只看其中两三个条件，这就是个条件，这就是化繁为简化繁为简。一个

10、复杂的问题，如果在简化时仍然一个复杂的问题，如果在简化时仍然保留了原来问题保留了原来问题的特点和本质的特点和本质，那么简化就，那么简化就“不失一般性不失一般性”。学会学会“简化问题简化问题”与学会与学会“推广问题推广问题”一样，是一种一样，是一种重要的数学能力。重要的数学能力。化繁为简的思想化繁为简的思想寻找规律的思想寻找规律的思想 把我们的解题方法总结为把我们的解题方法总结为筛法筛法，是重要的进步，是质，是重要的进步，是质的飞跃的飞跃找到规律了。找到规律了。筛法是一般性方法，还可以用来解决其他类似的问题。筛法是一般性方法，还可以用来解决其他类似的问题。9 化繁为简化繁为简 我们还是先看只有前

11、两个条件的简化题目。我们还是先看只有前两个条件的简化题目。1,3,5,7,9,11,13,15,17,19,21,23,25,1,3,5,7,9,11,13,15,17,19,21,23,25,（用（用2 2除余除余1 1）5,11,17,23,5,11,17,23,（用（用3 3除余除余2 2）上述筛选过程的第一步，得到上述筛选过程的第一步，得到:1,3,5,7,9,11,13,15,17,19,21,23,25,1,3,5,7,9,11,13,15,17,19,21,23,25,其实是列出了其实是列出了“用用2 2除余除余1 1”的数组成的数列。这个数的数组成的数列。这个数列实际上是用列实

12、际上是用带余除法带余除法的式子得到的。的式子得到的。2)2)公倍数法公倍数法10 对任意给定被除数对任意给定被除数a，不为零的除数，不为零的除数b，必唯一存在商，必唯一存在商q和余数和余数r，使，使所谓所谓“带余除法带余除法”，是指，是指整数整数的如下的如下“除法除法”：当余数当余数r=0=0时，则时，则 a=bq，称为，称为“a被被b整除整除”，或，或“b整除整除a”，这是通常除法，这是通常除法“”“”的另一种表达形式。的另一种表达形式。所以，带余除法是通常除法的推广。所以，带余除法是通常除法的推广。11 就是就是“带余除法带余除法”的式子的式子.当取当取 时，用上式求得的时，用上式求得的x

13、正好正好组成上述数列组成上述数列 1,3,5,7,9,11,13,15,17,19,21,23,25,1,3,5,7,9,11,13,15,17,19,21,23,25,设这样的数为设这样的数为x，则，则 。这里。这里x是被除是被除数，数，2 2是除数，是除数，是商，是商，1 1是余数，且是余数，且 。回到求回到求“用用2 2除余除余1 1的数的数”的问题。的问题。12 接着从中筛选出接着从中筛选出“用用3 3除余除余2”2”的数，就是挑出符合下的数，就是挑出符合下面面“带余除法带余除法”表达式表达式的数，这里的数，这里 可取可取0 0，1 1，2 2，3 3，4 4，再继续做下去再继续做下去

14、.如果我们不分上面两步，而是一上来就如果我们不分上面两步，而是一上来就综合综合考虑考虑两者两者，则就是要解联立方程组则就是要解联立方程组13 那么，为了解这个方程组，除了刚才的筛法外，还有那么，为了解这个方程组，除了刚才的筛法外，还有没有更加巧妙的解法？没有更加巧妙的解法？我们考察上边两个方程的特点，发现，两个我们考察上边两个方程的特点，发现，两个“带余除法带余除法”的式子，都是的式子，都是“余数比除数少余数比除数少1 1”。于是想到，如果于是想到，如果把被除数再加把被除数再加1 1，不是余数就为，不是余数就为0 0了吗？了吗？换句话说，不是就出现换句话说，不是就出现整除整除的情况了吗？的情况

15、了吗？于是把上边每个方程两边都加上于是把上边每个方程两边都加上1 1，成为，成为14 这说明，这说明，x+1 1既是既是2 2的倍数，又是的倍数，又是3 3的倍数，因此，它的倍数，因此，它是是2 2与与3 3的公倍数。由此想到的公倍数。由此想到对整个问题寻找规律。对整个问题寻找规律。再看问题：再看问题：今有物不知其数，二二数之剩今有物不知其数，二二数之剩1 1，三三数之剩，三三数之剩2 2，四四，四四数之剩数之剩3 3，五五数之剩，五五数之剩4 4，六六数之剩，六六数之剩5 5，七七数之剩，七七数之剩6 6，八八数之剩八八数之剩7 7，九九数之剩，九九数之剩8 8，问物几何？，问物几何？对整个

16、问题寻找规律对整个问题寻找规律15 寻找规律寻找规律 设问题中设问题中,需要求的数是需要求的数是x,则被则被2,3,4,5,6,7,8,92,3,4,5,6,7,8,9去除，去除，所得的余数都是比除数少所得的余数都是比除数少1 1，于是我们把被除数，于是我们把被除数x再加再加1,1,则则x+1+1就可被就可被2,3,4,5,6,7,8,92,3,4,5,6,7,8,9均整除均整除.也就是说，也就是说，x+1是是2,3,4,5,6,7,8,92,3,4,5,6,7,8,9的公倍数，从而是其最小公倍数的公倍数，从而是其最小公倍数2,3,4,5,6,7,8,92,3,4,5,6,7,8,9的倍数。的

17、倍数。即即 这就是原问题的全部解，有无穷多个解，其中第一个解这就是原问题的全部解，有无穷多个解，其中第一个解是是25192519；我们只取正数解，因为；我们只取正数解，因为“物体的个数物体的个数”总是正整数。总是正整数。16 思考题思考题：求求“用用2 2除余除余1,31,3除余除余2,2,用用m除余除余m-1”-1”的数。的数。求求“用用a除余除余a-1,-1,用用b除余除余b-1,-1,用用c除余除余c-1”-1”的数的数.（a,b,c是任意大于是任意大于1 1的自然数）的自然数）求求“用用2,3,4,5,6,7,8,92,3,4,5,6,7,8,9除都余除都余1”1”的数。的数。求求“用

18、用5,7,11 5,7,11 除都余除都余2”2”的数。的数。17 2.2.孙子算经中孙子算经中“有物不知其数有物不知其数”问题的解问题的解答答问题：问题：今有物不知其数，今有物不知其数，三三数之剩三三数之剩2 2，五五数之剩五五数之剩3 3，七七数之剩七七数之剩2 2，问物几何？问物几何？181）筛法）筛法:2,52,5，8 8，1111，1414，1717，2020，2323，2626，2929，（用（用3 3除余除余2 2）8 8，2323，（用（用5 5除余除余3 3）2323，（用（用7 7除余除余2 2）由此得到，由此得到，2323是最小的一个解。是最小的一个解。至于下一个解是什么

19、，要把至于下一个解是什么，要把“”“”写出来才知道；写出来才知道；实践以后发现，是要费一点儿功夫的。实践以后发现，是要费一点儿功夫的。19 2 2）公倍数法）公倍数法 现在仿照上边用过的现在仿照上边用过的“公倍数法公倍数法”，设要求的数为，设要求的数为x ，则依题意，得联立方程组，则依题意，得联立方程组 按上一问题中按上一问题中“公倍数法公倍数法”解决问题的思路：把解决问题的思路：把方程方程两边同时加上或减去两边同时加上或减去一个什么样的数，就能使三个等式的一个什么样的数，就能使三个等式的右边分别是右边分别是3 3，5 5，7 7的倍数，从而等式左边就是的倍数，从而等式左边就是3 3，5 5，

20、7 7的的公倍数了。公倍数了。20 一种试算的方法一种试算的方法从第三个等式入手，两边加从第三个等式入手，两边加5 5（或减（或减2 2）则得则得这要通过这要通过反复反复的试算去完成。的试算去完成。21则右边是则右边是7 7的倍数了，但两边加的倍数了，但两边加5 5（或减（或减2 2）并不能使前两式并不能使前两式的右边分别是的右边分别是3 3的倍数和的倍数和5 5的倍数，所以两边加的倍数，所以两边加5 5（或减（或减2 2）并不能使右边成为并不能使右边成为3 3，5 5，7 7的公倍数。再继续从第三个等式的公倍数。再继续从第三个等式入手，为使第三个等式右边仍然保持是入手，为使第三个等式右边仍然

21、保持是7 7的倍数，可再加的倍数，可再加7l7l（或再减（或再减7l7l），），（或（或 ）最后发现，为达到目的（三个等式的右边分别是最后发现，为达到目的（三个等式的右边分别是3,5,73,5,7的倍数）的倍数）,最小的加数是最小的加数是82(82(l=11=11时时,5+7,5+7l=82=82）（或（或最小的减数是最小的减数是2323，即，即h=3,2+7=3,2+7h=23=23）。将将 代入试算、分析，代入试算、分析，22 多了一个多了一个“”“”，因这时，因这时x也是正数，合要求。也是正数，合要求。用等式两边加用等式两边加8282来求解，有来求解，有用等式两边减用等式两边减2323来

22、求解，有来求解，有23 这两组解是一样的，都是这两组解是一样的，都是 “23 “23，23+10523+105，23+210523+2105，”。原因是原因是82+23=10582+23=105，故令，故令 第一组解就成为第一组解就成为 便转化成第二组解。便转化成第二组解。但是，这但是，这8282和和2323来之不易；并且如果来之不易；并且如果题目中的余数题目中的余数变变了，就得重新试算，所以这方法缺少一般性，为使它具有了，就得重新试算，所以这方法缺少一般性，为使它具有一般性，要做根本的修改。一般性，要做根本的修改。24 3）单因子构件凑成法）单因子构件凑成法 我们先对前几页（我们先对前几页（

23、*）式作两个方面的简化）式作两个方面的简化:一方面一方面是每是每次只考虑次只考虑“一个除式一个除式”有余数的情况有余数的情况(即另两个除式都是整即另两个除式都是整除的情况除的情况):):另一方面另一方面是把余数都简化为最简单的是把余数都简化为最简单的1 1。这样得。这样得到三组方程。到三组方程。25 （1 1）式意味着）式意味着,在在5 5和和7 7的公倍数中（的公倍数中（35,70,105,35,70,105,）寻找被寻找被3 3除余除余1 1的数；的数；（2 2）式意味着）式意味着,在在3 3和和7 7的公倍数中（的公倍数中（21,42,63,21,42,63,）寻）寻找被找被5 5除余除

24、余1 1的数；的数；（3 3）式意味着）式意味着,在在3 3和和5 5的公倍数中（的公倍数中（15,30,4515,30,45，）寻找被寻找被7 7除余除余1 1的数。的数。对（对（1 1）式而言，这个数可以取）式而言，这个数可以取7070，对（，对（2 2）式而言，）式而言，这个数可以取这个数可以取2121，对（，对（3 3）式而言，这个数可以取）式而言，这个数可以取1515。26 于是（于是（1 1）式两边同减）式两边同减7070变为这样：变为这样：第二式右边仍是第二式右边仍是5 5的倍数，第三式右边仍是的倍数，第三式右边仍是7 7的倍数，而第一式右边因为减的倍数，而第一式右边因为减的的7

25、070是是“用用3 3除余除余1”1”的数，正好原来也多一个的数，正好原来也多一个1 1，减没了。，减没了。第一式右边也成为了倍数，是第一式右边也成为了倍数，是3 3的倍数。的倍数。27（2 2）式两边同减）式两边同减2121变为变为（3 3）式两边同减）式两边同减1515变为变为28 现在重复一下：所得的现在重复一下：所得的x是是被被3 3除余除余1 1，被，被5 5和和7 7除余除余0 0的的数；数；y是是被被5 5除余除余1 1，被，被3 3和和7 7除余除余0 0的数；的数；z是是被被7 7除余除余1 1，被，被3 3和和5 5除余除余0 0的数。的数。于是得到于是得到 那么，凑出那么

26、，凑出s=2x+3y+2z,s不就是我们需要求的数吗？不就是我们需要求的数吗？29 因为用因为用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。30 于是我们要求的数是于是我们要求的数是 这就是孙子算经中这就是孙子算经中“物不

27、知其数物不知其数”一题的解，有一题的解，有无穷多解，最小的正整数解是无穷多解，最小的正整数解是2323（k=-2=-2时）。时）。31 这里这里,(1),(2),(3),(1),(2),(3)三式分别叫三个三式分别叫三个“单子因构件单子因构件”,”,分分别解得别解得每个单因子构件每个单因子构件,都是用某一个数去除余都是用某一个数去除余1,1,用另两个数去除用另两个数去除均余均余0 0的情况。再据题目要求余数分别是的情况。再据题目要求余数分别是2,3,22,3,2的情况的情况,凑成凑成再看由（再看由（*）式得到的下面三个式子：）式得到的下面三个式子：32 所以，上述方法叫所以，上述方法叫“单因子

28、构件凑成法单因子构件凑成法”解决解决“由几个平行条件表述的问题由几个平行条件表述的问题”的方法的方法 （也称也称“孙子孙子华方法华方法”）这种方法的最大优点是，可以这种方法的最大优点是，可以任意改变余数任意改变余数，加以，加以推广推广：问题：问题：有物不知其数，三三数之剩有物不知其数，三三数之剩a，五五数之剩五五数之剩b，七七数之剩，七七数之剩c，问物几何？，问物几何？答：答：解为解为 （的选取应使的选取应使 ）.33 推广了的推广了的“物不知其数物不知其数”问题的解为问题的解为 明朝数学家程大位在算法统宗中把上式总结为一明朝数学家程大位在算法统宗中把上式总结为一首通俗易懂的歌决：首通俗易懂的

29、歌决：三人同行七十稀，五树梅花廿一枝，三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。七子团圆正半月，除百零五便得知。其中正半月是指其中正半月是指15,15,这个口诀把这个口诀把3,5,7;70,21,153,5,7;70,21,15及及105105这几这几个关键的数都总结在内了。详细说个关键的数都总结在内了。详细说,歌诀的含义是歌诀的含义是:用用3 3除除的余数乘的余数乘70,570,5除的余数乘除的余数乘21,721,7除的余数乘除的余数乘15,15,相加后再减相加后再减去（去（“除除”当当“减减”讲）讲）105105的适当倍数的适当倍数,就是需要求的就是需要求的（最小）解

30、了。（最小）解了。4）歌诀）歌诀34 当然，解，不是唯一的，每差当然，解，不是唯一的，每差105105，都是另一个解答，都是另一个解答，但如果结合实际问题，答案往往就是唯一的了。例如一队但如果结合实际问题，答案往往就是唯一的了。例如一队士兵的大约人数，韩信应是知道的。士兵的大约人数，韩信应是知道的。35 三、中国剩余定理三、中国剩余定理 12471247年南宋的数学家秦九韶把孙子算经中年南宋的数学家秦九韶把孙子算经中“物不知物不知其数其数”一题的方法推广到一般的情况，得到称之为一题的方法推广到一般的情况，得到称之为“大衍求大衍求一术一术”的方法，在数书九章中发表。这个结论在欧洲要的方法，在数书

31、九章中发表。这个结论在欧洲要到十八世纪才由数学家高斯和欧拉发现。所以世界公认这个到十八世纪才由数学家高斯和欧拉发现。所以世界公认这个定理是中国人最早发现的，特别称之为定理是中国人最早发现的，特别称之为“中国剩余定理中国剩余定理”（Chinese remainder theoremChinese remainder theorem）。）。该定理用现在的语言表达如下该定理用现在的语言表达如下：36 设设 两两互素，设两两互素，设x分别被分别被 除所得的余数为除所得的余数为 ，则，则x可表示为下式可表示为下式 其中其中D是是 的最小公倍数；的最小公倍数；是是 的公倍数，而且被的公倍数，而且被 除所得

32、余数除所得余数为为1;1;k是任意整数。是任意整数。要注意的是要注意的是,用上述定理时，用上述定理时，必须两两互必须两两互素素.前面的问题中前面的问题中,3,5,7,3,5,7是两两互素的是两两互素的,所以所以“三三数三三数,五五五五数数,七七数七七数”得余数后可用此公式。但得余数后可用此公式。但“四四数四四数,六六数六六数,九九九数九数”得余数后就不能用此公式得余数后就不能用此公式,因为因为4,6,94,6,9并不是两两互并不是两两互素的。素的。37 “中国剩余定理中国剩余定理”不仅有光辉的历史意义，直到现不仅有光辉的历史意义，直到现在还是一个非常重要的定理。在还是一个非常重要的定理。197

33、01970年，年轻的苏联数学年，年轻的苏联数学家尤里家尤里.马季亚谢维奇（马季亚谢维奇（）（）（2828岁）岁）解决了希尔伯特提出的解决了希尔伯特提出的2323个问题中的第个问题中的第1010个问题，轰动个问题，轰动了世界数学界。他在解决这个问题时，用到的知识十分了世界数学界。他在解决这个问题时，用到的知识十分广泛，而在一个关键的地方，就用到了我们的祖先一千广泛，而在一个关键的地方，就用到了我们的祖先一千多年前发现的这个多年前发现的这个“中国剩余定理中国剩余定理”。“中国剩余定理中国剩余定理”意义意义38希尔伯特 希尔伯特的第希尔伯特的第1010个问题：个问题：丢番丢番图方程的可解性图方程的可

34、解性 能求出一个整系数方程的整数能求出一个整系数方程的整数根，称为根，称为丢番图方程可解丢番图方程可解。希尔伯。希尔伯特的问题，特的问题，能否用一种由有限步构能否用一种由有限步构成的一般算法判断一个丢番图方程成的一般算法判断一个丢番图方程的可解性？的可解性？19701970年，苏联的年，苏联的IO.B.IO.B.马马季亚谢维奇证明了希尔伯特所期望季亚谢维奇证明了希尔伯特所期望的算法不存在。的算法不存在。39 四、有趣的应用四、有趣的应用 某单位有某单位有100100把锁，分别编号为把锁，分别编号为1,2,3,1001,2,3,100。现在要。现在要对钥匙编号对钥匙编号,使外单位的人看不懂使外单

35、位的人看不懂,而本单位的人一看见锁的而本单位的人一看见锁的号码就知道该用哪一把钥匙。号码就知道该用哪一把钥匙。解解 把锁的号码被把锁的号码被3,5,73,5,7去除所得的三个余数来作钥匙的号码（首去除所得的三个余数来作钥匙的号码（首位余数是位余数是0 0时，也不能省略）。这样每把钥匙都有一个三位数编号。例时，也不能省略）。这样每把钥匙都有一个三位数编号。例如如2323号锁的钥匙编号是号锁的钥匙编号是232232号号,52,52号锁的钥匙编号是号锁的钥匙编号是123123号。号。8 8号锁号锁231,19231,19号锁号锁145,45145,45号锁号锁003,52003,52号锁号锁123.

36、123.因为只有因为只有100100把锁把锁,不超过不超过105,105,所以锁的编号与钥匙号是一一对应所以锁的编号与钥匙号是一一对应的。的。如果希望保密性再强一点儿如果希望保密性再强一点儿,则可以把刚才所说的钥匙编号加上一则可以把刚才所说的钥匙编号加上一个固定的常数作为新的钥匙编号系统。甚至可以每过一个月更换一次个固定的常数作为新的钥匙编号系统。甚至可以每过一个月更换一次这个常数。这样这个常数。这样,仍不破坏锁的号与钥匙的号之间的一一对应仍不破坏锁的号与钥匙的号之间的一一对应,而外人而外人则更难知道了。则更难知道了。40 1.1.有有5 5个外形相同的乒乓球，其中只有个外形相同的乒乓球，其中

37、只有1 1个重量不标个重量不标准的次品乒乓球。现再给你一个标准球；请用一架不带砝准的次品乒乓球。现再给你一个标准球；请用一架不带砝码的天平，最多两次使用该天平，找出上述次品乒乓球。码的天平，最多两次使用该天平，找出上述次品乒乓球。2.2.有有1212个外形相同的乒乓球，个外形相同的乒乓球，其中只有其中只有1 1个重量不标准的次品乒乓球。请用一架不带砝码个重量不标准的次品乒乓球。请用一架不带砝码的天平，最多三次使用该天平，找出上述次品乒乓球，并的天平，最多三次使用该天平，找出上述次品乒乓球，并判断它是重于标准球，还是轻于标准球。判断它是重于标准球，还是轻于标准球。最优化思想最优化思想u最少次数完

38、成预定任务最少次数完成预定任务u最大限度发挥该天平的作用最大限度发挥该天平的作用请思考请思考:下面的问题如何解决？下面的问题如何解决？趣题趣题找次品找次品：41 求求“用用2 2，3 3，4 4，5 5，6 6，7 7，8 8，9 9除都余除都余1”1”的数。的数。答：答：求求“用用a除余除余a1 1，用，用b除余除余b1 1，用，用c除余除余c1”1”的的数（数（a,b,c是任意大于是任意大于1 1的自然数）的自然数）答：答：求求“用用2 2除余除余1,1,用用3 3除除2,2,用用m除余除余m1”1”的数。的数。答：答：思考题解答思考题解答42 求求“用用5 5，7 7，9 9，11 11 除都余除都余2”2”数。数。答：答：43本节结束本节结束谢谢！谢谢！44