小升初奥数数论中国剩余定理要点及解题技巧

 一、中国剩余定理的由来

韩信点兵又称为中国剩余定理，相传汉高祖刘邦问大将军韩信统御兵士多少，韩信答说，每3人一列余1人、5人一列余2人、7人一列余4人、13人一列余6人……。

刘邦茫然而不知其数。

我们先考虑下列的问题：假设兵不满一万，每5人一列、9人一列、13人一列、17人一列都剩3人，则兵有多少?

首先我们先求5、9、13、17之最小公倍数9945(注：因为5、9、13、17为两两互质的整数，故其最小公倍数为这些数的积)，然后再加3，得9948(人)。

中国有一本数学古书「孙子算经」也有类似的问题：

「今有物，不知其数，三三数之，剩二，五五数之，剩三，七七数之，剩二，问物几何?」答曰：「二十三」术曰：「三三数之剩二，置一百四十，五五数之剩三，置六十三，七七数之剩二，置三十，并之，得二百三十三，以二百一十减之，即得。凡三三数之剩一，则置七十，五五数之剩一，则置二十一，七七数之剩一，则置十五，即得。」

孙子算经的作者及确实着作年代均不可考，不过根据考证，着作年代不会在晋朝之后，以这个考证来说上面这种问题的解法，中国人发现得比西方早，所以这个问题的推广及其解法，被称为中国剩余定理。

 二、中国剩余定理在数论中的地位

 中国剩余定理是数论四大定理(威尔逊定理、欧拉定理、费马小定理、中国剩余定理)之一，在初等数论中有着非常广泛和重要的应用。

 三、中国剩余定理问题的解题技巧

【问题】有1个数，除以7余2.除以8余4，除以9余3，这个数至少是多少?

这种问题称为"中国剩余定理"问题。

我一般用两种方法解决这类问题。

第一种是逐步满足法，方法麻烦一点，但适合所有这类题目。

第二种是最小公倍法，方法简单，但只适合特殊类型的题目。

还有"中国剩余定理"的方法，但它不完善且解法较为复杂，普及应用有一定难度，还不稳定。所以一般不用。

下面分别介绍一下常用的两种方法。

通用的方法：逐步满足法

【问题】一个数，除以5余1，除以3余2。问这个数最小是多少?

把除以5余1的数从小到大排列：1，6，11，16，21，26，……

然后从小到大找除以3余2的，发现最小的是11.

所以11就是所求的数。

先满足一个条件，再满足另一个条件，所以称之为"逐步满足法"。

好多数学题目都可以用逐步满足的思想解决。

特殊的方法：最小公倍法

情况一

【问题】一个数除以5余1，除以3也余1。问这个数最小是多少?(1除外)

除以5余1：说明这个数减去1后是5的倍数。

除以3余1：说明这个数减去1后也是3的倍数。

所以，这个数减去1后是3和5的公倍数。要求最小，所以这个数减去1后就是3和5的最小公倍数。即这个数减去1后是15，所以这个数是15+1=16.

情况二

【问题】一个数除以5余4，除以3余2。问这个数最小是多少?

这种情况也可以用特殊法。

数除以5余4，说明这个数加上1后是5的倍数。

数除以3余2，说明这个数加上1后也是3的倍数。

所以，这个数加上1后是3和5的公倍数。要求最小，所以这个数加上1后就是3和5的最小公倍数。即这个数加上1后是15，所以这个数是15-1=14.

多个数的，比如3个数的，有时候其中两个可以用特殊法，那就先用特殊法，用特殊法求出满足两个条件的数后再用通用的方法求满足最后一个条件的数。

所以有时候特殊法和通用法混合使用。在使用的过程中如果能灵活运用余数问题的技巧，会非常有利于解题。

我们接下来分析最开始的那个问题。

【问题】有1个数，除以7余2.除以8余4，除以9余3，这个数至少是多少?

这道题目不能用特殊法，我们用通用法，解题过程中注意余数知识的运用。

除以7余2的数可以写成7n+2。

7n+2这样的数除以8余4，由于2除以8余2，所以要求7n除以8余2。(余数知识)

7n除以8余2，7除以8余7，要求n除以8余6(余数知识)，则n最小取6。

所以满足"除以7余2，除以8余4"的最小的数是7×6+2=44.

所有满足"除以7余2，除以8余4"的数都可以写成44+56×m。(想想为什么?)

要求44+56×m除以9余3，由于44除以9余8，所以要求56×m除以9余4。(余数知识)

56×m除以9余4，由于56除以9余2，所以要求m除以9余2(余数知识)，则m最小取2。

所以满足"除以7余2，除以8余4，除以9余3"的最小的数是44+56×2=156.

四、运用中国剩余定理解题注意事项

如果整数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.