韩信点兵是一个有趣的猜数游戏.如果你随便拿一把蚕豆(数目约在100粒左右),先3粒3粒地数,直到不满3粒时,把余数记下来;第二次再5粒5粒地数,最后把余数记下来;第三次是7粒一数,把余数记下来.然后根据每次的余数,就可以知道原来拿了多少粒蚕豆了.不信的话,还可以实地试验一下.例如,假如3粒一数余1粒,5粒一数余2粒,7粒一数余2粒,那么,原有蚕豆有多少粒呢?
这类题目看起来是很难计算的,可是我国古时候却流传着一种算法,名称也很多,宋朝周密叫它“鬼谷算”,又名“隔墙算”;杨辉叫它“剪管术”;而比较通行的名称是“韩信点兵”.最初记述这类算法的是一本名叫《孙子算经》的书,后来在宋朝经过数学家秦九韶的推广,又发现了一种算法,叫作“大衍求一术”.这在数学史上是极有名的问题,外国人一般把它称为“中国剩余定理”.至于它的算法,在《孙子算经》上就已经有了说明.
刘邦给韩信出的题其实是古算书《孙子算经》(公元4世纪)中最著名于世的“物不知其数”问题的翻版.我们来看看原题:“今有物不知其数,三三数之剩二,五五数之剩三,七七数之剩二,问物几何?”
设N 为所求的数,即N≡2(mod3),N≡3(mod5),N ≡2(mod7).用现代的话说,书中的解法是:一个数用3除,除得的余数乘以70;用5除,除得的余数乘以21,用7除,除得的余数乘以15.再求出这三个乘积的和,如果所得的数小于105,即为所求的答数.否则必须减去105的倍数,得到小于105的数才是答案.用数学符号表示为:N=70×2+21×3+15×2-105×2=23.《孙子算经》还说明,对任意的余数R1、R2、R3,只要将算式中的2,3,2换成R1、R2、R3,并调整105的系数就行了.对于任意的余数R1、R2、R3,其解答为:
N=70R1+21R2+15R3-105P(P 为正整数)
因此,凡是除数为3,5,7的同类问题,只要记住70,21,15,105这几个关键数字,就可依照上面的方法求出答案.文人墨客便把解法编成歌谣,其中暗藏计算时所用的数字:
三人同行七十希,五树梅花二十一支,七子团圆正半月,除百零五便得知.
例1 “今有物不知其数,三三数之余一,五五数之余三,七七数之余二,问物几何?”
解法1:利用上面公式,R1=1,R2=3,R3=2代入公式N=70R1+21R2+15R3-105P 得:
N=70×1+21×3+15×2-105=58.
解法2:首先找到被3除余1,且能被5和7整除的最小的数5×7×2,再找到被5除余3,且能被3和7整除的最小的数3×7×3.最后找出被7除余2,且能被3和5整除的最小的数3×5×2,把三个积相加再减去3,5,7的最小公倍数105的倍数,得结果.设这个数为N.则有:
N=5×7×2+3×7×3+3×5×2-105=70+63+30-105=58.
注:在5×7×2,3×7×3,3×5×2三个数中,一个数5×7×2除以3余1,另两个数:3×7×3,3×5×2都能被3整除,所以这三个数的和除以3余1.同理可推,这三个数的和除以5余3,除以7余2.
第一步:计算能被两数整除且除以第三个数余数是已知余数;
第二步:计算三个数都能整除的数(三数的最小公倍数);(www.xing528.com)
第三步:用第一步中的三个整除数之和减去第二步中的整除数之差(有时候是倍数);
第四步:计算结果即可.
例2 一个数除以3余2,除以5余3,除以7余4,求符合条件的最小的数.
解法1:5×7+3×7×3+3×5×4-105=35+63+60-105=53.
解法2:70×2+21×3+15×4-105×2=140+63+60-210=53.
例3 某人数棋子,三三数之余一,四四数之余3,五五数之不足一个,问最少有多少个棋子?
解:本题可以理解为:某数除以3余1,除以4余3,除以5余4.
∴4×5×2+3×5+3×4×2-3×4×5=40+15+24-60=19.
1900年,德国大数学家大卫·希尔伯特归纳了当时世界上尚未解决的最困难的23个难题.后来,其中的第十个问题在70年代被解决了,这是近代数学的五个重大成就.据证明人说,在解决问题的过程中,他是受到了“中国剩余定理”的启发的.
练习
1.韩信带1500名兵士打仗,战死四五百人,3人站一排,多出2人;5人站一排,多出4人;7人站一排,多出6人.求士兵还有多少人?
2.今有一堆棋子不知其数,三三数之余一,五五数之余二,七七数之余三,求这堆棋子至少有几枚?
3.某数除以3余1,除以5余2,除以7余4,除以13余6.求符合条件的最小的数.
4.一支部队不足一万人,3人站一列、5人站一列、9人站一列、13人站一列、17人站一列都余3人,这支部队有多少人?
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
