中國剩餘定理問題的解題技巧

【問題】有１個數，除以７餘２．除以８餘４，除以９餘３，這個數至少是多少？

這種問題稱爲“中國剩餘定理”問題。

我一般用兩種方法解決這類問題。

第一種是逐步滿足法，方法麻煩一點，但適合所有這類題目。

第二種是最小共倍法，方法簡單，但只適合特殊類型的題目。

還有“中國剩餘定理”的方法，但它不完善且解法較爲複雜，普及應用有一定難度，還不穩定。所以一般不用。

下面分別介紹一下常用的兩種方法。

通用的方法：逐步滿足法

【問題】一個數，除以5餘1，除以3餘2。問這個數最小是多少？

把除以5餘1的數從小到大排列：1，6，11，16，21，26，……

然後從小到大找除以3餘2的，發現最小的是11。

所以11就是所求的.數。

先滿足一個條件，再滿足另一個條件，所以稱之爲“逐步滿足法”。

好多數學題目都可以用逐步滿足的思想解決。

特殊的方法：最小公倍法

情況一

【問題】一個數除以5餘1，除以3也餘1。問這個數最小是多少？（1除外）

除以5餘1：說明這個數減去1後是5的倍數。

除以3餘1：說明這個數減去1後也是3的倍數。

所以，這個數減去1後是3和5的公倍數。要求最小，所以這個數減去1後就是3和5的最小公倍數。即這個數減去1後是15，所以這個數是15＋1=16。

情況二

【問題】一個數除以5餘4，除以3餘2。問這個數最小是多少？

這種情況也可以用特殊法。

數除以5餘4，說明這個數加上1後是5的倍數。

數除以3餘2，說明這個數加上1後也是3的倍數。

所以，這個數加上1後是3和5的公倍數。要求最小，所以這個數加上1後就是3和5的最小公倍數。即這個數加上1後是15，所以這個數是15－1=14。

多個數的，比如3個數的，有時候其中兩個可以用特殊法，那就先用特殊法，用特殊法求出滿足兩個條件的數後再用通用的方法求滿足最後一個條件的數。

所以有時候特殊法和通用法混合使用。在使用的過程中如果能靈活運用餘數問題的技巧，會非常有利於解題。

我們接下來分析最開始的那個問題。

【問題】有１個數，除以７餘２．除以８餘４，除以９餘３，這個數至少是多少？

這道題目不能用特殊法，我們用通用法，解題過程中注意餘數知識的運用。

除以７餘２的數可以寫成7n＋2。

7n＋2這樣的數除以8餘4，由於2除以8餘2，所以要求7n除以8餘2。（餘數知識）

7n除以8餘2，7除以8餘7，要求n除以8餘6（餘數知識），則n最小取6。

所以滿足“除以７餘２，除以8餘4”的最小的數是7×6＋2=44。

所有滿足“除以７餘２，除以8餘4”的數都可以寫成44＋56×m。（想想爲什麼？）

要求44＋56×m除以９餘３，由於44除以9餘8，所以要求56×m除以9餘4。（餘數知識）

56×m除以9餘4，由於56除以9餘2，所以要求m除以9餘2（餘數知識），則m最小取2。

所以滿足“除以７餘２，除以8餘4，除以9餘3”的最小的數是44＋56×2=156。