技巧丨中國剩余定理

大家應該都聽說過韓信點兵的故事：韓信帶1500名兵士打仗，戰死四百多人，站3人一排，多出2人;站5人一排，多出4人;站7人一排，多出6人。韓信很快說出了人數。在《孫子算經》中也有一道算術題：“今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何?”實際上考題中也有這種題目：一個大于10的數，除以3余1，除以5余2，問滿足條件的最小自然數是多少。我們可以利用中國剩余定理解決這類題目。

一個數除以a余x，除以b余y，除以c余z，求滿足該條件的最小數。

(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人。