韩信暗点兵

我国汉初军事家韩信，神机妙算，百战百胜。传说在一次战斗前为了弄清敌方兵力，韩信化装到敌营外侦察，隔着高大寨墙偷听里面敌将正在指挥练兵。

只听得按3人一行整队时最后剩零头1人，按5人一行整队时剩零头2人，7人一行整队时剩零头3人，11人一行整队时剩零头1人。据此韩信很快算出敌兵有892人。于是针对敌情调兵遣将，一举击败了敌兵。这就是流传于民间的故事“韩信暗点兵”。

“韩信暗点兵”作为数学问题最早出现在我国的《孙子算经》中。原文是：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何子”

用现代话来说：“现在有一堆东西，不知它的数量。如果三个三个地数最后剩二个，五个五个地数最后剩三个，七个七个地数最后剩二个，问这一堆东西有多少个？”

该书给出的解法是：

N=70×2+21×3+15×2-2×105

这个解法巧妙之处在于70、21、15这三个数。

70可以被5和7整除，并且是用3除余1的最小正整数，因此2×70被3除余2；

21可以被3和7整除，并且是用5除余1的最小正整数，因此3×21被5除余3；

15可以被3和5整除，并且是用7除余1的最小正整数，因此2×15被7除余2。

这样一来，70×2+21×3+15×2被3除余2，被5除余3，被7除余2。这个数大于100，容易算出3、5、7的最小公倍数是105。从这个数中减去两倍的105，不会影响被3、5、7除所得的余数。

N=70×2+21×3+15×2-2×105=23

仿照《孙子算经》中“物不知数”问题的解法，来算一算“韩信暗点兵”：N=385×1+231×2+330×3+210×1-1155

=2047-1155=892

“韩信暗点兵”在中国古代数学史上有过不少有趣的别名，如“鬼谷算”、“秦王暗点兵”、“剪管术”、“隔墙算”等。

这就是著名的“中国剩余定理”或“孙子剩余定理”。