数学与统计学院
设为首页  |  加入收藏
首页 | 院系概况 | 教育教学 | 专业建设 | 学科建设 | 党建工作 | 团学工作 | 招生就业 | 实践教学 | 学科竞赛 | 校友会 | 资料下载 | 学校首页
资料下载
 教学科研文档 
 学生常用文档 
当前位置: 首页>>资料下载>>趣味数学>>正文
 
韩信点兵与中国剩余定理
2020-05-29 17:02   审核人:

三人同行七十稀,五树梅花二十一,七子团圆正半月,除百零五便得知。

实际上这个歌谣是一个古老数学题的解法。

韩信点兵

在数学典籍《孙子算经》中,有许多著名的数学问题。其中最有名的是鸡兔同笼问题。除此之外,另一个流传很广的经典问题,被后人称为物不知数问题:

有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二。问物几何?

意思是说:有一堆物体不知道有几个。如果三个三个分组,最后会剩下2个;如果五个五个分组,最后会剩下3个;如果七个七个分组,最后会剩下2个。问这些物体一共有几个?

后来,人们为了让这个问题更具体化,就把它改编成韩信点兵问题。

https://ss2.baidu.com/6ONYsjip0QIZ8tyhnq/it/u=3417620969,972343609&fm=173&app=25&f=JPEG?w=388&h=292&s=B1DC5E946CDBD1C816B4B06E0300D0F3

有一次战斗后,韩信要清点士兵的人数。让士兵三人一组,就有两人没法编组;五人一组,就有三人无法编组;七人一组,就有两人无法编组。那么请问这些士兵一共有几人?

https://ss2.baidu.com/6ONYsjip0QIZ8tyhnq/it/u=3428074736,869256126&fm=173&app=25&f=JPEG?w=640&h=360&s=B7955D8010E2C2BEC499E1D7030070B0

宋朝数学家秦九韶在《数书九章》中对这个问题做出了完整系统的解答。明朝数学家程大位在《算法统宗》中将解法编成易于上口的《孙子歌诀》,就是文初的那首歌谣。

https://ss2.baidu.com/6ONYsjip0QIZ8tyhnq/it/u=190509518,659013993&fm=173&app=25&f=JPEG?w=558&h=323&s=5D9BAF5505076D5B4891706A03003078

同余

现在我们一起来解决这个问题。首先我们来了解一下同余的概念。ab关于c同余,意思是说a除以cb除以c的余数相同。例如:8÷5=133÷5=03,所以83关于5同余,写作8≡3mod 5),其中mod读作。而且,由于3小于5,所以3本身就是3除以5的余数,因此8≡3mod 5)也可以理解为8除以5的余数是3

这样,韩信点兵问题就可以表示为数学语言了。有一个数字x,除以32,除以53,除以72 那么这个数字是多少?数学写法是

https://ss0.baidu.com/6ONWsjip0QIZ8tyhnq/it/u=548080875,1209547636&fm=173&app=25&f=JPEG?w=639&h=180&s=8436E53289E048134C7544DA0000C0B2

对于这个问题,最基本的解法是穷举法,就是把满足每个条件的数字写出来,然 后找到相同的数字。

除以3余数是2的数字有:258111417202326…除以5余数是3 的数字有:3813182328…除以7余数是2的数字有:29162330…我们发现,满足三个条件的第一个数字是23。所以23是这个问题的一个解。

但是,这个问题的解并不是唯一的。357彼此互质,它们的最小公倍数是105。也就是说,105除以3、除以5或者除以7都没有余数。如果一个数字x是满足要求的,那么在x上加上几个105都不会改变它对357的余数。比如,23是满足要求的,那么23+105=128也是满足要求的,23+210=233也是满足要求的。

所以这个问题最后的解就是23+105n,其中n=0123…

歌谣

那么,程大位在《算法统宗》中的歌谣又是什么意思呢?其实这个口诀是一个快速的算法,那就是:

三人同行七十稀:将除以3的余数乘以70;五树梅花二十一:将除以5的余数乘以21;七子团圆正半月:将除以7的余数乘以15(半个月);除百零五便得知:将以上三个数字相加,最后减去几个105

例如在韩信点兵问题中,除以3的余数是2,除以5的余数是3,除以7的余数是2,那么前三句话就是70×2+21×3+15×2=233233减去105等于128128减去105=23,那么23128233等就都是这个问题的答案。

这个口诀的证明其实也并不难:

70这个数字是57的倍数,并且除以31,也就是说,任何一个数添加一个70之后,不会改变除以57的余数,但是会在除以3的余数中多1。这样如果所求的数字除以32,就应该包含270,即70×221这个数字是37的倍数,并且除以51 也就是说,任何一个数添加了一个21之后不会改变除以37的余数,但是会在除以5的余数中多1。这样如果所求的数字除以53 就应该包含321,即21×315这个数字是35的倍数,并且除以71 也就是说,任何一个数添加了一个15之后不会改变除以35的余数,但是会在除以7的余数中多1。这样如果所求的数字除以72 就应该包含215,即15×2。将以上三个数字相加得到233,就可以得到一个满足条件:除以32,除以53,除以72的数字。105这个数字是357的公倍数,因此一个数字加上或者减去105之后,不会改变除以357的余数,因此在刚才得到的233上添加或者减去几个105,都是问题的解。最终,通过口诀我们还是可以得到通解:23+105n,其中n=0123…

中国剩余定理

余数问题是一个重要的数学问题,是计算机密码学的基石之一。世界著名的数学家欧拉、高斯等人,都曾经研究过这个问题。中国古代的先贤在这方面取得了丰硕的成果。韩信点兵问题只是一个例子,这样的问题有更加普遍和系统化的表示方法。而这个方法,就被世界称为中国剩余定理,是我国为数不多的获得世界公认的古代数学成就之一。

关闭窗口

Copyright © 2007-2014 http://sx.xxu.edu.cn All Rights Reserved.  新乡学院数学与统计学院 版权所有  站点地图

地址:河南省 新乡市 金穗大道东段 新乡学院 A-03#楼3楼  电话:0373-3683022、3682617、3682767  邮编:453003  Email:xxxysxx@126.com