Chinese Remainder Theorem

假設 m = p₁^{n₁ ...} p_r^n_r 其中 p_i 為相異質數且 f (x) 是一個整係數多項式. Proposition 4.2.3 告訴我們若對所有 i $\in$ {1,..., r}, f (x) $\equiv$ 0(mod p_i^n_i) 皆有解且有共同解, 則 f (x) $\equiv$ 0(mod m) 便有解. 如何找到共同解呢? 中國剩餘定理 (Chinese Remainder Theorem) 告訴我們只要個別地將 f (x) $\equiv$ 0(mod p_i^n_i) 的解找到, 就可得到共同解.

Theorem 4.4.1 (Chinese Remainder Theorem)   給定一組 m₁,..., m_r $\in$ $\mathbb {N}$ 其中這些 m_i 皆兩兩互質 (即當 i$\ne$j 時, gcd(m_i, m_j) = 1). 則對任意的一組 c₁,..., c_r $\in$ $\mathbb {Z}$ 皆可找到一整數 c 使得

c $$\equiv$$ c_i(mod m_i), $$\forall$$ i $$\in$$ {1,..., r}.

証 明. 為了方便, 我們令 M = m₁ ^... m_r 且對任意 i $\in$ {1,..., r}, 令 M_i = M/m_i.

要注意這裡 M_j 和 m_i 有以下的關係: (1) 若 i$\ne$j, 則 m_i| M_j. (2) gcd(M_i, m_i) = 1. 這裡 (1) 由 M_j 的定義相信大家很容易得知, 至於 (2) 不失一般性 (變換一下 m_i 的順序), 我們僅需證明 gcd(M₁, m₁) = 1. 假設 M₁, m₁ 不互質, 即存在一質數 p 使得 p| M₁ 且 p| m₁. 然而依定義 M₁ = m₂ ^... m_r, 故由 Corollary 1.4.3 知存在 i $\in$ {2,..., r} 使得 p| m_i. 但是 i$\ne$1, 依假設 gcd(m₁, m_i) = 1, 故 p| m₁ 且 p| m_i 和 m₁, m_i 互質相矛盾, 故得證 gcd(M₁, m₁) = 1.

接下來我們想要找到一組 t₁,..., t_r $\in$ $\mathbb {Z}$ 使得對所有的 i $\in$ {1,..., r},

t = c₁M₁t₁ + ^... + c_rM_rt_r

皆滿足 t $\equiv$ c_i(mod m_i). 然而對任何的一組 t₁,..., t_r $\in$ $\mathbb {Z}$ 以及一給定的 i $\in$ {1,..., r}, 由 (1) (即 m_i| M_j for i$\ne$j) 我們皆有 t $\equiv$ c_iM_it_i(mod m_i). 故我們僅需找到 t_i $\in$ $\mathbb {Z}$ 使得 c_iM_it_i $\equiv$ c_i(mod m_i) 即可. 然而由 (2) (即 gcd(M_i, m_i) = 1) 以及 Proposition 3.2.5 知存在 e_i $\in$ $\mathbb {Z}$ 使得 M_ie_i $\equiv$ 1(mod m_i), 故若令 t_i = e_i, 則得 t $\equiv$ c_iM_ie_i $\equiv$ c_i(mod m_i). 因此對所有 i $\in$ {1,..., r}, 我們先找到 e_i 使得 M_ie_i $\equiv$ 1(mod m_i), 再令 c = c₁M₁e₁ + ^... + c_rM_re_r, 則可得 c $\equiv$ c_i(mod m_i), $\forall$ i $\in$ {1,..., r}. $\qedsymbol$

要注意! 當這些 m_i 不是兩兩互質時, 給定任意的 c₁,..., c_r 不見得可找到一個整數 c 使得 c $\equiv$ c_i(mod m_i) 對所有的 i $\in$ {1,..., r} 都成立. 例如當 m₁ = 4, m₂ = 6 時若考慮 c₁ = 1, c₂ = 2, 則不可能找到一整數 c 同時滿足 c $\equiv$ 1(mod 4) 且 c $\equiv$ 2(mod 6). 這是因為若 c $\equiv$ 1(mod 4) 表示 c 為 4k + 1 的形式, 故必為奇數. 然而若 c $\equiv$ 2(mod 6), 則 c 為 6k + 2 之形式, 必為偶數. 因此當然不可能找到一整數是奇數又是偶數.

