中国余数定理和韩信点兵

在基础数论里有一个中国余数定理。给定一组正整数两两互素，也就是任意两个数没有大于一的公因子。现有一个未知数，它除以这个数组里每个数的余数是知道的，求解这个未知数。中国余数定理是对这个问题的解答。

	中国古代最有名的数学书“九章算术”里有一个问题：求知一个数，它除3余2，除5余3，除7余2.。书上没有给出这种问题的一般解法，但找出23这个数并不是很难。

	很多科普文章说这个问题的提出源自“韩信点兵”：韩信让一群士兵分别站成三人一排，五人一排，七人一排。每次站队时可能会有余下的士兵。从这三个余数就能知道这一群士兵有多少人。

	让我们来仔细看看这个过程，检查一下韩信点兵里可能会出现的问题。首先如果两个数除以三，五，七的余数是相同的，则两数之差可以整除三，五，七，因而就能整除这三个数的乘积一百零五。反之如果两数之差可以整除一百零五则它们除以三，五，七的余数是同样的。因而仅仅从三个余数无法唯一确定未知数。首先必须确定这个未知数在一个差别小于一百零五的范围，例如从一到一百零五，从两千三百到两千四百零四。

	下面我们假定一个等于一百零五的范围给定了。任意一个在这个范围里的数除三会有三个可能的余数，除五会有五个可能的余数，除七会有七个可能的余数，当然包括零余数。三个余数的所有可能刚好是一百零五。因而从三个余数可以唯一确定未知数。

	那么怎样从这三个余数决定未知数呢？有公式说从70m + 21n + 15p加减一百零五的适当倍数就能得出未知数。这里m,n,p是未知数除以三，五，七的余数。还可以列个表把每个数和它的三个余数列成四个数字一行的表，然后按照余数的顺序重新列表好从三个余数查出未知数。

	以未知数在一到一百零五为例。如果三个余数都为零未知数是一百零五。如果三个余数不都为零未知数是70m + 21n + 15p除以一百零五的余数。当然如果70m + 21n + 15p是在一到一百零四之间它就是未知数。在m=2,n=3,n=2时， 70m + 21n + 15p=233。然后把233除以105得到余数23。也可以列表第一行为 0， 0， 1， 15；第二行为 0， 0， 2， 30；一共一百零五行。 查表时则以余数为序从 2，3，2，23那一行得知未知数为23。

	如果未知数是在两千三百到两千四百零四之间，我们得把233加上2100得到2333这个数。查表的话，先得列个表把一百零五种可能的余数列出，后面列出有关的未知数。

	那么韩信在点兵知道三个余数后能不能一口报出士兵的人数呢？假如他知道人数不超过105，则看一下表他的确就能一口报出。要是用公式算则要费点功夫。要是人数多但在一个差105的范围内，查表也可以， 当然要多费点功夫。用公式算就更费功夫了。

	无论是查表还是用公式，韩信应该都是能做到的。列个表带在身边不是很难的事。至于他如何得到公式我们不清楚。但70，21，15是很特别的数，它们的余数分别为1，0，0；0，1，0；0，0，1。一旦他知道了公式记住用就行了。

	韩信没有带过兵和同时代的古罗马军队作战。韩信没法向他们学学更好的点兵法。古罗马的军队列成10人一排以十排作为一个方阵。如果不到一百人，数一下有几排人后再数余下的人数。点兵对于古罗马人是个很简单的事。

[野性de思维]

有趣！