转贴 中国剩余定理

　　　　　　　　　中国剩余定理!

我国汉代有一位大将，名叫韩信。他每次集合部队，都要求部下报三次数，第一次按1～3报数，第二次按1～5报数，第三次按1～7报数，每次报数后都要求最
后一个人报告他报的数是几，这样韩信就知道一共到了多少人。他的这种巧妙算法，人们称为“鬼谷算”、 “隔墙算”、“秦王暗点兵”等。
　这种问题在《孙子算经》中也有记载：“今有物不知其数：三三数之余二，五五数之余三，七七数之余二，问物几何?” 它的意思就是，有一些物品，如果3个3个的数，最后剩2个；如果5个5个的数，最后剩3个；如果7个7个的数，最后剩2个；求这些物品一共有多少？这个问
题人们通常把它叫作“孙子问题”，
西方数学家把它称为“中国剩余定理”。到现在，这个问题已成为世界数学史上闻名的问题。
　　到了明代，数学家程大位把这个问题的算法编成了四句歌诀：
　 三人同行七十稀，五树梅花廿一枝；
七子团圆正半月，除百零五便得知。
　　 用现在的话来说就是：一个数用3除，除得的余数乘70；用5除，除得的余数乘21；用7除，除得的余数乘15。最后把这些乘积加起来再减去105的倍数，就知道这个数是多少。
字串4
《孙子算经》中这个问题的算法是：
70×2＋21×3＋15×2＝233
233－105－105＝23
所以这些物品最少有23个。
根据上面的算法，韩信点兵时，必须先知道部队的大约人数，否则他也是无法准确算出人数的。你知道这是怎么回事吗？这是因为，
被5、7整除，而被3除余1的最小正整数是70。
被3、7整除，而被5除余1的最小正整数是21；
被3、5整除，而被7除余1的最小正整数是15；
所以，这三个数的和15×2＋21×3＋70×2，必然具有被3除余2，被5除余3，被7除余2的性质。
以上解法的道理在于：
被3、5整除，而被7除余1的最小正整数是15；
被3、7整除，而被5除余1的最小正整数是21；
被5、7整除，而被3除余1的最小正整数是70。
因此，被3、5整除，而被7除余2的最小正整数是 15×2＝30；
字串6
被3、7整除，而被5除余3的最小正整数是 21×3＝63；
被5、7整除，而被3除余2的最小正整数是 70×2＝140。
于是和数15×2＋21×3＋70×2，必具有被3除余2，被5除余3，被7除余2的性质。但所得结果233（30＋63＋140＝233）不一定是满足
上述性质的最小正整数，故从它中减去3、5、7的最小公倍数105的若干倍，直至差小于105为止，即 233－1O5－105＝23。所以23就是被3除余2，被5除余3，被7除余2的最小正整数。



[[i] 本帖最后由 草儿 于 2008-7-5 23:39 编辑
]