中国余数定理和韩信点兵

打印 被阅读次数
在基础数论里有一个中国余数定理。给定一组正整数两两互素,也就是任意两个数没有大于一的公因子。现有一个未知数,它除以这个数组里每个数的余数是知道的,求解这个未知数。中国余数定理是对这个问题的解答。
	中国古代最有名的数学书“九章算术”里有一个问题:求知一个数,它除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思维 发表评论于
有趣!
登录后才可评论.