韩信点兵-中国剩余定理
汉⾼祖刘邦曾问⼤将韩信：“你看我能带多少兵？”韩信斜了刘邦⼀眼说：“你顶多能带⼗万兵吧！”汉⾼祖⼼中有三分不悦，⼼想：你竟敢⼩看我！“那你呢？”韩信傲⽓⼗⾜地说：“我呀，当然是多多益善啰！”刘邦⼼中⼜添了三分不⾼兴，勉强说：“将军如此⼤才，我很佩服。现在，我有⼀个⼩⼩的问题向将军请教，凭将军的⼤才，答起来⼀定不费吹灰之⼒的。”韩信满不在乎地说：“可以可以。”刘邦狡黠地⼀笑，传令叫来⼀⼩队⼠兵隔墙站队，刘邦发令：“每三⼈站成⼀排。”队站好后，⼩队长进来报告：“最后⼀排只有⼆⼈。”“刘邦⼜传令：“每五⼈站成⼀排。”⼩队长报告：“最后⼀排只有三⼈。”刘邦再传令：“每七⼈站成⼀排。”⼩队长报告：“最后⼀排只有⼆⼈。”刘邦转脸问韩信：“敢问将军，这队⼠兵有多少⼈？”韩信脱⼝⽽出：“⼆⼗三⼈。”刘邦⼤惊，⼼中的不快已增⾄⼗分，⼼想：“此⼈本事太⼤，我得想法个岔⼦把他杀掉，免⽣后患。”⼀⾯则佯装笑脸夸了⼏句，并问：“你是怎样算的？”韩信说：“⾂幼得黄⽯公传授《孙⼦算经》，这孙⼦乃⿁⾕⼦的弟⼦，算经中载有此题之算法，⼝诀是：
三⼈同⾏七⼗稀，
五树梅花开⼀枝，
七⼦团圆正⽉半，
除百零五便得知。”
刘邦出的这道题，可⽤现代语⾔这样表述：
“⼀个正整数，被3除时余2，被5除时余3，被7除时余2，如果这数不超过100，求这个数。”
《孙⼦算经》中给出这类问题的解法：“三三数之剩⼆，则置⼀百四⼗；五五数之剩三，置六⼗三；七七数之剩⼆，置三⼗；并之得⼆百三⼗三，以⼆百⼀⼗减之，即得。凡三三数之剩⼀，则置七⼗；五五数之剩⼀，则置⼆⼗⼀；七七数之剩⼀，则置⼗五，⼀百六以上，以⼀百五减之，即得。”⽤现代语⾔说明这个解法就是： ⾸先出能被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除的余数不会变，从⽽所得的数都能满⾜题⽬的要求。由于所求仅是⼀⼩队⼠兵的⼈数，这意味着⼈数不超过100，所以⽤233减去105的2倍得23即是所求。
这个算法在我国有许多名称，如“韩信点兵”，“⿁⾕算”，“隔墙算”，“剪管术”，“神奇妙算”等等，题⽬与解法都载于我国古代重要的数学著作《孙⼦算经》中。⼀般认为这是三国或晋时的著作，⽐刘邦⽣活的年代要晚近五百年，算法⼝诀诗则载于明朝程⼤位的《算法统宗》，诗中数字隐含的⼝诀前⾯已经解释了。宋朝的数学家秦九韶把这个问题推⼴，并把解法称之为“⼤衍求⼀术”，这个解法传到西⽅后，被称为“孙⼦定理”或“中国剩余定理”。⽽韩信，则终于被刘邦的妻⼦吕后诛杀于未央宫。
韩信点兵多多益善 请你试⼀试，⽤刚才的⽅法解下⾯这题：
⼀个数在200与400之间，它被3除余2，被7除余3，被8除余5，求该数。
发布评论