秦王暗点兵（秦王暗点兵每百列则余一人）

鸡年伊始，有小伙伴问了一个有趣的数鸡蛋的智力题：

其实这类题代表了一类“不知其数”的智力趣题，而且由来已久，最早可以上溯到我国公元4、5世纪左右！

今天咱们先说说相关的故事，然后给出解法。

其中经典解法过程有点复杂难懂，小伙伴们要耐着性子，因为后面我们还会给出一个更简单粗暴的解法，很好懂哦！

孙子算经

此类问题的最早出处是《孙子算经》：

《九阴真经》是假的，这本《孙子算经》可是真的。它是我国古代重要的数学著作，作者已经无法考证，但基本可以确定，和《孙子兵法》的作者不是同一个人。

《孙子算经》共分三卷：

上卷叙述算筹记数的纵横相间制度和筹算乘除法；

中卷举例说明筹算分数算法和筹算开平方法；

下卷则列示了许多著名的问题，其中最经典的例子就是在后世广为流传的“鸡兔同笼”问题：

“今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？”

翻译过来就是：有一些鸡和兔同在一个笼子里，从上面数，有35个头；从下面数，有94只脚。求笼中各有几只鸡和兔？”

这个问题后来传到日本，变成“鹤龟算”。如果小伙伴们有兴趣，咱们也可以有空单独说它。

《孙子算经》的下卷里，还记载着一类“物不知数”问题，就是我们今天的主题：

“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”

这虽然是1500多年前的文字，但我们在今天看来还是很好懂的：

有一批物体不知道数量，3个3个数，剩2个；5个5个数，剩3个；7个7个数，剩2个。

问这些物体有多少呢？

原书中不仅提出了问题，也给出了正确答案：23。

这个问题引起了后世国内外相当的关注，我国南宋的大数学家秦九韶对此问题有深入研究，并进一步开创了对一次同余式理论的研究工作，推广了“物不知数”的问题。

在西方，德国数学家高斯于公元1801年出版的《算术探究》中明确地写出了解决此问题的定理，等到公元1852年，英国基督教士将《孙子算经》“物不知数”问题的解法传到欧洲，之后西方人发现，《孙子算经》之作者给出的解法符合高斯的定理，而我国的研究早了一千多年。

因此在全世界的数学史里，西方人将此定理称为“中国剩余定理”或者“孙子剩余定理”，这也是中国人的骄傲之一。

韩信点兵

在我国民间流传着类似的“韩信点兵”故事：

韩信是我国汉初著名的军事家，他神机妙算，百战百胜。

传说，有一次战斗前，他为了弄清楚敌方兵力，亲自化装到敌营外侦察，隔着寨墙听里面敌将练兵。

他听到里面按3人一行整队，剩1人；按5人一行整队，剩2人；按7人一行整队，剩3人；按11人一行整队，剩1人。

据此，韩信很快推算出敌兵一共有892人。于是他针对敌情调兵遣将，一举把敌人击溃了。

这就是“韩信点兵”或者“韩信暗点兵”的故事。

由此可见，韩信的神机妙算是基于其扎实的数学功底的。

在中国古代，这个故事还有不少有趣的别名，比如“鬼谷算”，“秦王暗点兵”，“剪管术”，“隔墙算”，等等。

无论是“物不知其数”，还是“韩信点兵”，在今天，这些研究余数的问题都被归纳为同余问题。

经典解法

中国剩余定理

那么这类问题到底如何解呢？

比如《孙子算经》里的例子：三三数之剩二，五五数之剩三，七七数之剩二，问物几何？

该书给出的解法是：

70*2 21*3 15*2-2*105=23。

这个解法不太容易看懂，需要简单解释下：

首先要解释一点：所有这类同余问题，其解答往往都不唯一。因为只要在得到的一个答案上累加所有除数的最小公倍数，就可以不断得到同时满足题目条件的其他答案。

由于这个原因，我们研究同余问题时，往往研究的是最小正整数的解。

本题解法最巧妙之处，在于找到70，21和15这三个数。

70被3除余1，且能被5和7整除，所以70*2被3除余2；

21被5除余1，且能被3和7整除，所以21*3被5除余3；

15被7除余1，且能被3和5整除，所以15*2被7除余2。

所以把70*2，21*3和15*2加起来得到233，它就能同时满足被3除余2，被5除余3和被7除余2这三个条件了。

接下来，由于3、5、7的最小公倍数是105，所以从233中减去105的若干倍就能得到最小正整数解。

233-105*2=23，这就是最后的精简答案。

这个解法就是著名的中国剩余定理的内容。这个经典解法中规中矩，而且放之四海皆可用。

