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

【中国剩余定理|韩信点兵，物不知数和中国剩余定理】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.
这件事可以用反证法证明：若不能整除，则必有
因此
因此余数也可以表示成一个整数乘以加上另一个整数乘以的形式，又因为是小于的，这就和最开始的假设是最小的正整数相矛盾了，因此必有