ARTICLE · 1117687
韩信点兵-中国剩余定理(含习题可打印)!
韩信点兵-中国剩余定理(含习题可打印)!剩余定理是中国古代数学史上一个非常经典的问题，原文为：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？ 翻译成吧白话文就是 一个数，除以3余2，除以5余3，除以7余2。它最小是多少? 解法一：枚举法 把分别满足这三个条件的数从小到大在数轴上标注出来，第一个相同的数就是同时满足所有条件最小的数。如图所示 
枚举法虽然简单，但是如果数字比较大比较复杂效率就会比较低了。 解法二：中国剩余定理，古人也称之为韩信点兵 定理详细推理 来看看3、5、7这三个除数它们两两互为质数，我们一个数一个数的拆解。要保证能够同时满足三个条件，我们需要构造互不干扰的余数叠加，每个除数构造一个专属的“基数”，让每个基数只影响对应除数的余数，完全不干扰其他除数的余数，最后把三个数的贡献加起来，就能同时满足所有余数要求。 怎么样构造呢，这里有一个非常巧妙的方法。 除数：3 5 7 余数：2 3 2 基数：70 21 15 我们把除数3的基数设为5和7的公倍数，同时除以3余1的数，为了不把计算量扩大，当然要选用同时满足这两个条件的最小数哈，这里是70。 为什么要用5和7的公倍数呢，它除以5除以7都余0，叠加上去不影响5和7的余数 为什么又要满足除以3余1呢，因为除以3余1的话，我们再让他乘以余数2，就刚好又保证了当前除数3的余数不变。 两者同时满足既能保证当前除数的余数不变，又不干扰另外两个数的余数，完美的同时满足题目三个条件。 相关练习 
这就是剩余定理的相关内容，理解了它的构造原理之后很简单，以后答题直接套用公式就行啦！
中国剩余定理是数论中求解一元线性同余方程组的重要定理，核心结论是：当除数两两互质时，方程组在模所有除数乘积下有唯一解。
经典问题
让基数同时满足2个核心性质
①能被另外两个除数整除（保证加这个数时，另外两个除数的余数不会变）；
②除以当前除数余1（保证乘以余数后，刚好得到需要的余数）。
以第一个除数3为例：
同理可推导除数5的基数为21，7的基数为15。
定好了基数之后接下来就到了构造的第二步，我们让这三个除数的基数分别乘以他们的余数，并相加
70×2+21×3+15×2
再来仔细看这个算式
70×2满足第一个条件“除以3余2”，同时它是5和7的公倍数，对于除数5和7来说，加上它不影响各自的余数。
21×3满足第二个条件“除以5余3”，同时它是3和7的公倍数，对于除数3和7来说，加上它不影响各自的余数。
15×2满足第三个条件“除以7余2”，同时他是3和5的公倍数，对于除数3和5来说，加上它不影响各自的余数。
她们三项相加完美的同时满足了题目的三个条件。
然而，通过求两两的公倍数然后又乘以余数之后得到的是满足条件了，但不一定就是最小的了，这里我就还得再构造一个数，三个除数的公倍数。
3×5×7=105
然后用70×2+21×3+15×2减去这个公倍数，因为70×2+21×3+15×2已经满足所有的余数条件了，因此减去3个除数的公倍数余数不变，也有可能是若干个公倍数，具体根据数字的大小来。
在这里70×2+21×3+15×2=233
233-2×105=23
答：它最小是23。
公式推广
一个数，除以3余a，除以5余b，除以7余c。它最小是多少?
公式：70a+21b+15c-105n
n取到结果变成最小的正数为止。
更生动的推理过程请看视频👇
关注
重播 分享 赞