兩個常用的方法

我們介紹兩種常用的方法將一個給定的 congruence equation 化成簡單一點的形式, 再來求解.

在這一節中我們都假設 f (x) = a_nxⁿ + ^... + a₁x + a₀, 其中 a_i $\in$ $\mathbb {Z}$, 而 m $\in$ $\mathbb {N}$ 是一給定的正整數. 我們要談論 f (x) $\equiv$ 0(mod m) 這一個 congruence equation.

第一種情形是這樣的: 如果 d 是 a_n,..., a₁, a₀ 以及 m 的正公因數. 也就是說我們可以將 a_i 及 m 寫成 a_n = a_n'd,..., a₁ = a₁'d, a₀ = a₀'d 以及 m = m'd, 其中這些 a_i' $\in$ $\mathbb {Z}$ 且 m' $\in$ $\mathbb {N}$. 令 g(x) = a_n'xⁿ + ^... a₁'x + a₀', 我們來探討 f (x) $\equiv$ 0(mod m) 及 g(x) $\equiv$ 0(mod m') 這兩個 congruence equation 之間的關係.

Proposition 4.2.1   給定 m $\in$ $\mathbb {N}$ 及 f (x) = a_nxⁿ + ^... + a₁x + a₀, 其中 a_i $\in$ $\mathbb {Z}$. 假設 d 是 a_n,..., a₁, a₀ 及 m 的正公因數且 a_n = a_n'd,..., a₁ = a₁'d, a₀ = a₀'d 以及 m = m'd. 令 g(x) = a_n'xⁿ + ^... + a₁'x + a₀'.

若 x $\equiv$ c(mod m') 是 g(x) $\equiv$ 0(mod m') 的一個解, 則對任意 t $\in$ $\mathbb {Z}$, x $\equiv$ c + m't(mod m) 為 f (x) $\equiv$ 0(mod m) 的解. 另一方面, 若 g(x) $\equiv$ 0(mod m') 無解, 則 f (x) $\equiv$ 0(mod m) 無解.

証 明. x $\equiv$ c(mod m') 為 g(x) $\equiv$ 0(mod m') 的一個解, 表示 m'| a_n'cⁿ + ^... + a₁'c + a₀'. 因此可得 m'd| a_n'dcⁿ + ^... + a₁'dc + a₀'d, 也就是說 m| a_ncⁿ + ^... a₁c + a₀. 因此 x $\equiv$ c(mod m) 是 f (x) $\equiv$ 0(mod m) 的一個解.

