剩余定理快速解法(剩余定理的典故)

剩余定理（物不知数）

物不知数出自《孙子算经》：“今有物不知数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？”

意思是说一些物品不知道具体数量，三个三个数剩二个，五个五个数剩三个，七个七个求剩二个，问这些物品一共多少个？

这是个倍数有关的题目，首先可以用列举法把除以3余2的数列举出来：2,5,8,11,14,17,20,23,26,29,32…；除以5余3的数：3,8,13,18,23,28,33…；除以7余2的数：2,9,16,23,30,37…；然后找出符合三个条件的共有的数：23,128…其中23是符合条件的最小的数。

学习了公倍数以后就可以少写一步，因为三个三个数余2，七个七个数也余2,就是说这个数是3和7的公倍数加2，这样的数有：2,23,44,65,86,107,128…；然后再找出符合除以5余3的数：23，128…这个数最小是23。

古人的算法更为巧妙：找出3和5的公倍数中除以7余1的最小数：15；3和7的公倍数中除以5余1的最小数：21；5和7的公倍数中除以3余1的最小数：70。然后将这几个数分别乘所要求的数被7、5、3除所得的余数，然后把乘得的积相加：15×2+21×3+70×2=233，再用233除以3、5、7的最小公倍数105,所得的余数就是符合条件的最小数233÷105=2……23；下一个符合条件的数就是23+105=128；如此加下去即可。这种算法被称为“中国剩余定理”。

然而有些余数相同或者差数相同的问题不需要这样复杂的算法，只需要用公倍数加上相同的余数或者减去相同的差数即可求出答案。

例1：有一批树苗，9棵一捆多7棵，10棵一捆多8棵，12棵一捆多10棵，问这批树苗最少多少棵？

读上面的题目不难发现，只要再增加2棵树苗，就能全部捆完没有剩余，所以树苗的棵数是9、10、12的最小公倍数减去2,即178棵。

每天分享一点数学知识，每天都有新的收获[比心]

温馨提示：通过以上关于剩余定理（物不知数）内容介绍后，相信大家有新的了解，更希望可以对你有所帮助。