中國剩餘定理

習題預習

1. 小華有一筆財產，拿去存到三家銀行中，第一家存了1000元，利率為2%，第二家存了2000元，利率為3%，第三家存了3000元，利率為4%。請問一年後，小華可以拿到多少利息？
2. 現在有一個數字，它除以4的餘數是1，除以5的餘數是2，除以7的餘數是3。請問這個數字是多少？
3. 某國的貨幣包括1元、2元、5元、10元四種硬幣，現在有一個人有151元，但只有20個硬幣，請問這個人有多少張1元硬幣、2元硬幣、5元硬幣和10元硬幣各幾張？
4. 某年的萬聖節是星期四，當時離聖誕節還有59天，也就是說聖誕節是星期幾？
5. 小美有12個企鵝，她要把它們分成三隊，每隊分別有2、3、7隻企鵝，請問小美一共有多少種方案？

說明知識

中國剩餘定理（Chinese Remainder Theorem）是一種數學定理，它提供了一種有效的方法，用於解決同餘方程組（congruence system）。同餘方程組是一種由多個同餘方程所構成的系統，而同餘方程則是說，兩個數之間的差值可以被某個整數整除。例如，x ≡ 1 (mod 3)，x ≡ 2 (mod 5)，就是一個同餘方程組。

中國剩餘定理的核心思想是，如果已知一些同餘方程的解，則可以通過這些解來推導出整個同餘方程組的解。具體而言，該定理表示，給定一個同餘方程組，假設方程間兩兩互質（gcd(a, b) = 1），且對於每一個方程，已知一個解，那麼可以求出該同餘方程組的唯一解。

我們用一個例子來說明中國剩餘定理。假設我們要解決一個同餘方程組：

x ≡ 2 (mod 3)
x ≡ 3 (mod 5)
x ≡ 2 (mod 7)

通過中國剩餘定理，我們可以分別解決每個方程，然後通過合併這些子解得到最終解。先看第一個方程，可以列出一個整數k，使得x = 3k + 2。這樣的k可以是0、1、2… 。將這個表達式代入第二個方程，得到：3k + 2 ≡ 3 (mod 5)，這意味著k ≡ 4 (mod 5)。將k = 5m + 4代入第一個表達式和第三個表達式中，可以得到：

x = 3k + 2 = 3(5m + 4) + 2 = 15m + 14
x = 2 (mod 7)

因為x ≡ 15m + 14 ≡ 2 (mod 7)，我們可以進一步解出m = 2 (mod 7)。最後，用這兩個解來合併所有同餘方程，得到最終解為x = 97。

總結來說，中國剩餘定理為解決同餘方程組提供了一個通用的方法。然而，該方法只對特定組合的方程組有效，一般而言，方程的求解通常需要配合其他方法使用。

彙總重點

1. Chinese Remainder Theorem: 對於一個正整數m，如果它是兩個正整數a和b（不一定互素）的最小公倍數，那麼可以通過以下方式解決下列同餘方程組：

x ≡ a1 (mod m1)
x ≡ a2 (mod m2)
…
x ≡ an (mod mn)

2. Chinese Remainder Theorem的解是唯一的，且可以通過以下方式構造：

x = a1M1y1 + a2M2y2 + … + anMnyn mod m

其中Mi = m / mi，yi是Mi模mi的乘法逆元。

3. 如果m1，m2，…，mn是互不相同的質數，那麼通過前兩個重點中提到的方法解決同餘方程組的計算很快，因為每個Mi都只有一個質因數。

4. Chinese Remainder Theorem廣泛用於加密和數學上的問題解決，例如RSA加密算法。

知識測驗

1. 一個選手參加了3場競賽，得分分別為15分、35分和50分。如果得分總和被15和35和50整除，求這個選手最高得分是多少？

答案：最高得分為105分。

2. 一個班級有60個學生，他們參加了散步比賽。每個小隊有12個學生。如果每個小隊的排名被2、3、4、5、6、7、8、9、10整除，求至少有多少個小隊得到了第一名？

答案：至少有6組小隊得到了第一名。

3. 一枚火箭有5個發動機，每個發動機的噴氣速度分別是5、7、11、13和17千米/秒。如果火箭的速度與每個發動機的噴氣速度之乘積相加後能夠被3和7同時整除，求這枚火箭的速度是多少千米/秒？

答案：這枚火箭的速度是604千米/秒。

4. 一個遊戲中有7個級別，每個級別需要的經驗值不一樣。假設一位玩家總共贏得了2530點經驗值，求他達到最高的級別需要的經驗值是多少？

答案：最高的級別需要的經驗值是735點。

5. 一個商人需要運送117件貨物到目的地。他有4輛車可用，分別能夠運載25、32、40和45件貨物。如果每輛車運輸的貨物數量之和都相同，求每輛車運輸的貨物數量？

答案：每輛車運輸的貨物數量為30件。