韩信点兵与中国剩余定理1教学提纲

1、韩信点兵与中国剩余定理1 2.孙子算经孙子算经中的题目中的题目 二问题的解答二问题的解答 1从另一个问题入手从另一个问题入手 问题：问题：今有物不知其数，二二数之剩今有物不知其数，二二数之剩1 1，三三，三三数之剩数之剩2 2，四四数之剩，四四数之剩3 3，五五数之剩，五五数之剩4 4，六六数，六六数之剩之剩5 5，七七数之剩，七七数之剩6 6，八八数之剩，八八数之剩7 7，九九数之，九九数之剩剩8 8，问物几何？，问物几何？ 1）筛法）筛法 5， 11， 17， 23， （ 用用3除余除余2） 11， 23， （ 用用4除余除余3）1，3，5，7，9，11，13，15，17，19， 21，2

2、3，25， （ 用用2除余除余1） 再从中挑再从中挑“用用5 5除余除余4 4”的数，的数， 化繁为简化繁为简的思想的思想 当问题中有很多类似的条件时，我们先只看其中两当问题中有很多类似的条件时，我们先只看其中两三个条件，这就是三个条件，这就是化繁为简化繁为简。 一个复杂的问题，如果在简化时仍然一个复杂的问题，如果在简化时仍然保留了原来问保留了原来问题的特点和本质题的特点和本质，那么简化就，那么简化就“不失一般性不失一般性”。 学会学会“简化问题简化问题”与学会与学会“推广问题推广问题”一样，是一一样，是一种重要的数学能力。种重要的数学能力。 2 2）公倍数法）公倍数法 化繁为简化繁为简 一个

3、数，被一个数，被2 2除余除余1 1，被，被3 3除余除余2 2，求这个数。求这个数。 所谓所谓“带余除法带余除法”，是指，是指整数整数的如下的如下“除法除法”： 被除数被除数 ，除数，除数 , 必唯一存必唯一存在在“商商” 和和“余余” ，使，使 q,0abqrrb0b ar 当余数当余数 时，则时，则 ，称为称为 “ 整除整除”，或，或 “ 整除整除 ”，这是通常除法，这是通常除法“ ” 的另一的另一种表达形式。所以，带余除法是通常除种表达形式。所以，带余除法是通常除法的推广。法的推广。0r abqab被baaqb 回到求回到求“用用2除余除余1的数的数”的问题。设这的问题。设这样的数为样

4、的数为 ，则，则 。这里。这里 是是被除数，被除数，2是除数，是除数， 是商，是商，1是余，是余， 且且 。x121xnx012 1n “用用3 3除余除余2 2”的数，就是挑出符合下的数，就是挑出符合下面面“带余除法带余除法”表达式表达式 的数，这里的数，这里 可取可取0 0，1 1，2 2，3 3，4 4， 232,(023)xn2n 1221.32xnxxn中的 把上边每个方程两边都加上把上边每个方程两边都加上1，成为，成为 这说明，这说明， 既是既是2的倍数，又是的倍数，又是3的的倍数，因此，它是倍数，因此，它是2与与3的公倍数。由此想到的公倍数。由此想到1212(1)13(1)xnx

5、n 1x只有前两个条件的简化题目的解为：只有前两个条件的简化题目的解为：X+1=k g2,3, k=1,2,3,4,X+1=k g2,3, k=1,2,3,4,X=6k-1, k=1,2,3,4,X=6k-1, k=1,2,3,4,对整个问题寻找规律对整个问题寻找规律问题：问题： 今有物不知其数，二二数之剩今有物不知其数，二二数之剩1，三三，三三数之剩数之剩2，四四数之剩，四四数之剩3，五五数之剩，五五数之剩4，六六，六六数之剩数之剩5，七七数之剩，七七数之剩6，八八数之剩，八八数之剩7，九九，九九数之剩数之剩8，问物几何？，问物几何？ 寻找规律寻找规律 设问题中，需要求的数是设问题中，需要求

