剩余定理

又称为“孙子定理”，是一种求解同余数组的方法。所谓数组，就是指几组数字除以某一个定值余数相同。例如13和23整除5的余数都为3，那么这两个数就是同余的。一般记做：

23≡13（mod 5）

而中国剩余定理所要解决的就是多个同余式组成的同余数组问题。

“有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二。问物几何？”就是这类问题的一个最典型的例子。

我们今天以另外一个例子来解释，中国剩余定理的解题方式。

有1个数，除以7余2．除以8余4，除以9余3，这个数至少是多少？

“剩余定理”的解题思路

我们这里采用简单的分步计算，先合并题目中的2个同余条件，再进行第二次合并。

第一次合并

我们先把要求的那个数记做a，原始的3个条件化简为：

a≡2（mod 7） a≡4（mod 8） a≡3（mod 9）

所以a可以表示为（7n+2）,其中n为正整数。又因为a≡4（mod 8），所以可以知道（7n）除以8余数应当是2。（注：7n+2除以8余4，那么7n除以8余数就一定是2）

我们知道7除以8余7，所以n除以8余数应当为6（乘数之余等于余数之乘）。

于是我们可以知道n最小为6，此时满足题意的数为6x7+2=44。

第二次合并

综合前两个条件，我们可以知道，44并不满足第三个条件。所以我们仍需进一步合并第三个条件。

我们知道7,8互质，所以其做小公倍数为56。所以前两个条件可以合并为：

a≡44（mod 56）

我们继续重复刚才的运算步骤，将所求数记为（56t+44），我们拆解为（54t+36+2t+8）。

因为次数除以9余3，所以可以知道（2t+8）除以9也余3。

所以2t除以9余数应当是4。自然可以知道t除以9余数应当是2。同样可知2是此时t的最小值。

此时我们所有的数为：2x56+44=156。即为满足3个题目条件的最小数字。

整体剩余定理的解题过程就是不断合并已知条件的过程，通过合并逐步找到解题的关键点：乘数之余等于余数之乘。