中国剩余定理

在中国数学史上，广泛流传着一个“韩信点兵”的故事：

韩信是汉高祖刘邦手下的大将，他英勇善战，智谋超群，为汉朝的建立了卓绝的功劳。

据说韩信的数学水平也非常高超，他在点兵的时候，为了保住军事机密，不让敌人知道自己

部队的实力，先令士兵从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个.问这堆桃子最少是多少个？

注释:此步又称为求"模逆"运算,利用扩展欧几里得法并借助计算机编程可比较快

速地求得.当然,对于很小的数,可以直接死算

你看一下吧

孙子算经》中给出这类问题的解法：“三三数之剩二，则置一百四十；五五数之

剩三，置六十三；七七数之剩二，置三十；并之得二百三十三，以二百一十减之，

即得。凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一，

则置十五，一百六以上，以一百五减之，即得。”用现代语言说明这个解法就是：

首先找出能被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即是所求。

中国剩余定理的实际应用：

有一个年级的同学,每9人一排多5人,每7人一排多1人, 每5人一排多2人,

问这个年级至少有多少人?

求数学高手详细解答!剩余定理是什么意思?

5 和 9 的公倍数依次是 45、90、135、180、225 ……

这些公倍数中，被7除余1的数是 225

9 和 7 的公倍数依次是 63、126、189、252……

这其中，被5除余2的是 252

5 和 7 的公倍数是 35、70、105、140、……

其中被9除余5的数是 140

把以上 225 252 140 三个数相加，求得

225 + 252 + 140 = 617

5 7 9 三个数的最小公倍数是 5*7*9=315

617-315 = 302

因此 302 就是这个年级至少人数。

===========================

关于剩余定理：

韩信点兵

汉高祖刘邦曾问大将韩信：“你看我能带多少兵？”韩信斜了刘邦一眼说：“你顶多

能带十万兵吧！”汉高祖心中有三分不悦，心想：你竟敢小看我！“那你呢？”韩信

傲气十足地说：“我呀，当然是多多益善啰！”刘邦心中又添了三分不高兴，勉强

说：“将军如此大才，我很佩服。现在，我有一个小小的问题向将军请教，凭将

军的大才，答起来一定不费吹灰之力的。”韩信满不在乎地说：“可以可以。”刘邦

狡黠地一笑，传令叫来一小队士兵隔墙站队，刘邦发令：“每三人站成一排。”队

站好后，小队长进来报告：“最后一排只有二人。”“刘邦又传令：“每五人站成一

排。”小队长报告：“最后一排只有三人。”刘邦再传令：“每七人站成一排。”小队

长报告：“最后一排只有二人。”刘邦转脸问韩信：“敢问将军，这队士兵有多少人？”

韩信脱口而出：“二十三人。”刘邦大惊，心中的不快已增至十分，心想：“此人本

事太大，我得想法找个岔子把他杀掉，免生后患。”一面则佯装笑脸夸了几句，

并问：“你是怎样算的？”韩信说：“臣幼得黄石公传授《孙子算经》，这孙子乃鬼

谷子的弟子，算经中载有此题之算法，口诀是：

三人同行七十稀，

五树梅花开一枝，

七子团圆正月半，

除百零五便得知。”

刘邦出的这道题，可用现代语言这样表述：

“一个正整数，被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，求该数。

（照上题的解法应为：56+24+21+1*168=269）