6、的数是 ，则，则 被被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的倍数。的倍数。xx1x1xx 即即 这就是原问题的全部解，有无穷多个解，其中第这就是原问题的全部解，有无穷多个解，其中第一个解是一个解是2519；我们只取正数解，因为；我们只取正数解，因为“物体的物体的 个数个数”总是正整数。总是正

7、整数。 12,3,4,5,6,7,8,92520,1,2,3,xkkk 25201,1,2,3,xkk 思思： 求求“用用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”的数。的数。 2孙子算经孙子算经中中“有物不知其数有物不知其数” 问题的解答问题的解答 问题问题:今有物不知其数，今有物不知其数， 三三数之剩三三数之剩

8、2 2， 五五数之剩五五数之剩3 3， 七七数之剩七七数之剩2 2， 问物几何？问物几何？1）筛法）筛法.2，5，8，11，14，17，20，23，26，29，（用（用3除余除余2）8，23， （用（用5除余除余3）23， （用（用7除余除余2） 由此得到，由此得到，23是最小的一个解。是最小的一个解。 至于下一个解是什么，要把至于下一个解是什么，要把“”写出来才知道；写出来才知道； 实践以后发现，是要费一点儿功夫的。实践以后发现，是要费一点儿功夫的。 2）公倍数法）公倍数法 现在仿照上边用过的现在仿照上边用过的“公倍数法公倍数法”，设要求的数为设要求的数为 ，则依题意，得联，则依题意，得联立

9、方程组立方程组x1233253(*)72xnxnxn 按上一问题中按上一问题中“公倍数法公倍数法”解决问题的解决问题的思路：把思路：把方程两边同时加上或减去方程两边同时加上或减去一个什么一个什么样的数，就能使三个等式的右边分别是样的数，就能使三个等式的右边分别是3 3，5 5，7 7的倍数，从而等式左边就是的倍数，从而等式左边就是3 3，5 5，7 7的公倍的公倍数了。数了。 这要通过这要通过反复反复的试算去完成。的试算去完成。一种试算的方法一种试算的方法1233253(*)72xnxnxn 从第三个等式入手，两边加从第三个等式入手，两边加5（或减（或减2）则则得得 357(1)xn3(27)

10、xn或 则右边是则右边是7 7的倍数了，但两边加的倍数了，但两边加5 5（或减（或减2 2）并不能并不能使前两式的右边分别是使前两式的右边分别是3 3的倍数和的倍数和5 5的倍数，所以两的倍数，所以两边加边加5 5（或减（或减2 2）并不能使右边成为并不能使右边成为3 3，5 5，7 7的公倍的公倍数。再继续从第三个等式入手，为使第三个等式右数。再继续从第三个等式入手，为使第三个等式右边仍然保持是边仍然保持是7 7的倍数的倍数, ,可再加可再加 ( (或再减或再减 ），则，则 将将 代入试算、分析，代入试算、分析，7l3577(1)xlnl 3277()xhnh1,2,3l 7h(1,2,3)

11、h 或 最后发现，为达到目的（三个等式的右最后发现，为达到目的（三个等式的右边分别是边分别是3 3，5 5，7 7的倍数），最小的加的倍数），最小的加数是数是8282（l=11,5+7l=82 l=11,5+7l=82 时时) )（或最小的（或最小的减数是减数是2323，即当，即当h=3h=3时时,2+7h=23),2+7h=23) 用等式两边加用等式两边加82来求解，有来求解，有 用等式两边减用等式两边减23来求解，有来求解，有 多了一个多了一个“ ” ，因这时，因这时 也是正数，合也是正数，合 要求要求。0k123823(28)825(17)823,5,7105827(12)10582,1

12、,2,3,xnxnxkkxnxkk123233(7)235(4)233,5,7105237(3)10523,0,1,2,3,xnxnxkkxnxkkx 这两组解是一样的，都是这两组解是一样的，都是“23，23+105，23+2105，”。 原因是原因是82+23=105，故令，故令 ， 第一组解就成为第一组解就成为 便转化成第二组解。便转化成第二组解。1kk105(1)821051058210523xkkk 但是，这但是，这8282和和2323来之不易；并且如果来之不易；并且如果题目中的余数题目中的余数变了，就得重新试算，所以变了，就得重新试算，所以这方法缺少一般性，为使它具有一般性，这方法缺

