中国剩余定理——韩信的历史故事

秦末，各地战乱不断，楚汉交战。 一次战斗中，韩信率领1500人与楚王将领李封作战。 经过一番苦战，楚军大败，退到营中。 于是，韩信整顿部队，返回大本营。 到了一个山坡上，突然有后军来报楚军骑兵追来。 只见远处尘土飞扬，杀声震天。 汉军本来就已经很疲惫了，但此时却掀起了巨大的轩然大波。 韩信的部队到了坡顶，见敌军骑兵不足五百，赶紧命令部队迎敌。

他命令3名士兵排成一排，还有2名士兵。 韩信又命5名士兵排成一列，又发现了3名士兵。 然后他命令7名士兵排成一排，结果又多了3名士兵。 还有2个人。 于是韩信立即说道：“我军有兄弟一千零七十三人，追击者只有五百人，我们一定能打败敌人。”

韩信是如何快速计算出士兵数量的呢？

其实，一千多年前的《孙子算经》里就有这样一道算术题：“今之物，其数未知，数三三，还剩二，数五五”。 ，就还剩三个了，如果数到七、七，就还剩两个了。” ，询问事物的几何形状？”

明代数学家程大位也在诗词中总结了这一算法。 他写了：

三人同行七十九，五树二十一梅花5的倍数有哪些，

七子正月重聚，除以一百零五便知。

用今天的话来说：一个数除以 3 余数为 2，一个数除以 5 余数为 3，一个数除以 7 余数为 2。求这个数。 这类问题被称为“韩信观点”或“中国剩余定理”。

那么我们现在来解决这个问题：

第一步：首先列出满足其中一个条件的数字（一般是从小到大），即除以3余数为2的数字：2、5、8、11、14、17、20 、23、26、……； 第二章：然后列出满足第二个条件的数字，即除以5余数为3的数字：3、8、13、18、23、28、……； 步骤3：总结上一步3第一次出现的常见数是8.8，它是除以3余2、除以5余3的最小数。3和的最小公倍数5就是15。两个条件合为一就是8+15×n（n=0,1,2,...）。 列出这串数字：8、23、38、…； 第四步：列出满足第三个条件的数字，即除以7余数为2的数字2、9、16、23、30……； 步骤5：总结步骤3、4得到的数列，结果发现满足题目条件的最小数是23； 事实上，我们已经将问题中的三个条件合二为一了。 3、5、7的最小公倍数为105，满足三个条件的所有数为23+105×n（n=0,1,2,...）； 第六步：那么韩信所在点的士兵数量在1000-1100人之间，应该是23+105×10=1073人。

如果你随机抓一把蚕豆（数量在100颗左右），数到3，剩下1、5、2，剩下7、2，那么原来的蚕豆有多少颗？ ？

中国剩余定理（汉信电饼）的计算方法是：

步骤1：用3个一位数的余数乘以70（因为70既是5又是7的倍数，是3除余数1得到的数）； 第二步：用5个一位数的余数 下面的余数，乘以21（因为21既是3和7的倍数，又是除以5余数为1的数）； 第三步：将7个一位数的余数乘以15（因为15是3和5的倍数，而且是除以7余数为1的数）； 第四步：将这些数字相加，如果超过105（105是3、5、7的最小公倍数），则减去105，如果剩余的数字仍然大于105，则再次减去105，直到数字小于105这样得到的数就是原来的数。 基于这个原理，你可以很容易地将上一个问题代入一个计算公式：1×70+2×21+2×15-105 =142-105 =37。 因此，我们可以知道这堆蚕豆有37颗。