對任意 t $\in$ $\mathbb {Z}$ 以及 r $\in$ $\mathbb {N}$, 由於 (c + m't)^r = c^r + rc^{r - 1}m't + ^... + rc(m't)^{r - 1} + (m't)^r, 我們可以將 (c + m't)^r 寫成 c^r + m'$\lambda_{r}^{}$, 其中 $\lambda_{r}^{}$ $\in$ $\mathbb {Z}$. 因此

f (c + m't) = a_n(c + m't)ⁿ + ^... + a₁(c + m't) + a₀ = f (c) + a_nm'$$\lambda_{n}^{}$$ + ^... + a₁m'$$\lambda_{1}^{}$$.

因為 d| a_i, 故知 dm'| a_im', 也就是說 a_im' $\equiv$ 0(mod m). 所以我們得

f (c + m't) $$\equiv$$ f (c) $$\equiv$$ 0(mod m),

也就是說對任意 t $\in$ $\mathbb {Z}$, x $\equiv$ c + m't 也會是 f (x) $\equiv$ 0(mod m) 的一個解.

另一方面, 若 x $\equiv$ c(mod m) 為 f (x) $\equiv$ 0(mod m) 的一個解, 即 m| a_ncⁿ + ^... + a₁c + a₀, 則 m'| a_n'cⁿ + ^... + a₁'c + a₀'. 也就是說 x $\equiv$ c(mod m') 為 g(x) $\equiv$ 0(mod m') 的一個解. 因此若 g(x) $\equiv$ 0(mod m') 無解, 則 f (x) $\equiv$ 0(mod m) 亦無解. $\qedsymbol$

Proposition 4.2.1 告訴我們, 如果 x $\equiv$ c(mod m') 是 g(x) $\equiv$ 0(mod m') 的一個解, 則對任意 t $\in$ $\mathbb {Z}$, x $\equiv$ c + m't(mod m) 便會是 f (x) $\equiv$ 0(mod m) 的一個解. 不過這裡由於我們要考慮在 modulo m 的情況, 很多解是重複的. 事實上若 t $\equiv$ t'(mod d), 則由 d| t - t', 可得 dm'| m'(t - t'). 也就是說 c + m't $\equiv$ c + m't'(mod m). 因此我們只要考慮 x $\equiv$ c + m't(mod m) 其中 0$\le$t$\le$d - 1, 就可以了.

Proposition 4.2.1 將一個 modulo m 的 congruence equation 化成一個 modulo 比較小的 m' 的 congruence equation. 這樣一來由於在 modulo m' 之下要考慮的數較少, 應該將原來的問題簡化了. 然而若 a_n,..., a₁, a₀ 和 m 是互質的, 我們仍然可以考慮 modulo 較小的值看看有沒有解. 事實上, 我們有以下之結果.

Lemma 4.2.2   給定 m $\in$ $\mathbb {N}$ 及一整係數多項式 f (x). 若 m'| m 且 f (x) $\equiv$ 0(mod m') 無解, 則 f (x) $\equiv$ 0(mod m) 亦無解.

証 明. 假設 f (x) $\equiv$ 0(mod m) 有解且 x $\equiv$ c(mod m) 為其中一解, 即 m| f (c). 由於 m'| m, 知 m'| f (c), 也就是說 x $\equiv$ c(mod m') 為 f (x) $\equiv$ 0(mod m') 之一解. 此與假設 f (x) $\equiv$ 0(mod m') 無解矛盾, 故得證 f (x) $\equiv$ 0(mod m) 無解. $\qedsymbol$

Lemma 4.2.2 和 Proposition 4.2.1 不同之處在於 Proposition 4.2.1 將原多項式各係數除以公因數後考慮 modulo m' 之解, 而且可利用其解得到原多項式在 modulo m 之解, 而 Lemma 4.2.2 並沒有改變多項式, 且僅知原多項式在 modulo 比較小的 m' 之下無解可推得原多項式在 modulo m 之下無解. 但無從判斷在 modulo m' 之下有解是否可得在 modulo m 之下有解, 而且也無從推得解之形式. 不過若我們多考慮幾個 m 的因數所得的 congruence equations, 確實可以幫我們得知解之情形. 這就是我們要探討的第二種方法.

這一種常用的方法就是先將 m 寫成質因數的分解, 即 m = p₁^{n₁ ...} p_r^n_r, 其中這些 p_i 為相異質數. 接著僅要探討對所有 i = 1,..., r, f (x) $\equiv$ 0(mod p_i^n_i) 之解的情形就可, 因為我們有以下之結果.

Proposition 4.2.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) 無解. 另一方面, 對任意 i $\in$ {1,..., r}, x $\equiv$ c(mod p_i^n_i) 皆為 f (x) $\equiv$ 0(mod p_i^n_i) 的解若且唯若 x $\equiv$ c(mod m) 為 f (x) $\equiv$ 0(mod m) 之ㄧ個解.

証 明. 首先, 由於 p_i^n_i| m, 因此套用 Lemma 4.2.2 知, 若 f (x) $\equiv$ 0(mod p_i^n_i) 無解, 則 f (x) $\equiv$ 0(mod m) 無解.

現假設 x $\equiv$ c(mod m) 為 f (x) $\equiv$ 0(mod m) 的一個解, 也就是說 m| f (c), 由於對任意 i $\in$ {1,..., r} 皆滿足 p_i^n_i| m, 知 p_i^n_i| f (c). 因此知對所有的 i $\in$ {1,..., r}, x $\equiv$ c(mod p_i^n_i) 為 f (x) $\equiv$ 0(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) 的解. 即 p_i^n_i| f (c). 則由於這些 p_i^n_i 是兩兩互質的, 利用 Proposition 1.2.7(2) 知 p₁^{n₁ ...} p_r^n_r| f (c), 亦即 m| f (c). 故得證 x $\equiv$ c(mod m) 為 f (x) $\equiv$ 0(mod m) 的一個解. $\qedsymbol$

Proposition 4.2.3 告訴我們, 若有一個 p_i 使得 f (x) $\equiv$ 0(mod p_i^n_i) 無解, 那麼 f (x) $\equiv$ 0(mod m) 就無解. 但是如果對所有的 p_i, f (x) $\equiv$ 0(mod p_i^n_i) 皆有解, 是否表示 f (x) $\equiv$ 0(mod m) 有解呢? 答案是肯定的. 這是因為雖然對任意的 p_i 解得的解未必相同, 但利用以後會探討的中國剩餘定理可找到一整數同時滿足 modulo p_i^n_i 下每個解的形式, 因此可由 Proposition 4.2.3 得知 f (x) $\equiv$ 0(mod m) 有解. 關於此部份以後在探討中國剩餘定理時我們會再說明.