网易首页 > 网易号 > 正文 申请入驻

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

0
分享至

  

1 韩信点兵问题

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

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

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

  那么韩信是如何快速算出士兵人数的呢?韩信点兵问题可以用现代数学语言描述如下:若士兵人数是 ,则有 除以3余2,除以5余4,除以7余6.

  我们也可以用同余式来表示这个问题:

  我们发现,若将 ,则可以同时被3、5、7整除,即

  所以 一定是3、5、7的最小公倍数的整数倍,由于3、5、7两两互素,则

  所以

  即

  其中 是正整数,当 时

  这样,韩信就计算出了剩余士兵的人数。

  
韩信点兵问题 2 孙子算经与物不知数问题

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

  

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

  转化为现代数学语言,即解整数 满足的同余式

  这个问题和上文所说的韩信点兵问题类似,但是,它不具备上一个问题那么好的性质,因为无论使 加上或减去一个数,都无法同时被3、5、7整除。那么,这个问题该如何解决呢?

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

  

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

  这首诗的意思是:将除以3得到的余数乘以70,将除以5得到的余数乘以21,将除以7得到的余数乘以15,全部加起来后除以105得到的余数就是答案。

  根据这个算法,可得:

  因此物不知数问题的最小正整数解即为 ,事实上,23确实满足除以3余2,除以5余3,除以7余2,这个问题的通解为

  其中 是自然数。

  3 中国剩余定理

  对于这个问题,如果是一般情况,该如何处理呢?例如,有同余式:

  我们把这个问题分解成三个同余式方程组

  那么初始问题就有最小正整数解

  因此只要能找到满足条件的 即可。以 为例,由同余式可得,

  因此

  所以存在 使得

  因此

  其中 的存在性可以证明,因为有如下定理:

  

“ 若 ,则必然存在 使得

  对于这个定理的证明,可以考虑集合 中的最小正整数,只要证明这个最小正整数就是1即可。

  考虑其中最小的正整数 , ,只需证明 且 ,由于 互素,所以 只能为1.

  这件事可以用反证法证明:若 不能整除 ,则必有

  因此

  因此余数 也可以表示成一个整数乘以 加上另一个整数乘以 的形式,又因为 是小于 的,这就和最开始的假设 是最小的正整数相矛盾了,因此必有

  因此存在性得证。

  事实上这样的 不仅存在,而且也比较好寻找,其中70就是既能被5、7同时整除又能除以3余1的最小正整数,所以 ,同理可得 , ,因此这类问题就有了通解:

  原来上面的古诗中出现的70、21、15这三个数是这么来的!

  一般来讲,给定 个不同的素数 ,则同余方程组

  一定是有解的,求解这个问题只需构造基础解系:

  因此有

  因为 都是素数,因此 的存在性是显然的。

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

  中国剩余定理的传播最早在1852年由英国来华传教士伟烈亚力将《孙子算经》中“物不知数”问题的解法传至欧洲。1874年,英国数学家马西森指出此法符合1801年由高斯得出的关于同余式解法的一般性定理,因而西方称之为“中国剩余定理”,成为了初等数论中非常重要的一个定理。

  来源:大小吴的数学课堂

  编辑:荔枝

特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。

Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.

相关推荐
热点推荐

中国领导人向拜登致贺电,引发外媒关注

观察者网
2020-11-26 20:18:00

领跑新生活 当沃尔沃遇见上海马拉松

天天汽车
2020-11-26 17:12:03

房东拒绝退还租金,租客花1万将店面改成公厕,房东:租不出去了

青海生活频道V
2020-11-26 15:23:48

高以翔逝世一周年,好友吕晓栋前往祭拜,昏倒在墓地抢救无效逝世

谈资
2020-11-26 17:36:40

泰国王室后宫又开撕!废妃复宠被爆1000多张不雅照,王后下狠手?

英国报姐
2020-11-26 15:14:16

知名教授拿女性阴道开玩笑被怒怼,此前曾说“女生早结婚智商低”

易视频
2020-11-26 23:45:03

湖北知名企业家海南医院动手术致脑死亡 院方愿补偿但金额未达成一致

上游新闻
2020-11-26 10:30:45

太悲壮!今晚,华为突然宣布!

财闻汇评
2020-11-26 23:07:54

2男子澡堂嫖娼一名女子,导致女子吃不消报警,网友:别揽瓷器活

民生有看点
2020-11-26 21:32:43

柬埔寨黑暗的处女交易:12岁那年,母亲把她的童贞卖给了一个老头

娱乐叭秀
2020-11-25 01:26:11

掌握这项关键技术的,全世界算上中国只有四个,比能研制氢弹的还少……

澎湃新闻
2020-11-26 21:29:15

知名互联网企业单方面辞退P7员工三次败诉,员工复岗再收解聘通知

红星新闻
2020-11-26 20:07:08

发现妻子的“老情人”又来撩拨,想起妻子怀孕时跟对方发生过关系,男子冒充妻子将对方约出杀害

潇湘晨报
2020-11-25 15:21:32

美媒分析拜登的国务卿人选:要重新拉拢盟友应对中国

观察者网
2020-11-26 15:54:36

一夜之间,借呗被关闭!湖南男子怒怼马云:还我20万借呗

星空影视娱乐酱
2020-11-26 22:13:23

上海女子中奖林肯豪车,主办方“依法”耍赖被法院判决必须交车

青苗法鸣在线
2020-11-26 16:45:59

舌吻女导演、全L露屁股…王大陆人设崩塌,我看到了最真实的人性

高能少女
2020-11-26 10:51:18

“女人的性生活状态,看胸就知道了!”

窈窕妈妈
2020-11-25 19:17:14

重磅!美国将制裁艾睿!官方回应!

中国半导体论坛
2020-11-26 21:22:02

男子卡里8000万活期存款,急用却取不出来,银行员工:管理比较严

青海生活频道V
2020-11-26 15:52:32
2020-11-27 02:32:59
http://dingyue.ws.126.net/Zdas6IwVglEsxgS3dvc6uIgmeFl5xo3HuUx2glz7LChru1479706078756.jpg
中科院物理所
爱上物理,改变世界。
3722文章数 111331粉丝数
往期回顾 全部

教育要闻

教育最大的悲哀:老师让位,家长越位,学生错位

头条要闻

企业家术后脑死亡 家属:耳鼻喉医生做脑外科 医院像开玩笑

头条要闻

企业家术后脑死亡 家属:耳鼻喉医生做脑外科 医院像开玩笑

体育要闻

马刺神射重返意大利联赛 因对NBA球队的报价不满

娱乐要闻

怀孕身材依旧好!吉娜穿红裙秀香肩

财经要闻

科技要闻

任正非:新荣耀要做华为最强的竞争对手

汽车要闻

美女上车不怕走光 日产全新SUV座椅能旋转

态度原创

家居
艺术
房产
游戏
亲子

家居要闻

澳洲姐妹花回乡下爆改老房 养鸭养羊过神仙日子

艺术要闻

广东梅州纪念林风眠诞辰120周年

房产要闻

好消息!海南山海高速有望年内功能性通车

奇幻动作游戏《Gods Will Fall》预告片公布

亲子要闻

宝宝出生时“几斤几两”最有福气?