韩信点兵--剩余定理

《韩信点兵--剩余定理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、韩信点兵与中国剩余定理1一、“韩信点兵”的故事和《孙子算经》中的题目1.“韩信点兵”的故事韩信阅兵时，让一队士兵5人一行排队从他面前走过，他记下最后一行士兵的人数（1人）；再让这队士兵6人一行排队从他面前走过，他记下最后一行士兵的人数（5人）；再让这队士兵7人一行排队从他面前走过，他记下最后一行士兵的人数（4人），再让这队士兵11人一行排队从他面前走过，他记下最后一行士兵的人数（10人）。然后韩信就凭这些数，可以求得这队士兵的总人数。2这里面有什么秘密呢？韩信好像非常重视作除法时的余数32.《孙子算经》中的题目我国古代数学名著《孙子算经》中有“物不知数”的题目：今有物不知其数

2、，三三数之剩2，五五数之剩3，七七数之剩2，问物几何？4这里面又有什么秘密呢？题目给出的条件，也仅仅是作除法时的余数5《孙子算经》6二．问题的解答1．从另一个问题入手问题：今有物不知其数，二二数之剩1，三三数之剩2，四四数之剩3，五五数之剩4，六六数之剩5，七七数之剩6，八八数之剩7，九九数之剩8，问物几何？71）筛法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）8再从中挑“用5除余4”的数，…一直筛选下去，舍得下功夫，就一定可得结果。并且看起来，解，还不是唯一的；可能有无

3、穷多个解。9化繁为简的思想当问题中有很多类似的条件时，我们先只看其中两三个条件，这就是化繁为简。一个复杂的问题，如果在简化时仍然保留了原来问题的特点和本质，那么简化就“不失一般性”。学会“简化问题”与学会“推广问题”一样，是一种重要的数学能力。寻找规律的思想把我们的解题方法总结为筛法，是重要的进步，是质的飞跃：——找到规律了。筛法是一般性方法，还可以用来解决其他类似的问题。102）公倍数法①化繁为简我们还是先看只有前两个条件的简化题目。1，3，5，7，9，11，13，15，17，19，21，23，25，…（用2除余1）5，11，17，23，…（用3除余2）上述筛选过程的第一步

4、，得到:1，3，5，7，9，11，13，15，17，19，21，23，25，…其实是列出了“用2除余1”的数组成的数列。这个数列实际上是用带余除法的式子得到的。11所谓“带余除法”，是指整数的如下“除法”：被除数，除数,必唯一存在商和余，使12当余时，则，称为“整除”，或“整除”，这是通常除法“”的另一种表达形式。所以，带余除法是通常除法的推广。13回到求“用2除余1的数”的问题。设这样的数为，则。这里是被除数，2是除数，是商，1是余，且。14这就是“带余除法”的式子。当取时，用上式求得的正好组成上述数列1，3，5，7，9，11，13，15，17，19，21，23，25，…1

5、5接着从中筛选出“用3除余2”的数，就是挑出符合下面“带余除法”表达式的数，这里可取0，1，2，3，4，…再继续做下去。。。。。。16如果我们不分上面两步，而是一上来就综合考虑两者，则就是要解联立方程组17那么，为了解这个方程组，除了刚才的筛法外，还有没有更加巧妙的解法？我们考察上边两个方程的特点，发现，两个“带余除法”的式子，都是“余数比除数少1”。于是想到，如果把被除数再加1，不是余数就为0了吗？换句话说，不是就出现整除的情况了吗？18于是把上边每个方程两边都加上1，成为这说明，既是2的倍数，又是3的倍数，因此，它是2与3的公倍数。由此想到19对整个问题寻找规律问题：今有

6、物不知其数，二二数之剩1，三三数之剩2，四四数之剩3，五五数之剩4，六六数之剩5，七七数之剩6，八八数之剩7，九九数之剩8，问物几何？20②寻找规律设问题中，需要求的数是，则被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]的倍数。21即这就是原问题的全部解，有无穷多个解，其中第一个解是2519；我们只取正数解，因为“物体的个数”总是正整数。22[思]：①求“用2除余1，3除余2，…用m除余

7、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，9，11除都余2”的数。232．《孙子算经》中“有物不知其数”问题的解答问题：今有物不知其数，三三数之剩2，五五数之剩3，七七数之剩2，问物几何？241）筛法.2，5，8，11，14，17，20，23，26，29，…（用3除余2）8，23，…（用5除余3）23，…（用7除余2）由此得到，23是最小的一个解。至于下一个解是什么，要