請問如何解聯立同餘式?

只能談談最簡單的情況﹐因為若果全講會過字數。


Theorem 4.4.1 (Chinese Remainder Theorem) 給定一組 m1,..., mr
圖片參考：http://math.ntnu.edu.tw/~li/ent-html/img16.gif
皆可找到一整數 c 使得

c
圖片參考：http://math.ntnu.edu.tw/~li/ent-html/img28.gif
{1,..., r}.




証 明. 為了方便, 我們令 M = m1 ... mr 且對任意 i
圖片參考：http://math.ntnu.edu.tw/~li/ent-html/img17.gif
{1,..., r}, 令 Mi = M /mi.
要注意這裡 Mj 和 mi 有以下的關係: (1) 若 i
圖片參考：http://math.ntnu.edu.tw/~li/ent-html/img21.gif
1, 依假設 gcd(m1, mi) = 1, 故 p| m1 且 p| mi 和 m1, mi 互質相矛盾, 故得證 gcd(M1, m1) = 1.
接下來我們想要找到一組 t1,..., tr
圖片參考：http://math.ntnu.edu.tw/~li/ent-html/img17.gif
{1,..., r},

t = c1M1t1 + ... + crMrtr

皆滿足 t
圖片參考：http://math.ntnu.edu.tw/~li/ent-html/img19.gif


要注意! 當這些 mi 不是兩兩互質時, 給定任意的 c1,..., cr 不見得可找到一個整數 c 使得 c
圖片參考：http://math.ntnu.edu.tw/~li/ent-html/img2.gif
2(mod 6), 則 c 為 6k + 2 之形式, 必為偶數. 因此當然不可能找到一整數是奇數又是偶數.
一般來說我們可以將中國剩餘定理看成是解如


圖片參考：http://math.ntnu.edu.tw/~li/ent-html/img90.gif


這樣的聯立方程式. 一般來說聯立方程式是要找到一個共同解同時符合這 r 個式子感覺起來較難. 而在 Theorem 4.4.1 的證明中, 大家可以看出參數 t1,...tr 的設定, 就是要把這 r 個聯立的式子化成 r 個獨立的式子個別解出 ti 來, 自然就變簡單了. 我們來看看以下的例子.

Example 4.4.2 給定 m1 = 3, m2 = 4, m3 = 5 以及 c1 = 2, c2 = 1, c3 = 3 我們希望找到一整數 c 使得 c
圖片參考：http://math.ntnu.edu.tw/~li/ent-html/img17.gif
{1, 2, 3}. 也就是說找到 c 同時滿足



圖片參考：http://math.ntnu.edu.tw/~li/ent-html/img92.gif


依照 Theorem 4.4.1 的符號訂法我們有 M1 = 20, M2 = 15 以及 M3 = 12. 首先我們找到 e1
圖片參考：http://math.ntnu.edu.tw/~li/ent-html/img2.gif
3(mod 5).