数学中国

 找回密码
 注册
搜索
热搜: 活动 交友 discuz
查看: 108|回复: 6

韩信点兵,物不知数和中国剩余定理

[复制链接]
发表于 2020-10-7 18:55 | 显示全部楼层 |阅读模式
韩信点兵,物不知数和中国剩余定理

以下文章来源于大小吴的数学课堂 ,作者大小吴

中国古代数学有着辉煌的成就,今天大小吴将为大家介绍在中国数学史上非常著名的中国剩余定理

1 韩信点兵问题

这个问题首先要从一个叫做“韩信点兵”的故事说起。


淮阴侯韩信(约前231年-前196年)

秦末时期,楚汉相争,汉初三杰之一的韩信有一次带1500名兵士打仗,战死四五百人。为了统计剩余士兵的个数,韩信令士兵3人一排,多出2人;5人一排,多出4人;7人一排,多出6人。韩信据此很快说出人数:1049人。汉军本来就十分信服韩信大将军,经此之后就更加相信韩信是“天神下凡,神机妙算",于是士气大振,鼓声喧天,在接下来的战役中汉军步步紧逼,楚军乱作一团,大败而逃。韩信由此名扬天下,被后世誉为“兵仙“,“神帅”。




韩信点兵问题

2 孙子算经与物不知数问题

实际上,这类问题就是在求解初等数论中的同余方程组。在数学史上韩信点兵问题也被称为物不知数问题,最早记载于一千多年前的《孙子算经》中:

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



宋朝数学家秦九韶于1247年《数书九章》卷一、二《大衍类》对“物不知数”问题做出了完整系统的解答。明朝数学家程大位将解法编成易于上口的《孙子歌诀》:

“三人同行七十稀,五树梅花廿一支(二十一),七子团圆正半月,除百零五使得知。”



3 中国剩余定理





求解上述问题的过程与方法就称为“中国剩余定理”,又称为“孙子定理”。

中国剩余定理的传播最早在1852年由英国来华传教士伟烈亚力将《孙子算经》中“物不知数”问题的解法传至欧洲。

1874年,英国数学家马西森指出此法符合1801年由高斯得出的关于同余式解法的一般性定理,因而西方称之为“中国剩余定理”,成为了初等数论中非常重要的一个定理。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
发表于 2020-10-15 20:30 | 显示全部楼层
中国剩余定理会用到求乘法的逆元(古人叫乘率),当然简单的问题也可以不用。
谢谢陆教授给了我一个普遍方法,适用于各种类型(总共有3种类型)。谢谢!解决大问题了!
在大素数的快速判断,RSA密码的破解等等,都会用到!
回复 支持 反对

使用道具 举报

发表于 2020-10-17 20:50 | 显示全部楼层
其实,韩信点兵问题的最小解是104人,而不是1049人。
孙子算经与物不知数问题的最小解是128
回复 支持 反对

使用道具 举报

发表于 2020-10-17 21:58 | 显示全部楼层
在这个时代,闭门造车,远不如集思广益。
回复 支持 反对

使用道具 举报

发表于 2020-10-18 04:51 | 显示全部楼层
您看看这样出题:
今有物不知其数,三、三数之余2,五、五数之余1,七、七数之余4,13、13数之余10,55、55数之余21,56、56数之余39,问物几何?
回复 支持 反对

使用道具 举报

发表于 2020-10-18 14:23 | 显示全部楼层
题:
今有物不知其数,三、三数之余2,五、五数之余1,七、七数之余4,13、13数之余10,55、55数之余21,56、56数之余39,问物几何?

解:
21/5余数1,
39/7余数4,
与前面不矛盾,所以,有解,
3*5*7*13*11*8=120120,
120120/3=40040,
120120/5=24024,
120120/7=17160,
120120/13=9240,
120120/55=2184,
120120/56=2145,
40040模3 的逆元为:2,则满足3,3数余2的为:2*40040*2=160160,
24024模5 的逆元为:4,则满足5,5数余1的为:4*24024*1=96096,
17160模7 的逆元为:5,则满足7,7数余4的为:5*17160*4=343200,
9240模13 的逆元为:4,则满足13,13数余10的为:4*9240*10=369600,
2184模55 的逆元为:24,则满足55,55数余21的为:24*2184*10=524160,(因为96096/55=1747余11,加10就会余数为21),
2145模56 的逆元为:33,则满足56,56数余39的为:33*2145*7=495495,(因为343200/56=6128余32,加7就会余数为39),
495495/56=8848余7,所以,正确,
160160+96096+343200+369600+524160+495495=1988711,
1988711/3=662903余2,
1988711/5=397742余1,
1988711/7=284101余4,
1988711/13=152977余10,
1988711/55=36158余21,
1988711/56=35512余39,所以,都符合实际,正确!

回复 支持 反对

使用道具 举报

发表于 2020-10-18 15:37 | 显示全部楼层
1988711/120120=16余66791,所以,最小解为66791.
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 注册

本版积分规则

Archiver|手机版|小黑屋|数学中国 ( 京ICP备05040119号 )

GMT+8, 2020-10-22 14:34 , Processed in 0.062500 second(s), 16 queries .

Powered by Discuz! X3.4

Copyright © 2001-2020, Tencent Cloud.

快速回复 返回顶部 返回列表