韩信点兵--剩余定理

韩信点兵与中国剩余定理

一、“韩信点兵”的故事和《孙子算经》 韩信点兵”的故事和《孙子算经》 中的题目 1.“韩信点兵”的故事 韩信点兵” 韩信点兵韩信阅兵时，让一队士兵 人一行排队从他面前走 韩信阅兵时，让一队士兵5人一行排队从他面前走 再让这队士兵6 过，他记下最后一行士兵的人数(1人);再让这队士兵 他记下最后一行士兵的人数( 人);再让这队士兵 人一行排队从他面前走过， 人一行排队从他面前走过，他记下最后一行士兵的人数 再让这队士兵7人一行排队从他面前走过 (5人);再让这队士兵 人一行排队从他面前走过，他记 人);再让这队士兵 人一行排队从他面前走过， 下最后一行士兵的人数( 人),再让这队士兵 再让这队士兵11人一行 下最后一行士兵的人数(4人),再让这队士兵 人一行 排队从他面前走过，他记下最后一行士兵的人数( 人 排队从他面前走过，他记下最后一行士兵的人数(10人)。 然后韩信就凭这些数， 可以求得这队士兵的总人数。 然后韩信就凭这些数 ， 可以求得这队士兵的总人数 。

这里面有什么秘密呢？ 这里面有什么秘密呢？

韩信好像非常重视作除法时的余数 韩信好像非常重视作除法时的余数

2.《孙子算经》中的题目 《孙子算经》我国古代数学名著《孙子算经》中有“物不知数” 我国古代数学名著《孙子算经》中有“物不知数” 的 题目： 题目： 今有物不知其数， 今有物不知其数， 三三数之剩2, 三三数之剩 ， 五五数之剩3, 五五数之剩 ， 七七数之剩2, 七七数之剩 ， 问物几何？ 问物几何？

这里面又有什么秘密呢？ 这里面又有什么秘密呢？

题目给出的条件， 题目给出的条件， 也仅仅是作除法时的余数 也仅仅是作除法时的余数5

《孙子算经》 孙子算经》

二.问题的解答1.从另一个问题入手 .

问题：今有物不知其数，二二数之剩 ，三三 问题：今有物不知其数，二二数之剩1,数之剩2,四四数之剩 ，五五数之剩4, 数之剩 ，四四数之剩3,五五数之剩 ，六六数 之剩5,七七数之剩 ，八八数之剩7, 之剩 ，七七数之剩6,八八数之剩 ，九九数之 剩8,问物几何？ ,问物几何？7

1)筛法 )1,3,5,7,9,11,13,15,17,19, , , , , , , , , , , 21,23,25,… , , , 除余1) ( 用2除余 ) 除余

5, 5,

11, 11,

17, 17,

23, 23, … ( 用3除余2) 3除余 除余2)

11, ,

23,… ,

除余3) ( 用4除余 ) 除余8

再从中挑“ 除余4”的数 再从中挑“用5除余 的数，… 除余 的数，

一直筛选下去，舍得下功夫， 一直筛选下去，舍得

下功夫，就一定可 得结果。 得结果。 并且看起来， 并且看起来，解，还不是唯一的；可能 还不是唯一的； 有无穷多个解。 有无穷多个解。9

化繁为简的思想 化繁为简的思想当问题中有很多类似的条件时，我们先只看其中两三个条件， 当问题中有很多类似的条件时，我们先只看其中两三个条件，这 就是化繁为简 化繁为简。 就是化繁为简。 一个复杂的问题，如果在简化时仍然保留了原来问题的特点和本 一个复杂的问题，如果在简化时仍然保留了原来问题的特点和本 那么简化就“不失一般性” 质，那么简化就“不失一般性”。 学会“简化问题”与学会“推广问题”一样， 学会“简化问题”与学会“推广问题”一样，是一种重要的数学 能力。 能力。