13、少一般性，为使它具有一般性，要做根本的修改。要做根本的修改。 3）单因子构件凑成法）单因子构件凑成法 我们先对（我们先对（* *）式作两个方面的简化：）式作两个方面的简化：一方面一方面是每次只是每次只考虑考虑“一个除式一个除式”有余数的情况（即另两个除式都是整除有余数的情况（即另两个除式都是整除的情况）；的情况）；另一方面另一方面是把余数都简化为最简单的是把余数都简化为最简单的1 1。这样得。这样得到三组方程。到三组方程。1233253(*)72xnxnxn11122233331335(1);51(2);5(3)7771xnynznxnynznxnynzn （1 1）式意味着，在）式意味着，在

14、5 5和和7 7的公倍数中（的公倍数中（3535，7070，105105，）寻找被）寻找被3 3除余除余1 1的数；的数； （2 2）式意味着，在）式意味着，在3 3和和7 7的公倍数中（的公倍数中（2121，4242，6363，）寻找被）寻找被5 5除余除余1 1的数；的数； （3 3）式意味着，在）式意味着，在3 3和和5 5的公倍数中（的公倍数中（1515，3030，4545，）寻找被）寻找被7 7除余除余1 1的数。的数。11122233331335(1);51(2);5(3)7771xnynznxnynznxnynzn 对（对（1 1）式而言，这个数可以取）式而言，这个数可以取707

15、0，对（，对（2 2）式而言，这个）式而言，这个数可以取数可以取2121，对（，对（3 3）式而言，这个数可以取）式而言，这个数可以取1515。 于是（于是（1 1）式两边同减）式两边同减7070变为这样：变为这样：第二个等式右边仍是第二个等式右边仍是5 5的倍数，第三个等式右边仍是的倍数，第三个等式右边仍是7 7的倍数，而第一个等式右边的倍数，而第一个等式右边因为减的因为减的7070是是“用用3 3除余除余1 1”的数，正好原来也多一个的数，正好原来也多一个1 1，减，减没了。第一个等式右边也成为了倍数，是没了。第一个等式右边也成为了倍数，是3 3的倍数。的倍数。 1112223333133

16、5(1);51(2);5(3)7771xnynznxnynznxnynzn（2）式两边同减）式两边同减21变为变为 1112113703(23)703,5,7105705(14)10570,0,1,2,707(10)xnxkkxnxkkxn1222223213(7)213,5,7105215(4)10521,0,1,2,217(3)ynykkynykkyn （3 3）式两边同减）式两边同减1515变为变为 于是得到于是得到 1332332153(5)153,5,7105155(3)10515,0,1,2,157(2)znzkkznzkkzn 123105701052110515xkykzk 现

17、在重复一下：所得的现在重复一下：所得的x x是是被被3 3除余除余1 1，被被5 5和和7 7除余除余0 0的数；的数；y y是是被被5 5除余除余1 1，被，被3 3和和7 7除余除余0 0的数；的数；z z是是被被7 7除余除余1 1，被，被3 3和和5 5除余除余0 0的数。的数。 那么，凑出那么，凑出 ， s s 不就是我们需要求的数吗？不就是我们需要求的数吗？ 232sxyz 因为，用因为，用3去除去除s时，除时，除y及除及除z均余均余0 除除3y及除及除2z均余均余0， 又除又除x余余1 除除2x余余2，用用3除除s时余时余2。 用用5去除去除s时，除时，除x及除及除z均余均余0

18、除除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。 于是我们要于是我们要求的数求的数是是 这就是这就是孙子算经孙子算经中中“物不知其数物不知其数”一题的解，有无穷多解，最小的正整数解是一题的解，有无穷多解，最小的正整数解是2323（ 时）。时）。1231232322(10570)3(10521)2(10515)(70221 3152)105(232)70221 31521052, 1,0,1,2,3,sxy

