中国剩余定理
       在中国数学史上，广泛流传着一个“韩信点兵”的故事：
    韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超，为汉朝的建立了卓绝的功劳。据说韩信的数学水平也非常高超，他在点兵的时候，为了保住军事机密，不让敌人知道自己部队的实力，先令士兵从1至3报数，然后记下最后一个士兵所报之数；再令士兵从１至５报数，也记下最后一个士兵所报之数；最后令士兵从1至7报数，又记下最后一个士兵所报之数；这样，他很快就算出了自己部队士兵的总人数，而敌人则始终无法弄清他的部队究竟有多少名士兵。
    这个故事中所说的韩信点兵的计算方法，就是现在被称为“中国剩余定理”的一次同余式解法。它是中国古代数学家的一项重大创造，在世界数学史上具有重要的地位。
    最早提出并记叙这个数学问题的，是南北朝时期的数学著作《孙子算经》中的“物不知数”题目。这道“物不知数”的题目是这样的：
  “今有一些物不知其数量。如果三个三个地去数它，则最后还剩二个；如果五个五个地去数它，则最后还剩三个；如果七个七个地去数它，则最后也剩二个。问：这些物一共有多少？”
    用简练的数学语言来表述就是：求这样一个数，使它被３除余２，被５除余３，被７除余２。《孙子算经》给出了这道题目的解法和答案，用算式表示即为：
   
                                        
    用现代的数学术语来说，这幅“开方作法本源图”实际上是一个指数为正整数的二项式定理系数表。稍懂代数的读者都知道：
                     
    《孙子算经》实际上是给出了这类一次同余式组
                         
的一般解：
           
    其中70、21、15和105这四个数是关键，所以后来的数学家把这种解法编成了如下的一首诗歌以便于记诵：
                “三人同行七十（７０）稀，
                  五树梅花二一（２１）枝。
                  七子团圆正半月（１５），
                  除百零五（１０５）便得知。”
　
    《孙子算经》的“物不知数”题虽然开创了一次同余式研究的先河，但由于题目比较简单，甚至用试猜的方法也能求得，所以尚没有上升到一套完整的计算程序和理论的高度。真正从完整的计算程序和理论上解决这个问题的，是南宋时期的数学家秦九韶。秦
九韶在他的《数书九章》（见图１一７一１）中提出了一个数学方法“大衍求一术”，系统地论述了一次同余式组解法的基本原理和一般程序。
    秦九韶为什么要把他的这一套计算程序和基本原理称为“大衍求一术”呢？这是因为其计算程序的核心问题是要“求一”。所谓“求一”，通俗他说，就是求“一个数的多少倍除以另一个数，所得的余数为一”。那么为什么要“求一”呢？我们可以从“物不知数”题的几个关键数字７０、２１、１５中到如下的规律：
　
                       
                       
　
图1-7-1 文澜阁四库全书本《数书九章》书影
　
                       
    其中70是5和7的倍数，但被3除余1；21是3和7的倍数，但被5除余1；15是3和5的倍数，但被7除余1，任何一个一次同余式组，只要根据这个规律求出那几个关键数字，那么这个一次同余式组就不难解出了。为此，秦九韶提出了乘率、定数、衍母、衍数等一系列数学概念，并详细叙述了“大衍求一术”的完整过程。（由于解法过于繁细，我们在这里就不展开叙述了，有兴趣的读者可进一步参阅有关书籍。）直到此时，由《孙子算经》“物不知数”题开创的一次同余式问题，才真正得到了一个普遍的解法，才真正上升到了
“中国剩余定理”的高度。
    从《孙子算经》到秦九韶《数书九章》对一次同余式问题的研究成果，在１９世纪中期开始受到西方数学界的重视。１８５２年，英国传教士伟烈亚力向欧洲介绍了《孙子算经》的“物不知数”题和秦九韶的“大衍求一术”；１８７６年，德国人马蒂生指出，中国的这一解法与西方１９世纪高斯《算术探究》中关于一次同余式组的解法完全一致。从此，中国古代数学的这一创造逐渐受到世界学者的瞩目，并在西方数学史著作中正式被称为“中国剩余定理”。
  例： 一个住校生，家里每星期给他36元生活费。该生每天实际只用生活费5元，某天他小姨到学校看他并给了50元钱，他用此钱买了两本喜爱的课外读物花10元，买学习用具花2元，放假回家后说明情况并给家长交回55元。
  问：该生带几个星期的生活费？实际在校住几天？一共有多少钱？花去多少钱？
  用方法二解：
  列式（36×□＋50－10－2）÷5＝□……55元
  ｛36×（5＋55-50＋10＋2）＋50－10－2｝÷（5×36）
  ＝（36×22＋50－10－2）÷180
  ＝830÷180……110
  答; 1，（110－50＋10＋2）÷36＝2， （括号内□内最小数）
  2，（110－55）÷5＝11， （括号外□内最小数）
  3 36×2＋50＝122，
  4，122－55＝67。
  答：该生带2个星期的生活费，实际住校11天，一共有122元，花去67元。
  2008.08.08
