韩信点兵与中国剩余定理
这就是《孙子算经》中“物不知其数” 一题的解,有无穷多解,最小的正整数解是 23( k 2 时)。
38
x 3n1 1 (1); x 5n2 x 7n 3
y 3n1 y 5n2 1 (2); y 7n 3
z 3n1 (3) z 5n2 z 7n 1 3
y 3n1 y 5n2 1 (2); y 7n 3
z 3n1 (3) z 5n2 z 7n 1 3
(1)式意味着,在5和7的公倍数中(35,70, 105,…)寻找被3除余1的数; (2)式意味着,在3和7的公倍数中(21,42, 63,…)寻找被5除余1的数; (3)式意味着,在3和5的公倍数中(15,30, 45,…)寻找被7除余1的数。
用等式两边减23来求解,有
x 23 3(n1 7) x 23 5(n2 4) x 23 7(n 3) 3 x 23 k [3,5, 7] k 105 x 105k 23, k 0,1, 2,3,
③ 求“用2,3,4,5,6,7,8,9除 都余1”
的数。
④ 求“用5,7,9,11 除都余2”的数。
18
2.《孙子算经》中“有物不知其数” 问题的解答
问题:今有物不知其数,
三三数之剩2,
五五数之剩3,
七七数之剩2,
问物几何?
1)筛法.
2,5,8,11,14,17,20,23,26,29,…(用3除余2)
31
对(1)式而言,这个数可以取70,对(2)式而言,这个
数可以取21,对(3)式而言,这个数可以取15。
x 3n1 1 (1); x 5n2 x 7n 3
y 3n1 y 5n2 1 (2); y 7n 3
z 3n1 (3) z 5n2 z 7n 1 3
X=6k-1, k=1,2,3,4,……
问题: 今有物不知其数,二二数之剩1,三三
数之剩2,四四数之剩3,五五数之剩4,六六
数之剩5,七七数之剩6,八八数之剩7,九九 数之剩8,问物几何?
15
②寻找规律
设问题中,需要求的数是 于是我们把被除数
x ,则 x 被2,3,4,
x 1 是
5,6,7,8,9去除,所得的余数都是比除数少1, 4,5,6,7,8,9均整除。也就是说,
然后韩信就凭这些数,可以求得这队士兵的总人数。
2
2.《孙子算经》中的题目
3
二.问题的解答
1.从另一个问题入手
问题:今有物不知其数,二二数之剩1,三三
数之剩2,四四数之剩3,五五数之剩4,六六数
之剩5,七七数之剩6,八八数之剩7,九九数之 剩8,问物几何?
1)筛法
1,3,5,7,9,11,13,15,17,19, 21,23,25,… ( 用2除余1)
33
(3)式两边同减15变为
z 15 3(n1 5) z 15 5(n2 3) z 15 7(n 2) 2
于是得到
z 15 k3 [3,5,7] k3 105 z 105k3 15, k3 0,1, 2,
5, 11, 17, 23, … ( 用3除余2) 11, 23,… ( 用4除余3)
再从中挑“用5除余4”的数,…
化繁为简的思想
当问题中有很多类似的条件时,我们先只看其中两
三个条件,这就是化繁为简。
一个复杂的问题,如果在简化时仍然保留了原来问
题的特点和本质,那么简化就“不失一般性”。
学会“简化问题”与学会“推广问题”一样,是一 种重要的数学能力。
多了一个“k 0 要求。
” ,因这时 x
也是正数,合
这两组解是一样的,都是“23,23+105,
23+2×105,……”。
原因是82+23=105,故令k k 1, 第一组解就成为
x 105(k 1) 82 105k 105 82 105k 23
[2,3,4,5,6,7,8,9]的倍数。
x 再加1,则 x 1就可被2,3,
2,3,4,5,6,7,8,9的公倍数,从而是其最小公倍数
x 1 k [2, 3, 4, 5, 6, 7, 8, 9] k
即 x 2520 k 1,k 1, 2, 3,
2520, k
1, 2, 3,
这就是原问题的全部解,有无穷多个解,其中第 一个解是 2519 ;我们只取正数解,因为“物体的 个数”总是正整数。
17
[思 ] : ① 求“用2除余1,3除余2,… 用m除余
m- 1”的数。
② 求“用a除余a -1,用b除余b-1,用c
除余c-1”的数。
(a,b,c是任意大于1的自然数)
4,…
x 2n1 1 中的x. x 3 n 2 2
12
把上边每个方程两边都加上1,成为
x 1 2(n1 1) x 1 3(n2 1)
这说明,
x 1
既是2的倍数,又是3的
倍数,因此,它是 2 与 3 的公倍数。由此想到
13
只有前两个条件的简化题目的解为: X+1=k g[2,3], k=1,2,3,4,……
这里,(1),(2),(3)三式分别叫三个“单子因构件”, 分别解得
x 105k1 70 y 105k2 21 z 105k3 15
每个单因子构件,都是用某一个数去除余1,用另两个数去除均 余0的情况。再据题目要求余数分别是2,3,2的情况,凑成
s 2x 3 y 2z
于是(1)式两边同减70变为这样:第二个等式右边仍是5 的倍数,第三个等式右边仍是7的倍数,而第一个等式右边 因为减的70是“用3除余1”的数,正好原来也多一个1,减 没了。第一个等式右边也成为了倍数,是3的倍数。
x 70 3(n1 23) x 70 5(n2 14) x 70 7(n 10) 3
l 1, 2,3
代入试算、分析,
x 2 7h 7(n3 h) (或h 1, 2,3)
最后发现,为达到目的(三个等式的右 边分别是3,5,7的倍数),最小的加
数是82(l=11,5+7l=82 时)(或最小的
减数是23,即当h=3时,2+7h=23)
用等式两边加82来求解,有 x 82 3(n1 28) x 82 k [3,5, 7] k 105 x 82 5(n2 17) x 82 7(n 12) x 105k 82, k 1, 2,3, 3
x 70 k1 [3,5, 7] k1 105 x 105k1 70, k1 0,1, 2,
(2)式两边同减21变为
y 21 3(n1 7) y 21 5(n2 4) y 21 7(n 3) 3 y 21 k2 [3,5, 7] k2 105 y 105k2 21, k2 0,1, 2,
x 105k1 70 y 105k2 21 z 105k3 15
34
现在重复一下:所得的x是被3除余1,
被5和7除余0的数;y是被5除余1,被3
和7除余0的数;z是被7除余1,被3和5
除余0的数。
35
那么,凑出
s 2x 3 y 2z
,
s 不就是我们需要求的数吗?
天津师范大学初等教育学院 李林波
1、“韩信点兵”的故事
韩信阅兵时,让一队士兵5人一行排队从他面前走过, 他记下最后一行士兵的人数(1人);再让这队士兵6人一
行排队从他面前走过,他记下最后一行士兵的人数(5 人);再让这队士兵7人一行排队从他面前走过,他记下 最后一行士兵的人数(4人),再让这队士兵11人一行排 队从他面前走过,他记下最后一行士兵的人数(10人)。
x 3n1 1 (1); x 5n2 x 7n 3
y 3n1 y 5n2 1 (2); y 7n 3
z 3n1 (3) z 5n2 z 7n 1 3
x 3n1 1 (1); x 5n2 x 7n 3
于是我们要求的数是
s 2x 3 y 2z 2(105k1 70) 3(105k2 21) 2(1(2k1 3k2 2k3 ) 70 2 21 3 15 2 105k k 2, 1,0,1, 2,3,
36
因为,用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,
37
又除z余1除2z余2, ∴用7除s时余2。
便转化成第二组解。
28
但是,这82和23来之不易;并且如果 题目中的余数变了,就得重新试算,所以 这方法缺少一般性,为使它具有一般性,
要做根本的修改。
29
3)单因子构件凑成法
x 3n1 2 x 5n2 3 x 7n 2 3 (*)
我们先对(*)式作两个方面的简化:一方面是每次只 考虑“一个除式”有余数的情况(即另两个除式都是整除 的情况);另一方面是把余数都简化为最简单的1。这样得 到三组方程。
8,23,… 23,… 由此得到,23是最小的一个解。
(用5除余3) (用7除余2)