技巧丨中国剩余定理

大家应该都听说过韩信点兵的故事：韩信带1500名兵士打仗，战死四百多人，站3人一排，多出2人;站5人一排，多出4人;站7人一排，多出6人。韩信很快说出了人数。在《孙子算经》中也有一道算术题：“今有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何?”实际上考题中也有这种题目：一个大于10的数，除以3余1，除以5余2，问满足条件的最小自然数是多少。我们可以利用中国剩余定理解决这类题目。

1.基本模型

一个数除以a余x，除以b余y，除以c余z，求满足该条件的最小数。

2.特殊模型

(1)余同加余

如果两个或多个除式的被除数相同，余数相同，那么这个被除数等于两个或多个除数的公倍数加上余数。如x÷4余1，x÷5余1，则x=20n+1(20是4和5的最小公倍数)。

(2)和同加和

如果两个或多个除式的被除数相同，除数和余数的和相同，那么这个被除数等于两个或多个除数的公倍数加上除数和余数的和。如如x÷4余2，x÷5余1，则x=20n+6(20是4和5的最小公倍数)。

(3)差同减差

如果两个或多个除式的被除数相同，除数和余数的差相同，那么这个被除数等于两个或多个除数的公倍数减去除数和余数的差。如如x÷4余2，x÷5余3，则x=20n-2(20是4和5的最小公倍数)。

(4)其他情况：逐步满足

先满足一个条件，再满足另一个条件，直到所有条件都满足。

例如：一个大于10的数，除以3余1，除以5余2，问满足条件的最小自然数是多少?

先从小到大找到满足除以5余2的数：2、7、12、17，……然后从中发现满足除以3余1的最小的数是7。所以7就是满足所有条件的最小的数，那么满足所有条件的数可以表示为15n+7。问题所求满足条件的最小自然数是15×1+7=22。

我们再来看文章开头提到的“韩信点兵”的问题。

【例】韩信带1500名兵士打仗，战死四百多人，站3人一排，多出2人;站5人一排，多出4人;站7人一排，多出6人。还剩下多少名士兵?

【中公解析】题干要求满足被除数相同，除数和余数的差相同，那么士兵人数等于105n-1。1500名兵士打仗，战死四百多人，说明还剩下1000~1100人，符合条件的只有105×10-1=1049人。