缺点也很明显：就是对于不熟悉的小伙伴来说，过程略显复杂，计算量也很大。尤其是当问题中的条件很多时，要找到中间过渡的那些数（70，21，15这些）再进行计算，难度和复杂度也都不小。

快捷解法

同余问题的快捷解法也有，很简单粗暴。

思路基于一个简单事实：

同余的数间隔都是相同的，一点一点往后排就可以。

比如：一个数被2除余1，那会是多少？

1，3，5，7，9，11，13，15，17，19，21，23，25，……

相隔为2。

那一个数被3除余2，会是多少？

那就是2，5，8，11，14，17，20，23，……

相隔为3。

那一个数被2除余1又被3除余2呢？

那就是上面两串数的公共数：

5，11，17，23，29，……

相隔为6，6是2和3的最小公倍数。

看出名堂了吧。

这时如果要再加条件：被5除余4呢？

上面这串数里第一个满足这个新加条件的是29。

再往后，相隔就应该是2，3，5的最小公倍数30。

所以下一个同时满足被2除余1、被3除余2、被5除余4三个条件的数，就是29 30=59。

以此类推。

从问题中的任意一个条件出发，先找到一个满足该条件的数；然后每增加一个条件，都用之前的所有条件里出现除数的最小公倍数往上加，直到满足新条件为止。

用这个方法，我们可以来解上文提到的韩信点兵的原题：

按3人一行，剩1人；

按5人一行，剩2人；

按7人一行，剩3人；

按11人一行，剩1人。

最少有多少人？

——3人一行剩1人：最少1人。

5人一行，剩2人：这时要不断加3：

1，不满足；

1 3=4，不满足；

4 3=7，满足。

7人一行，剩3人：这时要不断加的是3，5的最小公倍数15：

7，不满足；

7 15=22，不满足；

22 15=37，不满足；

37 15=52，满足。

11人一行，剩1人：这时要不断加3，5，7的最小公倍数105：

52，不满足；

52 105=157，不满足；

157 105=262，不满足；

262 105=367，不满足；

367 105=472，不满足；

472 105=577，不满足；

577 105=682，不满足；

682 105=787，不满足；

787 105=892，满足。

所以答案就是892。

从这个过程中大家能够看出，这个方法的特点是思路简单，可操作性强；而且用这个方法推出来的满足各条件的数一定是最小正数解，不会像剩余定理那样，得出的答案还要再减去最小公倍数的若干倍才能得到最小正数解。

同时，一个进阶的技巧是：在面对很多条件时，我们可以选择以余数相同的数作为推理的起点，这样可以大幅减少计算量。

开篇问题的解答

用上述快捷方法，可以比较轻松地搞定开篇的问题：

被2除余1，

被3除余0，

被4除余1，

被5除余4，

被6除余3，

被7除余0，

被8除余1，

被9除余0。

先注意到9是3的倍数，被9整除的数一定被3整除；再结合被7除余0，那么我们的推理起点就是7*9=63。

63已经满足了被2除余1，被3除余0，被6除余3，被7除余0，被9除余0；

此时2，3，6，7，9的最小公倍数是126。

来看被4除余1：

63不满足，

63 126=189满足。

此时2，3，4，6，7，9的最小公倍数是252。

来看被5除余4：

189满足。

此时2，3，4，5，6，7，9的最小公倍数是1260。

来看被8除余1：

189不满足，

189 1260=1449，满足。

此时所有条件都满足：所以1449就是答案了。

补充一句，这类同余问题中还有一些特殊情况，可以更简单地处理。

比如一个数被2，3，4，5，6，7，8，9除都余1：

第一个满足条件的当然就是数1啦。

后面的数，就在1的基础上不断加上2，3，4，5，6，7，8，9的最小公倍数2520就可以。

另一类问题比较隐蔽，但道理是一样的：

被2除余1，被3除余2，被4除余3，被5除余4，被6除余5，被7除余6，被8除余7，被9除余8。

这个问题的超快捷解法是：被所有这些除数除，都正好少1，那咱给他凑1个，不就全都整除了吗？

所以答案就是2，3，4，5，6，7，8，9的最小公倍数2520再减去1，2519。

另外，当条件中的各除数之间，存在着倍数或公因数的关系时，是很可能出现无解的情况哒！

比如一个数被6除余3，被8除余2：这样的数其实是不存在的。

余音

中国剩余定理的内容，被我国明朝数学家程大位编成了一首诗歌：

三人同行七十稀，五树梅花廿一枝。

七子团圆月正半，除百零五便得知。

这首诗歌在金庸先生的著作《射雕英雄传》里原文引用了，作者借黄蓉之口解出了瑛姑的难题，看完此文的你是不是也像黄蓉一样冰雪聪明：）