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

内容导航：

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

中国剩余定理的典故

求解下面的问题：今有物不知其数，三三数之剩1，五五数之剩4，七七数之剩3，问物几何？

什么是“韩信点兵计算法？

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

“

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

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年由高斯得出的关于同余式解法的一般性定理，因而西方称之为“中国剩余定理”，成为了初等数论中非常重要的一个定理。

一、中国剩余定理的典故

“
中国古代数学有着辉煌的成就，今天大小吴将为大家介绍在中国数学史上非常著名的中国剩余定理。
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年由高斯得出的关于同余式解法的一般性定理，因而西方称之为“中国剩余定理”，成为了初等数论中非常重要的一个定理。

二、求解下面的问题：今有物不知其数，三三数之剩1，五五数之剩4，七七数之剩3，问物几何？

23+105n。

题目意思是说：有一堆物体不知道有几个。如果三个三个分组，最后会剩下2个；如果五个五个分组，最后会剩下3个；如果七个七个分组，最后会剩下2个。问这些物体一共有几个。

除以3余数是2的数字有：2、5、8、11、14、17、20、23、26…

除以5余数是3 的数字有：3、8、13、18、23、28…

除以7余数是2的数字有：2、9、16、23、30…

我们发现，满足三个条件的第一个数字是23。所以23是这个问题的一个解。

但是，这个问题的解并不是唯一的。3、5、7彼此互质，它们的最小公倍数是105。也就是说，105除以3、除以5或者除以7都没有余数。

如果一个数字x是满足要求的，那么在x上加上几个105都不会改变它对3、5、7的余数。比如，23是满足要求的，那么23+105=128也是满足要求的，23+210=233也是满足要求的。

所以这个问题最后的解就是23+105n，其中n=0，1，2，3…。

扩展资料：

孙子定理（剩余定理）是中国古代求解一次同余式组（见同余）的方法。是数论中一个重要定理。又称中国余数定理。一元线性同余方程组问题最早可见于中国南北朝时期（公元5世纪）的数学著作《孙子算经》卷下第二十六题，叫做“物不知数”问题。

《孙子算经》中首次提到了同余方程组问题，以及以上具体问题的解法，因此在中文数学文献中也会将中国剩余定理称为孙子定理。

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

三、什么是“韩信点兵计算法？

这个还是比较容易的，常出的题型如“今有物不知其数，三三数之剩二（就是这个数除以三的余数是二的意思），五五数之剩三，七七数之剩二，问物几何。”（韩信点兵算法也就是所谓的中国剩余定理）
我们来假设这个数为x，根据题意列出下式；
x≡2(mod3),
x≡3(mod5),
x≡2(mod7),
根据中国剩余定理，
m1=3,m2=5,m3=7,a1=2,a2=3,a3=2,
m=m1m2m3=3×5×7=105,
m1=m/m1=m2m3=5×7=35,
m2=m/m2=m1m3=3×7=21,
m3=m/m3=m1m2=3×5=15,
y1=m-11modm1=35-1mod3=2,
类似的y2,y3自己写，用word打这些慢麻烦的
写出了y2,y3后；我擦了辛辛苦苦打的求和在这边不知道用哪个语言才能显示
（我还是口述吧，x=求aimiyimodm的和从i=1开始到3）
=(2×35×2+3×21×1+2×15×1)mod105
=23
23即为所求数
，第一次回答很水，很多都没深入告诉你比如m-11其实-1是上标1是下标，
上标-1表示的是m1的逆{即x≡mm-1a(modm)=x≡a(modm)}不写了
希望你能看懂，要是没看懂
可以在问我总之我表达能力不是太强