谈韩信点兵与中国剩余定理
高二级 叶景杰 陈栩炜
一千多年前的《孙子算经》中，有这样一道算术题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”按照今天的话来说：一个数除以3余2，除以5余3，除以7余2，求这个数。这样的问题，也有人称为“韩信点兵”.它形成了一类问题，也就是初等数论中的解同余式。
这题若用方程可轻易解出。但早在从前古人已用算术解出。《孙子算经》的解法：“三三数之剩二，则置一百四十；五五数之剩三，置六十三；七七数之剩二，置三十；并之得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一，则置十五，一百六以上，以一百五减之，即得。”翻译如下：
首先出能被5与7整除而被3除余1的数70，被3与7整除而被5除余1的数21，被3与5整除而被7除余1的数15。
此数被3除余2，则取数70×2＝140，140是被5与7整除而被3除余2的数。
此数被5除余3，则取数21×3＝63，63是被3与7整除而被5除余3的数。
此数被7除余2，则取数15×2=30，30是被3与5整除而被7除余2的数。
又，140＋63＋30=233，由于63与30都能被3整除，故233与140这两数被3除的余数相同，都是余2，同理233与63这两数被5除的余数相同，都是3，233与30被7除的余数相同，都是2。所以233是满足题目要求的一个数。
而3、5、7的最小公倍数是105，故233加减105的整数倍后被3、5、7除的余数不会变，从而所得的数都能满足题目的要求。所以用233减去105的2倍得23即是所求的最小数。
总结原理：
1.被除数增加（减少）除数的若干倍，余数不变
2.被除数扩大（缩小）若干倍，其余数也扩大（缩小）若干倍
明代数学家程大位用诗歌概括了这一算法，他写道：
三人同行七十稀，
五树梅花廿一枝，
七子团圆正月半，
除百零五便得知。
这首诗的意思是：用3除所得的余数乘上70，加上用5除所得余数乘以21，再加上用7除所得的余数乘上15，结果大于105就减去105的倍数，这样就知道所求的数了。
这个算法在我国有许多名称，如“韩信点兵”，“鬼谷算”，“隔墙算”，“剪管术”，“神奇妙算”等等，题目与解法都载于我国古代重要的数学著作《孙子算经》中。宋朝的数学家秦九韶把这个问题推广，并把解法称之为“大衍求一术”，这个解法传到西方后，被称为“孙子定理”或“秦九韶著作中国剩余定理”。
中国剩余定理拓展应用：
其表达形式有以下几种：
（1）“若自然数N不能被不大于(根号)√N的任何素数整除，则N是一个素数”。
（2）N=p1m1+a1=p2m2+a2=......=pkmk+ak 。其中 p1，p2，.....，pk表示顺序素数2，3，5，,,,,。a≠0。即N不能是2m+0，3m+0，5m+0，...，pkm+0形。若N<P（k+1）的平方 [注： 1，2，3，....，k，（k+1）是脚标， ，则N是一个素数。
例如，29，29不能够被根号29以下的任何素数2，3，5整除，29=2x14+1=3x9+2=5x5+4。 29小于7的平方49，所以29是一个素数。
（3）N≡a1(modp1)， N≡a2(modp2)，.....，N≡ak(modpk) 例如，29，29不能够被根号29以下的任何素数2，3，5整除，29=2x14+1=3x9+2=5x5+4。 29≡1(mod2)，29≡2(mod3)， 29≡4(mod5)。29小于7的平方49，所以29是一个素数。 以后平方用“*”表示，即：㎡=m*。 由于模p1，p2，....，pk 两两互素，根据孙子定理(中国剩余定理）知，在pk范围内有唯一解。 例如k=1时，N=2m+1，解得N=3，5，7。求得了（3，3*）区间的全部素数。 k=2时，N=2m+1=3m+1，解得N=7，13，19； N=2m+1=3m+2，解得N=5，11，17，23。求得了（5，5*）区间的全部素数。 k=3时, ---------------------| 5m+1-|- 5m+2-| 5m+3,| 5m+4.| ---------------------|---------|----------|--------|---------| n=2m+
1=3m+1= |--31----|--7, 37-|-13,43|--19----| n=2m+1=3m+2= |-11,41-|-17,47-|--23---|---29---| ------------------------------------------------------------ 求得了（7，7*）区间的全部素数。仿此下去可以求得任意大的数以内的全部素数。
参考文献:
1. 中国剩余定理
设整数m1,m2,m3,......,mn 两两互素，令（mi的连乘）。则对于任意的J在（1,n)整数，下列联立的同余式有解：
{xj≡1(mod mj)
{xj≡0(mod mi) i不等于j
令x为从1到najxj的和，则x适合下列联立同余式
x≡aj（mod mj）, j=1,2,3,.....,n
2.百度百科之素数定理
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论