先提醒大家过去曾经有过的一个经验.

如果整数a除以整数b所得余数是1，那么，整数a的2倍、3倍、4倍、……、（b-1）倍除以整数b所得的余数就分别是

1×2=2，

1×3=3，

1×4=4，

…………

1×（b-1）=b-1.

例如，15÷7=2……余1，即

2×15÷7=4……余2，

3×15÷7=6……余3，

4×15÷7=8……余4，

5×15÷7=10……余5，


6×15÷7=12……余6.

还请大家注意一条经验.

从某数a中连续减去若干个b后，求所得的要求小于数b的差数，实际上就是求数a除以数b所得的余数.

例如，从758里连续减去若干个105后，求所得的要求小于105的差数，实际上就是求758除以105所得的余数.即

758÷105=7……余23.

下面我们就来研究“孙子问题”.

在我国古代算书《孙子算经》中有这样一个问题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”意思是，“一个数除以3余2，除以5余3，除以7余2.求适合这个条件的最小数.”这个问题称为“孙子问题”.关于孙子问题的一般解法，国际上称为“中国剩余定理”.

实际上，上面的问题我们可以这样来想：

分别写出除数3、5、7的两两公倍数.如下表：

我们在第一组数中选出合乎“除以7余2”的较小数——30；

在第二组数中选出合乎“除以5余3”的较小数——63；

在第三组数中选出合乎“除以3余2”的较小数——35.

根据和的整除性，可知30+63+35=128一定是一个同时合乎“被3除余2，被5除余3，被7除余2”的数（为什么？），但是不一定是最小的.要得到合乎条件的最小数，只要从中减去3、5、7的最小公倍数的若干倍，使得差数小于这个最小公倍数就是了.

3、5、7的最小公倍数是3×5×7=105，因此，由于前面的经验二，可知

128÷105=1……余23.

这个余数23就是要求的合乎条件的最小数.

有意义的是，虽然孙老先生的解法也是从对上表的思索得到的，但他的解法更具有一般性.亲爱的读者，你能猜想到孙子的一般解法吗？

【规律】

一个数除以3余2，除以5余3，除以7余2，求适合这个条件的最小数.孙子的解法是：

先从3和5、3和7、5和7的公倍数中相应地出分别被7、5、3除均余1的较小数15、21、70 ( 注释:此步又称为求"模逆"运算,利用扩展欧几里得法并借助计算机编程可比较快速地求得.当然,对于很小的数,可以直接死算 ).即

15÷7=2……余1，

21÷5=4……余1，

70÷3=23……余1.

再用到的三个较小数分别乘以所要求的数被7、5、3除所得的余数的积连加，

15×2+21×3+70×2=233. （将233处用i代替，用程序可以求出）


最后用和233除以3、5、7三个除数的最小公倍数.

233÷105=2……余23，

这个余数23就是合乎条件的最小数.

以上三个步骤适合于解类似“孙子问题”的所有问题.

【练习】

1.韩信点兵：有兵一队，若列成五行纵队，则末行一人，成六行纵队，则末行五人，成七行纵队，则末行四人，成十一行纵队，则末行十人.求兵数.

2.有一堆棋子，三个三个地数剩下2个，五个五个地数剩下4个，七个七个地数剩下6个.问这
堆棋子最少有多少个？（用两种方法解）

3.某数除以7余3，除以8余4，除以9余5.从小到大求出适合条件的十个数.
秦九韶著作
4.某数除以5余2，除以7余4，除以11余8.求适合条件的最小数.

5.一猴子数一堆桃子.两个两个地数剩下1个，三个三个地数剩下1个，五个五个地数剩下3个，七个七个地数剩下3个.问这堆桃子最少是多少个？

注释:此步又称为求"模逆"运算,利用扩展欧几里得法并借助计算机编程可比较快速地求得.当然,对于很小的数,可以直接死算

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。