中国剩余定理

没想到，古代韩信点兵的传说，后来竟然启发了计算机加密算法。 △韩信是左边那位，不是右边的 相传，楚汉争霸之时，韩信率1500名将士与楚军交战败退，退往山上，这时候敌军率五百骑杀奔而来，韩信便急速点兵迎敌。 韩信命令士兵3人一排，结果多出2名；接着命令士兵5人一排，结果多出3名；他又命令士兵7人一排，结果又多出2名。 韩信马上算出，军中还剩1073人，而敌人不足五百，而且居高临下、以众击寡，于是率军杀得敌方大败而逃。 韩信是如何算出人数的，背后的算法又是如何影响当今的计算机领域？且往下看。 韩信还是个数学家？ 当然，韩信算出士兵人数只是个传说matlab求余数，韩信本人并非数学大师。这个问题最早见于一本1700年前的古籍，已经是韩信死后600多年了。 在南北朝时期，《孙子算经》记述了这样一个问题。（注：这位孙子不是写《孙子兵法》的孙武） 原书是这样说的： 有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？ 意思是，一個整数除以三余二，除以五余三，除以七余二，求這個整数。 它就是中国剩余定理，也被叫做“韩信点兵”问题。 在近代数学中，很少有以中国数学家命名的重要定理，然而这样一条数学定理，名字里就有“中国”二字。 南宋时期，我国数学家秦九韶首先给出了这类问题的解法：大衍术。 直到500年后，著名数学家高斯才在自己的书中描述类似的结果。 那么问题来了：传说中的“韩信”到底是怎么算出来人数的呢？ “韩信点兵”问题求解 为了更好地理解和表述“韩信点兵”问题，我们引入一个新的数学概念——“同余”。 在数学上，如果a和b除以正整数m后的余数相同，则称a、b对于模m同余，韩信点兵用数学公式来表示就是（X是未知的人数）： X ≡ 2 (mod 3) X ≡ 3 (mod 5) X ≡ 2 (mod 7) 为了简化问题，我们先只考虑前两个同余条件，满足除以3余2、除以5余3的整数分别为： 2、5、8、11、14、17、20、23、26…… 3、8、13、18、23、28、33、38…… 可以看出，同时符合这两个条件的第一个数是8，第二个数是23。后面的每个解与前一个之差都应该是3和5的最小公倍数15，即： X = 8 + 15K （K是整数） 这样我们就把寻找的整数解缩小了，接着再加入第三个条件，找到分别满足X=8+15K和除以7余2的数：...