韩信点兵--剩余定理

更新时间:2023-03-29 18:13:01 阅读量: 基础教育 文档下载

说明:文章内容仅供预览,部分内容可能不全。下载后的文档,内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的,是否完整无缺。

韩信点兵与中国剩余定理

一、“韩信点兵”的故事和《孙子算经》 韩信点兵”的故事和《孙子算经》 中的题目 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/4ryl.html

Top