19、zkkkkkkkk 2k 这里，（这里，（1 1），（），（2 2），（），（3 3）三式分别叫三个）三式分别叫三个“单子因构件单子因构件”，分别解得分别解得 每个单因子构件，都是用某一个数去除余每个单因子构件，都是用某一个数去除余1 1，用另两个数去除均，用另两个数去除均余余0 0的情况。再据题目要求余数分别是的情况。再据题目要求余数分别是2 2，3 3，2 2的情况，凑成的情况，凑成11122233331335(1);51(2);5(3)7771xnynznxnynznxnynzn232sxyz123105701052110515xkykzk 所以，上述方法叫所以，上述方法叫“单因子构件凑

20、成法单因子构件凑成法” 解决解决“由几个平行条件表述的问题由几个平行条件表述的问题”的方法的方法 （ 也称也称“孙子孙子华方法华方法”） 这种方法的最大优点是，可以这种方法的最大优点是，可以任意改变余数任意改变余数，加以，加以推广推广： 题：题： 有物不知其数，三三数之剩有物不知其数，三三数之剩a a，五五数，五五数 之剩之剩b b，七七数之剩，七七数之剩c c，问物几何？，问物几何？ 答：答：解为解为 （ 的选取应使的选取应使 ）.702115105sabck,kkZ0s 4 4）歌诀）歌诀 推广了的推广了的“物不知其数物不知其数”问题的解为问题的解为 明朝数学家程大位在明朝数学家程大位在算

21、法统宗算法统宗中把上式总结为中把上式总结为一首通俗易懂的歌决：一首通俗易懂的歌决： 三人同行七十稀，五树梅花廿一枝，三人同行七十稀，五树梅花廿一枝， 七子团圆正半月，除百零五便得知。七子团圆正半月，除百零五便得知。 其中正半月是指其中正半月是指1515，这个口诀把，这个口诀把3 3，5 5，7 7；7070，2121，1515及及105105这几个关键的数都总结在内了。详细说，歌诀的这几个关键的数都总结在内了。详细说，歌诀的含义是：用含义是：用3 3除的余数乘除的余数乘7070，5 5除的余数乘除的余数乘2121，7 7除的余数除的余数乘乘1515，相加后再减去（，相加后再减去（“除除”当当“

22、减减”讲）讲）105105的适当倍的适当倍数，就是需要求的（最小）解了。数，就是需要求的（最小）解了。702115105sabck 当然，解，不是唯一的，每差当然，解，不是唯一的，每差105105，都是另一个解答，但如果结合实际问题，都是另一个解答，但如果结合实际问题，答案往往就是唯一的了。例如一队士兵的答案往往就是唯一的了。例如一队士兵的大约人数，韩信应是知道的。大约人数，韩信应是知道的。 三、中国剩余定理三、中国剩余定理 12471247年南宋的数学家秦九韶把年南宋的数学家秦九韶把孙子算经孙子算经中中“物不知其数物不知其数”一题的方法推广到一般的情况，得一题的方法推广到一般的情况，得到称之

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

24、其中其中 是是 的最小公倍数；的最小公倍数； 是是 的公倍数，而且被的公倍数，而且被 除所得除所得余数为余数为1； 是任意整数。是任意整数。 id12,nd dd12,nd dd12,nr rr12,nd dd111,iinddddDkxxkDrlrlrlrlxnn332211il 要注意的是，用上述定理时，要注意的是，用上述定理时， 必须两两互素。前面的问题中，必须两两互素。前面的问题中，3，5，7是两是两两互素的，所以两互素的，所以“三三数，五五数，七七数三三数，五五数，七七数”得得余数后可用此公式。但余数后可用此公式。但“四四数，六六数，九四四数，六六数，九九数九数”得余数后就不能用此公

