韩信点兵与中国剩余定理

韩信点兵与中国剩余定理一、“韩信点兵”的故事和《孙子算经》中的问题1.“韩信点兵”的故事据传，韩信阅兵时，让一队士兵5人一行排队从他面前走过，他记下最后一行士兵的人数（1人）；再让这队士兵6人一行排队从他面前走过，他记下最后一行士兵的人数（5人）；再让这队士兵7人一行排队从他面前走过，他记下最后一行士兵的人数（4人），再让这队士兵11人一行排队从他面前走过，他记下最后一行士兵的人数（10人），然后韩信就凭这些数，可以求得这队士兵的总人数。这里面有什么秘密呢？韩信记下好像都是作除法时的余数，由此就可以求出士兵的总数吗？2.《孙子算经》中的问题我国古代数学名著《孙子算经》中有“物不知数”的问题：今有物不知其数，三三数之剩2，五五数之剩3，七七数之剩2，问物几何？这里面又有什么秘密呢？题目给出的条件，也仅仅是作除法时的余数，由此如何求出物体的总数？二．问题的解答1．从另一个问题入手问题：今有物不知其数，二二数之剩1，三三数之剩2，四四数之剩3，五五数之剩4，六六数之剩5，七七数之剩6，八八数之剩7，九九数之剩8，问物几何？1）筛法1，3，5，7，9，11，13，15，17，19，21，23，…（用2除余1）5，11，17，23，…（用3除余2）11，23，…（用4除余3）再从中挑“用5除余4”的数，“用6除余5的数”，…一直筛选下去，直到再从中挑“九九数之剩8”的数就可以得出结果，我们发现，每次筛选后都还有无穷多个数，所以解还不是唯一的；可能有无穷多个解。化繁为简的思想当问题中有很多类似的条件时，我们先只看其中两三个条件，这就是化繁为简。一个复杂的问题，如果在简化时仍然保留了原来问题的特点和本质，那么简化就“不失一般性”。学会“简化问题”与学会“推广问题”一样，是一种重要的数学能力。寻找规律的思想把我们的解题方法总结为筛法，是重要的进步，是质的飞跃：——找到规律了。筛法是一般性方法，还可以用来解决其他类似的问题。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”的数组成的数列，这个数列实际上是用带余除法的式子得到的。所谓“带余除法”，是指整数的如下的除法：被除数，除数，必唯一存在商和余，使得如下式子成立q,0abqrrb0bar当余时，则，称为整除，或“整除”，这是通常除法的另一种表达形式。所以，带余除法是通常除法的推广。0rabqab被baaqb回到求“用2除余1的数”的问题。设这样的数为，则，这里是被除数，2是除数，是商，1是余数，且。x121xnx0121n这就是“带余除法的式子。当取时，用上式求得的正好组成上述数列1，3，5，7，9，11，13，15，17，19，21，23，25，…121(012),xn10,1,2,3,4,nx接着从中筛选出“用3除余2”的数，就是挑出符合下面“带余除法”表达式的数，这里可取0，1，2，3，4，...232,(023)xn2n如果我们不分上面两步，而是一上来就综合考虑两者，则就是要解联立方程组1221.32xnxxn中的那么，我们进一步思考为了解这个方程组，除了刚才的筛法外，还有没有更加巧妙的解法？我们考察上边两个方程的特点，发现，两个“带余除法”的式子，都是“余数比除数少1”。于是想到，如果把被除数再加1，不是余数就为0了吗？换句话说，不是就出现整除的情况了吗？于是把上边每个方程两边都加上1，成为这说明既是2的倍数，又是3的倍数，因此，它是2与3的公倍数。由此想到对1212(1)13(1)xnxn1x原来整个问题寻找规律.原来整个问题是：今有物不知其数，二二数之剩1，三三数之剩2，四四数之剩3，五五数之剩4，六六数之剩5，七七数之剩6，八八数之剩7，九九数之剩8，问物几何？②寻找规律设问题中需要求的数是，则被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]的倍数.xxx1x1xx即这就是原问题的全部解，有无穷多个解，其中第一个解是2519；我们只取正数解，因为物体的个数总是正整数.1[2,3,4,5,6,7,8,9]2520,1,2,3,xkkk25201,1,2,3,xkk2．《孙子算经》中有“物不知其数”问题的解答问题：今有物不知其数，三三数之剩2，五五数之剩3，七七数之剩2，问物几何？在前面经验的基础上我们分别用“筛选”和“公倍数法”来解决，然后在思考有无其他方法.1）筛法.2，5，8，11，14，17，20，23，26，29，…（用3除余2）8，23，…（用5除余3）23，…（用7除余2）由此得到，23是最小的一个解。至于下一个解是什么，要把“…”写出来才知道；实践以后发现，是要费一点儿功夫的。2）公倍数法现在仿照上边用过的“公倍数法”，设要求的数为，则依题意，得联立方程组x1233253(*)72xnxnxn按上一问题中“公倍数法”解决问题的思路：把方程两边同时加上或减去一个什么样的数，就能使三个等式的右边分别是3，5，7的倍数，从而等式左边就是3，5，7的公倍数了。实践表明这要通过反复的试算去完成，一种误算的方法是观察法。先观察如下方程组1233253(*)72xnxnxn从其中第三个等式入手，两边加5（或减2）则得357(1)xn3(27)xn或则右边是7的倍数了，但两边加5（或减2）并不能使前两式的右边分别是3的倍数和5的倍数，所以两边加5（或减2）并不能使右边成为3，5，7的公倍数。再继续从第三个等式入手，为使第三个等式右边仍然保持是7的倍数，可再加（或再减），则有式子或将代入试算、分析，7l3577(1)xlnl3277()xhnh1,2,3l7h(1,2,3)h或最后发现，为达到目的，三个等式的右边分别是3，5，7的倍数即可.当时有，所以最小的加数是82.或当时有所以最小的减数是23.11l5782l3h2723h用等式两边加82来求解，有用等式两边减23来求解，有多了一个，因这时也是正数，符合要求。0k123823(28)825(17)82[3,5,7]105827(12)10582,1,2,3,xnxnxkkxnxkk123233(7)235(4)23[3,5,7]105237(3)10523,0,1,2,3,xnxnxkkxnxkkx这两组解是一样的，都是“23，23+105，23+2×105，……”。原因是82+23=105，故令第一组解就成为便转化成第二组解。1kk105(1)821051058210523xkkk但是，这82和23来之不易；并且如果题目中的余数变了，就得重新试算，所以这方法缺少一般性，为使它具有一般性，要做根本的修改。3）单因子构件凑成法下面我们采用一种新的思路来求解，我们先对前几页（*）式作两个方面的简化：一方面是每次只考虑“一个除式”有余数的情况（即另两个除式都是整除的情况）；另一方面是把余数都简化为最简单的1。这样得到三组方程。1233253(*)72xnxnxn11122233331335(1);51(2);5(3)7771xnynznxnynznxnynzn（1）式意味着，在5和7的公倍数中（35，70，105，…）寻找被3除余1的数；（2）式意味着，在3和7的公倍数中（21，42，63，…）寻找被5除余1的数；（3）式意味着，在3和5的公倍数中（15，30，45，…）寻找被7除余1的数.11122233331335(1);51(2);5(3)7771xnynznxnynznxnynzn对（1）式而言，这个数可以取70，对（2）式而言，这个数可以取21，对（3）式而言，这个数可以取15。于是（1）式两边同减70变为这样：第二式右边仍是5的倍数，第三式右边仍是7的倍数，而第一式右边因为减的70是“用3除余1”的数，正好原来也多一个1，减没了。第一式右边也成为了倍数，是3的倍数。11122233331335(1);51(2);5(3)7771xnynznxnynznxnynzn类似地，把（2）式两边同减21变为1112113703(23)70[3,5,7]105705(14)10570,0,1,2,707(10)xnxkkxnxkkxn1222223213(7)21[3,5,7]105215(4)10521,0,1,2,217(3)ynykkynykkyn（3）式两边同减15变为于是得到1332332153(5)15[3,5,7]105155(3)10515,0,1,2,157(2)znzkkznzkkzn123105701052110515xkykzk现在重复一下：所得的x是被3除余1，被5和7除余0的数；y是被5除余1，被3和7除余0的数；z是被7除余1，被3和5除余0的数。从而，凑出，s就是我们需要求的数232sxyz因为，用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.这样我们要求的数是这就是《孙子算经》中“物不知其数”一题的解，有无穷多解，当时，最小的正整数解是23.1231232322(10570)3(10521)2(10515)(702213152)105(232)7022131521052,1,0,1,2,3,sxyzkkkkkkkk2k这里，（1），（2），（3）三式分别叫三个“单子因构件”，分别解得每个单因子构件，都是用某一个数去除余1，用另两个数去除均余0的情况。再据题目要求余数分别是2，3，2的情况，凑成11122233331335(1);51(2);5(3)7771xnynznxnynznxnynzn232sxyz123105701052110515xkykzk所以，上述方法叫“单因子构件凑成法”——解决“由几个平行条件表述的问题”的方法（也称“孙子—华方法”）这种方法的最大优点是，可以任意改变余数，以加以推广：问题：有物不知其数，三三数之剩a，五五数之剩b，七七数之剩c，问物几何？答：解为（的选取应使）.702115105sabck,kkZ0s4）歌诀推广了的“物不知其数”问题的解为明朝数学家程大位在《算法统宗》中把上式总结为一首通俗易懂的歌决：三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。其中正半月是指15，这个口诀把3，5，7；70，21，15及105这几个关键的数都总结在内了。详细说，歌诀的含义是：用3除的余数乘70，5除的余数乘21，7除的余数乘15，相加后再减去（“除”当“减”讲）105的适当