韩信点兵的数学解密
致谢：写这两篇文章是受康慕宁老师课堂对此问题的阐述的启发，然后自己通过整理网络上关于韩信点兵和中国余式定理的资料完成。 韩信点兵的问题的原题应该是“物不知其数”的问题，用现在的话可以简述为：一个数除以3余2，除以5余3，除以7余2，问这个数是几？我国古代数学家关于“孙子问题”的解法，因其独特有效，而闻名于世，被称为“中国剩余定理”。“中国剩余定理”与“欧拉定理”、“费马小定理”都是著名的数论定理，在初等数论中有着重要的作用。那么什么是中国余式定理呢，下面是其一种表述及证明方法：令m和n是二互素的正整数，并令a,b是两个整数，0≤a ≤m-1,0 ≤b ≤n-1。则存在一个正整数x，使得x除以m的余数为a,x除以n的余数为b.即x可以表示为x=mp+a=nq+b其中，p,q是两个整数。证明：考虑n个整数：a,m+a,2m+a,…,(n-1)m+a.注意，这些数中的每一个除以m都余a.假定它们除以n的余数分别为r0,r1,…,rn-1,显然，其取值均在0,n-1之间。假设存在ri=rj=r (0≤i<j≤n-1),即有 im+a=qin+r及jm+a=qjn+r二式相减，有(j-i)m=(qj-qi)n。即n是(j-i)m的因子，而由于m,n互素，则n只能是(j-i)的因子。可是，j ≤n是已知的。这表明，假设存在ri=rj=r (0≤i<j ≤n-1)是不成立的。从而可知，上述序列中，模r的每个余数0~n-1都将出现一次。因此，数b(0≤b≤n-1)也出现过,即存在某个pm+a模n的余数为b ：pm+a=qn+b=x。了结了中国余式定理，我们就知道了前文提到的解决韩信点兵的口诀的由来。口诀是这样说的：三人同行七十稀，五树梅花廿一枝，七子团圆正半月，除百零五便得知。那在这里不妨就重新说一下如何运用口诀吧。三人同行七十稀，就是说把除以3所得的余数用70乘。五树梅花廿一枝，就是把除以5所得的余数用21乘。七子团圆正半月，就是把除以7所得的余数用15乘。除百零五便得知，把上述三个积加起来，减去105的倍数，所得的差即为所求（如果这个结果大于105就减去105，直到小于105为止，就是所求的数了）。解法如下：70*2+21*3+15*2=233，233－105×2=23。其实适合题意的所求数就是最小数23+N乘除数的最小公倍数105。好的，再回到口诀的由来这个问题上来， 为什么70，21，15，105有如此神奇作用？70，21，15，105是从何而来？先后70，21，15，105的性质（中国余式定理作为理论基础）：70除以3余1，被5，7整除，所以70a除以3余a，也被5，7整除；
21余以5余1，被3，7整除，所以21b除以5余b，也被3，7整除；
15除以7余1，被3，5整除，所以15c除以7余c，被3，5整除。
105则是3，5，7的最小公倍数。总之来说：70a＋21b＋15c是被3除余a，被5除余b，被7除余c的数，这个数如果大了，还要减去它们的公倍数，直到该数小于105（3、5、7的最小公倍数）。华罗庚在金坛初级中学上学时，老师出了“物不知其数”的算题。“23！”老师的话音刚落，华罗庚的答案就脱口而出。当时的华罗庚并未学过《孙子算经》，他是用如下妙法思考的：“三三数之剩二，七七数之剩二，余数都是二，此数可能是3×7+2=23，用5除之余3，所以23就是所求之数。” 1900年，德国大数学家大卫·希尔伯特归纳了当时世界上尚未解决的23个难题，其中第10个问题在20世纪70年代被解决了，这是近代数学的五个重大成就之一。据证明人说，在解决问过程中，他受到了“中国剩余定理”的启发。在应用中国剩余定理过程中，我们很容易想到列方程来解。例如上述问题，一个自然数用3、5、7除的余数分别是2、3、2，问这个自然数是几？可设该数为X(小于105),被3、5、7除的商为a、b、c,由题意得：3a+2=5b+3=7c+2，且X<=105。但是这个模型的求解就不是很容易的，可以说如果你用这个方法解这个问题，还不如你直接凑来得快。
页:
[1]