25、式，因为得余数后就不能用此公式，因为4、6、9并不是两两互素的。并不是两两互素的。12,nd ddu中国剩余定理中国剩余定理 设 （ ）， ， 则同余组 （ ）的解为 。 其中 满足1,jimmnji1nmmmM21iimrxmodni, 2, 1MrmMkxniiiimod1ik 其中 称为“定母定母”，M 称为“衍母衍母”， 称为“衍数衍数”； 称为“乘率乘率”。u大衍求一术大衍求一术 用中国剩余定理解一次同余组问题的关键在于求用中国剩余定理解一次同余组问题的关键在于求解同余式：解同余式： iiimmMkmod1ni, 2, 1imimMik 秦九韶大衍求一术求同余式秦九韶大衍求一术求同余

26、式 的程序：的程序：iiimmMkmod1baxmod1ba 1ab大衍求一大衍求一 术云：术云：置奇右上，定居置奇右上，定居右下，立天元一右下，立天元一于左上。于左上。baxmod1 1r 11qc 1q1a先以先以 右上除右右上除右下，所得商数与下，所得商数与左上一相生，入左上一相生，入左下。左下。中国古代数学：少广方程 1122cqc 2r 2q 1c 1r然后乃以右行上下然后乃以右行上下以少除多，递互除以少除多，递互除之，所得商数随即之，所得商数随即递互累乘，归左行递互累乘，归左行上、下。上、下。 1233ccqc 3r 3q 2c 2r 4r 3r 4q 2344ccqc 3c 4r

27、 5r 5q 3455ccqc 4c 32221212nnnnccqc 12 nr 12 nq 22 nr 22 nc 221222nnnnccqc 12nr 12 nc nq2 12 nr须使右上末后奇须使右上末后奇一而止，乃验左一而止，乃验左上所得，以为乘上所得，以为乘率。率。&数书九章数书九章卷一卷一“推计土功推计土功”题：题： 27mod120 x&数书九章数书九章卷二“余米推数”题： “问有米铺诉被盗去米一般三箩，皆适满，不记细数。今左壁箩剩一合，中间箩剩一升四合，左壁箩剩一合。后获贼，系甲、乙、丙三名。甲称当夜摸得马勺，在左壁箩满舀入布袋；乙称踢着木履，在中箩舀入袋

28、；丙称摸得漆碗，在右边箩舀入袋；将归食用，日久不知数。索得三器：马勺满容一升九合；木履容一升七合；漆碗一升二合，欲知所失米数，计赃结断三盗各几何。”12mod117mod1419mod1x相当于求同余组3876mod11132345228115204x3876mod31933876121719M衍母：20412171M22812192M32317193M衍数： 19mod12041k19mod1141k151k17mod12282k17mod172k52k12mod13233k12mod1113k113k乘率： “中国剩余定理中国剩余定理”不仅有光辉的历史意义，直到不仅有光辉的历史意义，直到现

29、在还是一个非常重要的定理。现在还是一个非常重要的定理。19701970年，年轻的年，年轻的苏联数学家尤里苏联数学家尤里. .马季亚谢维奇（）（）（2828岁）解决了希尔岁）解决了希尔伯特提出的伯特提出的2323个问题中的第个问题中的第1010个问题，轰动了世个问题，轰动了世界数学界。他在解决这个问题时，用到的知识十界数学界。他在解决这个问题时，用到的知识十分广泛，而在一个关键的地方，就用到了我们的分广泛，而在一个关键的地方，就用到了我们的祖先一千多年前发现的这个祖先一千多年前发现的这个“中国剩余定理中国剩余定理”。 希尔伯特的第10个问题： 丢番图方程的可解性 能求出一个整系数方程的能求出一个整系数方程的整数根，称为丢番图方程整数根，称为丢番图方程可解。可解。希尔伯特问，能否希尔伯特问，能否用一种由有限步构成的一用一种由有限步构成的一般算法判断一个丢番图方般算法判断一个丢番图方程的可解性？程的可解性？1970年，苏联的IO.B.马季亚谢维奇证明了希尔伯特所期望的算法不存在。 希尔伯特希尔伯特 四、有趣的应用四、有趣的应用 某单位有某单位有100100把锁，分别编号为把锁，分别编号为1 1