韩信点兵的故事（中国数学史上非常著名的中国剩余定理）
“
中国古代数学有着辉煌的成就，今天大小吴将为大家介绍在中国数学史上非常著名的中国剩余定理。
1 韩信点兵问题
这个问题首先要从一个叫做“韩信点兵”的故事说起。
秦末时期，楚汉相争，汉初三杰之一的韩信有一次带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年由高斯得出的关于同余式解法的一般性定理，因而西方称之为“中国剩余定理”，成为了初等数论中非常重要的一个定理。
原创文章，作者：，如若转载，请注明出处：https://www.webacg.com/gushi/489756.html
相关推荐
-
有关科学家的故事（屠呦呦、袁隆平等八个故事）
电视剧《功勋》的幕前，是尘封功绩的八位首批“共和国勋章”获得者，他们伟大的故事被平实地讲述给更多人听；而《功勋》幕后，则是十多位艺术创作者，近百位演员，以及数以千计的演职人员，他们…
-
寓言故事有哪些？都讲述了什么道理呢？
寓言故事是一种文学体裁，它是用讽刺的方法，让人简单明了的领悟到故事中的道理。在我国，有很多著名的寓言故事，深受读者的喜爱。接下来，我就给大家介绍几个寓言故事。 一、农夫与蛇 农夫与…
-
泥人张的故事（天津“泥人张”）
打卡好地方【天津“泥人张”：家传六代小泥人】清朝道光年间，浙江绍兴人张万全举家迁居天津，以私塾为业，并制作一些泥制的小玩具、小摆设。其子张明山天资聪慧，能打破旧框框，扩大泥塑的范围…
-
三国时期的10个故事
《三国演义》中的10个经典故事 1、草船借箭 周瑜十分妒忌诸葛亮的才干。一天周瑜在商议军事时提出让诸葛亮赶制10万支箭。诸葛亮答应三天造好，立下了军令状。诸葛亮事后请鲁肃帮他借船、…
-
关于勤奋的故事（古人的14个勤奋故事）
韦编三绝 春秋时的书，主要是以竹子为材料制造的，把竹子破成一根根竹签，称为竹“简”，用火烘干后在上面写字。竹简有一定的长度和宽度，一根竹简只能写一行字，多则几十个，少则八九个。一部…
-
来听我讲讲守株待兔的故事
宋国有个农夫种着几亩地，他的地头上有一棵大树。一天，他在地里干活，忽然看见一只兔子箭一般地飞奔过来，猛地撞在那棵大树上，一下子把脖子折断了，蹬蹬腿就死了。这个农夫飞快地跑过去，把兔…
-
儿童经典故事100篇（一）
1.子欲养而亲不待 孔子在前往齐国的路上，突然听到有人在哭，声音显得很悲哀。 孔子对驾车的人说：“这哭声，虽然听起来很悲哀，却不是家中有人去世的悲痛之声啊！” 于是，赶着马车寻声到…
-
少儿故事（老巫婆和神奇的魔法书）
小熊安迪在山路上捡到了一本魔法书，奇怪的是上面密密麻麻的全是标点符号。 他想这是谁丢下的呢？ 我一定要还给他。 呵呵，肯定是小白兔丢的，他走路总是蹦蹦跳跳的。 小熊安迪这样想着，这…
-
民间关于马的故事（男子冒险救下生完孩子的母马）
相传很久以前，陈元乾家祖上还是个大大的土财主，可自他爷爷那辈起，因生意经营不善，陈家便开始走向了落寞。传到陈元乾这代，只能说是家徒四壁，食不果腹了。 这天，陈元乾想要去山上采一点野…
-
来自吕梁山下的柳林县一个女孩的的励志故事
吕梁山下的柳林县，地处晋陕大峡谷的黄河东岸，三川河绕城而过，西连陕北吴堡，东临吕梁市离石，依山带水，矿产丰富，是自明清以来晋西著名的商贸集散地。柳林人杰地灵，人才辈出，当年红军东征…