一般來說我們可以將中國剩餘定理看成是解如

$$\left\{\vphantom{ \begin{array}{ll} x\equiv c_1 & \hbox{$\pmod{m... ...uad\vdots$} \\ x\equiv c_r & \hbox{$\pmod{m_r}$} \\ \end{array}%% }\right.$$$$\begin{array}{ll} x\equiv c_1 & \hbox{$\pmod{m_1}$} \\ x\equi... ... \hbox{$\qquad\vdots$} \\ x\equiv c_r & \hbox{$\pmod{m_r}$} \\ \end{array}$$

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

Example 4.4.2   給定 m₁ = 3, m₂ = 4, m₃ = 5 以及 c₁ = 2, c₂ = 1, c₃ = 3 我們希望找到一整數 c 使得 c $\equiv$ c_i(mod m_i), $\forall$ i $\in$ {1, 2, 3}. 也就是說找到 c 同時滿足

$$\left\{\vphantom{ \begin{array}{ll} c\equiv 2 & \hbox{(mod $3$)}... ...\hbox{(mod $4$)} \\ c\equiv 3 & \hbox{(mod $5$)} \\ \end{array}%% }\right.$$$$\begin{array}{ll} c\equiv 2 & \hbox{(mod $3$)} \\ c\equiv 1 & \hbox{(mod $4$)} \\ c\equiv 3 & \hbox{(mod $5$)} \\ \end{array}$$

依照 Theorem 4.4.1 的符號訂法我們有 M₁ = 20, M₂ = 15 以及 M₃ = 12. 首先我們找到 e₁ $\in$ $\mathbb {Z}$ 使得 M₁e₁ $\equiv$ 1(mod m₁), 即 20e₁ $\equiv$ 1(mod 3), 也就是說滿足 2e₁ $\equiv$ 1(mod 3). 由此找到 e₁ = 2. 同理我們要找到 e₂, e₃ 分別滿足 15e₂ $\equiv$ 1(mod 4) (即 3e₂ $\equiv$ 1(mod 4)) 以及 12e₃ $\equiv$ 1(mod 5) (即 2e₃ $\equiv$ 1(mod 5)). 可得 e₂ = 3 和 e₃ = 3 分別滿足上式. 故令 c = 2×20×2 + 1×15×3 + 3×12×3 = 233 滿足 233 $\equiv$ 2(mod 3), 233 $\equiv$ 1(mod 4) 以及 233 $\equiv$ 3(mod 5).

前面提過, 給定 m $\in$ $\mathbb {N}$, 假設 m = p₁^{n₁ ...} p_r^n_r, 其中 p_i 為相異質數. 如果 f (x) 是一個整係數多項式, 要解 f (x) $\equiv$ 0(mod m), 我們可以先對每個 p_i 考慮解 f (x) $\equiv$ 0(mod p_i^n_i). 如果有一個 p_i 發生 f (x) $\equiv$ 0(mod p_i^n_i) 無解的情況, 那麼依 Proposition 4.2.3 知 f (x) $\equiv$ 0(mod m) 無解. 如果每一個 p_i 皆會使得 f (x) $\equiv$ 0(mod p_i^n_i), 則依 Proposition 4.2.3 知, 需解聯立方程式

$$\left\{\vphantom{ \begin{array}{ll} f(x)\equiv 0 & \hbox{$\pmod{... ...ts$} \\ f(x)\equiv 0 & \hbox{$\pmod{p_r^{n_r}}$} \\ \end{array}%% }\right.$$$$\begin{array}{ll} f(x)\equiv 0 & \hbox{$\pmod{p_1^{n_1}}$} \\ ... ...$\qquad\vdots$} \\ f(x)\equiv 0 & \hbox{$\pmod{p_r^{n_r}}$} \\ \end{array}$$

有一共同解才可得 f (x) $\equiv$ 0(mod m) 的解. 解聯立方程是困難的, 而中國剩餘定理告訴我們可以不必考慮解聯立式子, 先個別將解求出便可得到共同的解.

Corollary 4.4.3   假設 m = p₁^{n₁ ...} p_r^n_r, 其中這些 p_i 為相異質數且 f (x) 為一整係數多項式. 則對任意 i $\in$ {1,..., r}, f (x) $\equiv$ 0(mod p_i^n_i) 皆有解若且唯若 f (x) $\equiv$ 0(mod m) 有解.

証 明. 依 Proposition 4.2.3 知, 如果 f (x) $\equiv$ 0(mod m) 有解, 則對任意 i $\in$ {1,..., r}, f (x) $\equiv$ 0(mod p_i^n_i) 皆有解.

現假設對任意 i $\in$ {1,..., r}, f (x) $\equiv$ 0(mod p_i^n_i) 皆有解且 x $\equiv$ c_i(mod p_i^n_i) 為其一解. 由於這些 p_i^n_i 是兩兩互質的故依 Theorem 4.4.1 知, 存在 c $\in$ $\mathbb {Z}$ 滿足對任意 i $\in$ {1,..., r} 皆有 c $\equiv$ c_i(mod p_i^n_i). 也就是說任意 i $\in$ {1,..., r}, x $\equiv$ c(mod p_i^n_i) 為 f (x) $\equiv$ 0(mod p_i^n_i) 之一解. 故再利用 Proposition 4.2.3 得知 x $\equiv$ c(mod m) 為 f (x) $\equiv$ 0(mod m) 之一解. $\qedsymbol$

我們就來看一個這方面的簡單例子. 雖然底下的例子可以直接代數字得到解答, 但是我們只是希望利用此例來講解這裡所用的概念, 所以希望大家了解應著重於如何應用所學的方法而不在於解答為何.

Example 4.4.4   我們來解 x² $\equiv$ 1(mod 15). 依前面結果知我們可以分別考慮 x² $\equiv$ 1(mod 3) 及 x² $\equiv$ 1(mod 5) 的解. 因為 3 和 5 皆為質數, 依 Lemma 3.4.2 知 x $\equiv$ ±1(mod 3) 和 x $\equiv$ ±1(mod 5) 分別為 x² $\equiv$ 1(mod 3) 和 x² $\equiv$ 1(mod 5) 之解. 因此我們要找到以下的四個聯立的 congruence equation:

(1)$$\left\{\vphantom{ \begin{array}{ll} x\equiv 1 & \hbox{$\pmod{3}$} \\ x\equiv 1 & \hbox{$\pmod{5}$} \\ \end{array}%% }\right.$$$$\begin{array}{ll} x\equiv 1 & \hbox{$\pmod{3}$} \\ x\equiv 1 & \hbox{$\pmod{5}$} \\ \end{array}$$, (2)$$\left\{\vphantom{ \begin{array}{ll} x\equiv -1 & \hbox{$\pmod{3}$} \\ x\equiv -1 & \hbox{$\pmod{5}$} \\ \end{array}%% }\right.$$$$\begin{array}{ll} x\equiv -1 & \hbox{$\pmod{3}$} \\ x\equiv -1 & \hbox{$\pmod{5}$} \\ \end{array}$$,

(3)$$\left\{\vphantom{ \begin{array}{ll} x\equiv -1 & \hbox{$\pmod{3}$} \\ x\equiv 1 & \hbox{$\pmod{5}$} \\ \end{array}%% }\right.$$$$\begin{array}{ll} x\equiv -1 & \hbox{$\pmod{3}$} \\ x\equiv 1 & \hbox{$\pmod{5}$} \\ \end{array}$$, (4)$$\left\{\vphantom{ \begin{array}{ll} x\equiv 1 & \hbox{$\pmod{3}$} \\ x\equiv -1 & \hbox{$\pmod{5}$} \\ \end{array}%% }\right.$$$$\begin{array}{ll} x\equiv 1 & \hbox{$\pmod{3}$} \\ x\equiv -1 & \hbox{$\pmod{5}$} \\ \end{array}$$.

(1) 和 (2) 我們很容易看出分別取整數 1 和 -1 就可分別滿足 (1) 和 (2). 而 11 可以滿足 (3), 4 可以滿足 (4). 所以由 Proposition 4.2.3 我們知 x $\equiv$ 1, - 1, 11, 4(mod 15) 都為 x² $\equiv$ 1(mod 15) 的解. 我們找到 x² $\equiv$ 1(mod 15) 在 modulo 15 之下的 4 個解, 並不表示就只有這 4 個解. 不過大家可以自行驗證一下在 modulo 15 之下確實僅有這 4 個解.

在上個例子中我們解出 x² $\equiv$ 1(mod 15) 在 modulo 15 之下的 4 個解但不敢確定是否僅有這 4 解是因為我們不知在利用中國剩餘定理時, 是否還有其他的解. 也就是說 Theorem 4.4.1 只告訴我們解的存在性, 並未告訴我們是否有其他解. 當然我們都知道會有無窮多解, 但是其他的解如何得知呢? 我們再套用一次常用的老方法, 看看兩個解之間的關係為何, 自然就可將所有的解寫下了.

Theorem 4.4.5   給定一組 m₁,..., m_r $\in$ $\mathbb {N}$ 其中這些 m_i 皆兩兩互質. 令 M = m₁ ^... m_r, 則對任意的一組 c₁,..., c_r $\in$ $\mathbb {Z}$ 以下聯立的 congruence equation

$$\left\{\vphantom{ \begin{array}{ll} x\equiv c_1 & \hbox{$\pmod{m... ...uad\vdots$} \\ x\equiv c_r & \hbox{$\pmod{m_r}$} \\ \end{array}%% }\right.$$$$\begin{array}{ll} x\equiv c_1 & \hbox{$\pmod{m_1}$} \\ x\equi... ... \hbox{$\qquad\vdots$} \\ x\equiv c_r & \hbox{$\pmod{m_r}$} \\ \end{array}$$

在 modulo M 之下存在唯一的一個解. 事實上若 c $\in$ $\mathbb {Z}$ 滿足此聯立 congruence equation, 則對任意 c' $\in$ $\mathbb {Z}$ 滿足 c' $\equiv$ c(mod M) 皆會滿足此聯立 congruence equation.

証 明. Theorem 4.4.1 已證得存在性, 我們要證明在 modulo m₁ ^... m_r 之下其解唯一.

假設 c, c' $\in$ $\mathbb {Z}$ 皆滿足以上聯立的 congruence equation. 也就是說對任意 i $\in$ {1,..., r} 我們皆有 c $\equiv$ c_i(mod m_i) 且 c' $\equiv$ c_i(mod m_i). 因此之對任意 i $\in$ {1,..., r} 皆有 m_i| c - c'. 然而這些 m_i 兩兩互質, 故利用 Proposition 1.2.11(2), 我們得 m₁ ^... m_r| c - c', 即 c $\equiv$ c'(mod M). 也就是說在 modulo M 之下其解唯一.

另一方面, 若 c 滿足聯立 congruence equation 且 c' $\in$ $\mathbb {Z}$ 滿足 c' $\equiv$ c(mod M), 則由於對任意 i $\in$ {1,..., r}, m_i| M, 故知 c' $\equiv$ c $\equiv$ c_i(mod m_i). 亦即 c' 滿足此聯立 congruence equation. $\qedsymbol$

例如在 Example 4.4.2 中, 我們知道 x = 233 滿足

$$\left\{\vphantom{ \begin{array}{ll} x\equiv 2 & \hbox{(mod $3$)}... ...\hbox{(mod $4$)} \\ x\equiv 3 & \hbox{(mod $5$)} \\ \end{array}%% }\right.$$$$\begin{array}{ll} x\equiv 2 & \hbox{(mod $3$)} \\ x\equiv 1 & \hbox{(mod $4$)} \\ x\equiv 3 & \hbox{(mod $5$)} \\ \end{array}$$

這一組聯立的 congruence equation, 所以由 Theorem 4.4.5 知任意的整數 c 滿足 c $\equiv$ 233 $\equiv$ 53(mod 60) 都可以滿足這一組聯立 congruence equation. 當然了也僅有滿足 c $\equiv$ 53(mod 60) 的整數會滿足此聯立 congruence equation.

Theorem 4.4.5 比 Theorem 4.4.1 完整. 因為在 Theorem 4.4.1 中我們僅提及解的存在性, 而 Theorem 4.4.5 提及解在 modulo m₁ ^... m_r 之下是存在且唯一的, 而且因而可由一解找到所有的解. 有的書不會將兩定理分開來談, 而直接談論較完整的 Theorem 4.4.5 並稱之為 Chinese remainder theorem. 我們將兩定理分開主要是因為想先強調中國剩餘定理解的存在性及如何找到一解.