中国剩余定理(孙子定理)
巡山小妖精
695次浏览
2021年01月26日 06:12
最佳经验
本文由作者推荐
军训小结-
中国剩余定理（孙子定理）
问题：今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？
简单点说就是，存在一个数
x
，除以
3
余
2
，除以
5
余三，除以
7
余二，然后求这个数。上面
给出了解法。再明白这个解法的原 理之前，需要先知道一下两个定理。
定理
1
：几个数相加，如果存在一个加 数，不能被整数
a
整除，那么它们的和，就不能被整数
a
整除。
< br>定理
2
：两数不能整除，若除数扩大（或缩小）了几倍，而被除数不变，则其商和余数也 同时
扩大（或缩小）相同的倍数（余数必小于除数）。
以上两个定理随便个例子即可证明！
现给出求解该问题的具体步骤：
1
、求出最小公倍数
lcm=3*5*7=105
2
、求各个数所对应的基础数
（
1
）
105÷
3=35
35÷
3=11......2 //
基础数
35
（
2
）
105÷
5=21
21÷
5=4......1
定理
2
把
1扩大
3
倍得到
3
，那么被除数也扩大
3
倍，得到
21*3=63//
基础数
63
3
、
105÷
7=15
15÷
7=2......1
定理
2
把
1
扩大
2
倍得到
2
，那么被除数也扩大
2
倍，得到
15*2=30//
基础数
30
把得到的基础数加和（注意：基础数不一定就是正数）
35+63+30=128
4
、减去最小公倍数
lcm
（在比最小公倍数大的情况下）
x=128-105=23
那么满足题意得最小的数就是
23
了。 一共有四个步骤。下面详细解释每一步的原因。
（
1
）最小公倍数就不解释 了，跳过（记住，这里讨论的都是两两互质的情况）
（
2
）观察求每个数对 应的基础数时候的步骤，比如第一个。
105÷
3=35
。显然这个
35是除
了当前这个数不能整除以外都能够被其他数整除，就是其他数的最小公倍数。相当于找到了最< br>小的起始值，用它去除以
3
发现正好余
2
。那么这个基础数就是
35
。记住
35
的特征，可以整
除其他数但是不能被
3
整 除，并且余数是
2
。体现的还不够明显，再看下
5
对应的基础数。
2 1
是其他数的最小公倍数，但是不能被
5
整除，用
21
除以
5
得到的余数是
1
，而要求的数除以
5
应该是余
1
的。所以余数被扩大，就得到了相应的基础数
63
。记住这个数的特征，可以被其
他数 整除但是被
5
除应该余三。同理，我们得到了第三个基础数
23
，那么他的特 征就是：可
以被其他数整除，但是不能被
7
整除，并且余数为
2
。< br>
（
3
）第三步基础数加和，为什么要这样做呢？利用就是上面提到的定理1
。
35+63+30=128
。对于
3
来说，可以 把
63+30
的和看作一个整体，应该他们都可以被
3
整除。看着上面写出的 三个数的特征，运用定理
1
来说，就是在
35
的基础上加上一个可以被
3
整除的倍数，那么得到的结果依然还是满足原先的性质的，就是
128
除以同样还 是余
2
的。
同理，对于
5
还说，这个数被除之后会剩余
3< br>；对于
7
来说，被除之后剩余
2
。所以说，我们
当前得到的这 个数是满足题目要求的一个数。但是这个数是不是最小的，那就不一定了。
（
4）应该不能确定是不是最小的数，这个时候就要用到他们的最小公倍数了。最小公倍数顾名
思义，一 定是一个同时被几个数整除的最小的一个数，所以减去它剩余下来的余数还是符合题