寻找规律的思想 寻找规律的思想筛法， 把我们的解题方法总结为筛法 是重要的进步，是质的飞跃： 把我们的解题方法总结为筛法，是重要的进步，是质的飞跃： ——找到规律了。 找到规律了。 找到规律了 筛法是一般性方法，还可以用来解决其他类似的问题。 筛法是一般性方法，还可以用来解决其他类似的问题。10

2)公倍数法① 化繁为简我们还是先看只有前两个条件的简化题目。 我们还是先看只有前两个条件的简化题目。除余1) 1,3,5,7,9,11,13,15,17,19,21,23,25,… ( 用2除余 ) , , , , , , , , , , , , , 除余 5, , 11, , 17, , 23, … , ( 用3除余 ) 除余2) 除余

上述筛选过程的第一步，得到: 上述筛选过程的第一步，得到: 1,3,5,7,9,11,13,15,17,19,21,23,25,… 11,13,15,17,19,21,23,25, 其实是列出了“ 其实是列出了“用2除余1”的数组成的数列。这个数列 除余1”的数组成的数列。 1”的数组成的数列 实际上是用带余除法的式子得到的。 带余除法的式子得到的 实际上是用带余除法的式子得到的。11

所谓“带余除法” 是指整数的如 所谓“带余除法”,是指整数的如 整数 下 “除法”: 除法” a b≠0 , 必唯一 被除数 r ,除数 q 存在商 和余 ，使

a = bq + r ,

0≤r<b

当余 r = 0 时，则 a = bq ,称为 “被b a 整除”,或 “ 整除” ba = 法“q b

a 整除 ”,这是通常除

” 的另一种表达形式。所以， 的另一种表达形式。所以，

带余 除法是通常除法的推广。 除法是通常除法的推广。

回到求“ 除余1的数 回到求“用2除余 的数”的问题。设 除余 的数”的问题。 这 样的数为

x,则

x = 2n1 + 1n1。这里

x是

被除数， 2是除数 被除数，2是除数， 0 ≤ 1 < 是除数， 且 。

是商， 是余 是余， 是商，1是余，

这就是“ x =

2n1 + 1(0 ≤ 1 < 2), 这就是“带余除 法”的式子。当取n1 = 0,1, 2,3, 4,L 时， 的式子。 用上式求得的 x 正好组成上述数列 1,3,5,7,9,11,13,15, , , , , , , , , 17,19,21,23,25,… , , , , ,

接着从中筛选出“用3除余2”的 就是挑出符合下面“带余除法” 数，就是挑出符合下面“带余除法”表达 式 ≤ 2 < 3) x = 3n2 + 2, (0n2

的数， 的数，这里

可取0, , , , , 可取 ，1,2,3,4,…

再继续做下去。。。。。。 再继续做下去。。。。。。16

如果我们不分上面两步， 如果我们不分上面两步，而是一上 来就综合考虑两者 综合考虑两者， 来就综合考虑两者，则就是要解联立方 程组 x = 2n1 + 1 中的x. x = 3n2 + 2

那么，为了解这个方程组， 那么，为了解这个方程组，除了刚才的筛法 外，还有没有更加巧妙的解法？ 还有没有更加巧妙的解法？ 我们考察上边两个方程的特点，发现， 我们考察上边两个方程的特点，发现，两个 “带余除法”的式子，都是“余数比除数少1”。 带余除法”的式子，都是“余数比除数少1

于是想到，如果把被除数再加1 于是想到，如果把被除数再加1,不是余数就为 把被除数再加 0了吗？换句话说，不是就出现整除的情况了吗？ 了吗？换句话说，不是就出现整除的情况了吗？ 整除的情况了吗

于是把上边每个方程两边都加上1, 于是把上边每个方程两边都加上 ，成为

x + 1 = 2(n1 + 1) x + 1 = 3(n2 + 1)这说明， 这说明，

x +1

既是2的倍数，又是 的 既是 的倍数，又是3的 的倍数

倍数， 因此， 它是2与 的公倍数 的公倍数。 倍数 ， 因此 ， 它是 与 3的公倍数 。 由此想到19

本文来源：https://www.bwwdw.com/article/t30j.html