江苏龙网

  1. 首页 > 人文 > >

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

【中国剩余定理|韩信点兵，物不知数和中国剩余定理】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年由高斯得出的关于同余式解法的一般性定理 ， 因而西方称之为“中国剩余定理” ， 成为了初等数论中非常重要的一个定理 。
来源：大小吴的数学课堂
编辑：荔枝


    推荐阅读


    上一篇：太平天国的王府到底有多奢华？最简朴的忠王府，让李鸿章不敢直视

    下一篇：吹风机|Hi，给你们介绍一下熟悉的新朋友