解 Congruence Equation 的原則

給定 f (x) = c_nxⁿ + ^... + c₁x + c₀, 其中 c_i $\in$ $\mathbb {Z}$ . 若已知對於 m $\in$ $\mathbb {N}$ , a $\in$ $\mathbb {Z}$ 是 f (x) $\equiv$ 0(mod m) 的一個解, 即 f (a) $\equiv$ 0(mod m). 假設 b $\equiv$ a(mod m), 由 Proposition 3.2.2 知, 對任意 i $\in$ $\mathbb {N}$ 皆有 bⁱ $\equiv$ aⁱ(mod m). 再由同一 Proposition 知 c_ibⁱ $\equiv$ c_iaⁱ(mod m), 進而得 f (b) $\equiv$ f (a)(mod m). 也就是說, 若 x = a 是 f (x) $\equiv$ 0(mod m) 的一個整數解, 則對任意 b $\in$ $\mathbb {Z}$ 滿足 b $\equiv$ a(mod m), x = b 亦為 f (x) $\equiv$ 0(mod m) 的一個解. 所以若 x = a 是 f (x) $\equiv$ 0(mod m) 的一個整數解, 我們通常會說 x $\equiv$ a(mod m) 是 f (x) $\equiv$ 0(mod m) 的一個解. 當然還有可能有其他在 modulo m 之下和 a 不同餘的整數會是 f (x) $\equiv$ 0(mod m) 的解. 我們必須把這些解用 modulo m 的同餘類的方式全部寫下, 這樣的表達方法才能將所有的整數解寫下. 所以我們在談 f (x) $\equiv$ 0(mod m) 的解時, 談的是 modulo m 的同餘類, 因此當我們說 f (x) $\equiv$ 0(mod m) 的解的個數時, 談的是在 modulo m 之下有多少的相異同餘類會滿足 f (x) $\equiv$ 0(mod m), 而不是談有多少個整數解.

從這個角度來看, 我們只要列出一個 modulo m 的 complete residue system S, 然後將 S 的元素一一帶入 f (x) 中, 看看哪一些會使得 f (x) $\equiv$ 0(mod m), 那麼就可以找到所有的解了. 不過這方法在 m 很大時就顯得不切實際了. 因此我們希望能發展一套理論, 至少能理解一些較特殊的 congruence equation 其解的特性. 不過不管怎樣, 我們知道一個 congruence equation 在 modulo m 之下其解的個數至多就是 m.

其實上, 我們之前就已接觸到一些解 congruence equation 的問題了. 在 modulo m 之下找 a $\in$ $\mathbb {Z}$ 的乘法反元素的問題事實上就是在解 ax $\equiv$ 1(mod m) (即 ax - 1 $\equiv$ 0(mod m)) 這一個 congruence equation. 由 Proposition 3.2.5 知當 a 和 m 不互質時, 此 congruence equation 無解. 另外加上 Proposition 3.2.3, 我們知道當 a 和 m 互質時此 congruence equation 在 modulo m 之下有唯一解.

再如 Lemma 3.4.2 是討論當 p 是質數時 x² $\equiv$ 1(mod p) 的解. 此時由 Lemma 3.4.2 我們知當 p 是奇質數時有兩個解, 分別是 x $\equiv$ 1(mod p) 和 x $\equiv$ - 1(mod p). 我們提過當 m 不是質數時, 雖然 x $\equiv$ ±1(mod m) 仍為 x² $\equiv$ 1(mod m) 這一個 congruence equation 的兩個解, 但此 congruence equation 有可能有多於兩個解. 例如 x² $\equiv$ 1(mod 15) 的解就是 x $\equiv$ ±1(mod 15) 和 x $\equiv$ ±4(mod 15) 這 4 個解. 這和我們一般熟知一個 n 次多項式至多有 n 個解不同, 應特別注意.

一個 n 次的實係數多項式至多有 n 個解的原因是因為實係數多項式之間也有所謂的除法原理, 這個原理並不能套用在整系數多項式中. 不過當除式是一個最高次項係數為 1 的整係數多項式時, 仍可套用除法原理. 由於我們並不需要一般的性質, 這裡我們僅探討除式是一次多項式的情況.

Lemma 4.1.1 假設 f (x) 是一個 n 次 (n $\ge$ 1) 的整係數多項式且 a $\in$ $\mathbb {Z}$ . 則存在一個 n - 1 次的整係數多項式 h(x) 以及 r $\in$ $\mathbb {Z}$ 滿足

f (x) = (x - a)h(x) + r.

証明. 對 f (x) 的次數 n 做數學歸納法. 假設 f (x) 是 1 次多項式, 即 f (x) = c₁x + c₀, 則令 h(x) = c₁ 且 r = ac₁ + c₀, 我們得 (x - a)h(x) + r = f (x).

應用數學歸納法, 假設對次數 n < k 的整係數多項式 g(x), 皆存在 n - 1 次的整係數多項式 h₀(x) 以及 r₀ $\in$ $\mathbb {Z}$ 使得 g(x) = (x - a)h₀(x) + r₀. 現考慮 f (x) 的次數 n = k 的情形, 也就是說 f (x) = c_kx^k + c_{k - 1}x^{k - 1} + ^... + c₁x + c₀, 其中 c_i $\in$ $\mathbb {Z}$ 且 c_k $\ne$ 0. 令 g(x) = f (x) - (x - a)c_kx^{k - 1}, 則 g(x) = (c_{k - 1} + c_ka)x^{k - 1} + ^...c₁x + c₀ 是一個次數小於 k 的整係數多項式. 故套用歸納假設知存在一次數小於 k - 1 的整係數多項式 h₀(x) 以及 r₀ $\in$ $\mathbb {Z}$ 使得 g(x) = (x - a)h₀(x) + r₀. 也就是說 f (x) = (x - a)c_kx^{k - 1} + (x - a)h₀(x) + r₀. 故令 h(x) = c_kx^{k - 1} + h₀(x) 以及 r = r₀, 我們有 h(x) 是一個次數為 k - 1 的整係數多項式且 r $\in$ $\mathbb {Z}$ 滿足 f (x) = (x - a)h(x) + r. $\qedsymbol$

套用 Lemma 4.1.1, 我們可以證得當 p 是一質數時在 modulo p 之下一個 n 次的 congruence equation 最多有 n 個解. 不過首先我們需對一個 congruence equation 的次數下個定義.

Definition 4.1.2 假設 f (x) = c_nxⁿ + ^... + c₁x + c₀ 是一個整係數多項式, 給定 m $\in$ $\mathbb {N}$ .

若 m $\nmid$ c_n, 則我們稱 f (x) 在 modulo m 之下是一個次數 (degree) 為 n 的多項式.
若 m $\nmid$ c_r 但 m| c_i, for r < i $\le$ n, 則我們稱 f (x) 在 modulo m 之下是一個次數為 r 的多項式.

如果一個整係數多項式 g(x) 其在 modulo m 之下之次數為 n, 則我們稱 g(x) $\equiv$ 0(mod m) 是一個 n 次的 congruence equation.

由此定義我們知道若 f (x) 是一個在 modulo m 之下次數為 n 的整係數多項式, 有可能 f (x) 本身的次數是大於 n 的. 不過我們可以找到一個次數為 n 的整係數多項式 g(x) (例如刪去 f (x) 中可以被 m 整除的項) 使得對任一整數 a, 皆有 f (a) $\equiv$ g(a)(mod m). 所以 f (x) $\equiv$ 0(mod m) 的解會和 g(x) $\equiv$ 0(mod m) 相同. 由於我們只關心 congruence equation 的解, 所以今後當討論一個 n 次的 congruence equation f (x) $\equiv$ 0(mod m) 時, 不失ㄧ般性, 我們就直接假設 f (x) 的次數為 n.

証明. 不失一般性, 我們假設 f (x) = c_nxⁿ + ^... + c₁x + c₀, 其中 p $\nmid$ c_n. 我們對 n 做歸納法. 首先當 f (x) = c₁x + c₀ 是一次整係數多項式時, 假設 x $\equiv$ a(mod p) 是 f (x) $\equiv$ 0(mod p) 的一個解. 現另假設 x $\equiv$ b(mod p) 也是一個解, 亦即 c₁a + c₀ $\equiv$ c₁b + c₀(mod p). 因為 gcd(p, c₁) = 1, 由 Lemma 3.2.4 可得 a $\equiv$ b(mod p). 也就是說 n = 1 時至多有一個解.

用歸納假設當 n < k 時一個 n 次的 congruence equation 至多有 n 個解. 現考慮 n = k 的情形. 若 x $\equiv$ a(mod p) 是 f (x) $\equiv$ 0(mod p) 的一個解, 利用 Lemma 4.1.1 知存在一個次數為 k - 1 的整係數多項式 h(x) 以及 r $\in$ $\mathbb {Z}$ 使得 f (x) = (x - a)h(x) + r. 依假設 x $\equiv$ a(mod p) 是 f (x) $\equiv$ 0(mod p) 的一個解, 即 f (a) $\equiv$ 0(mod p), 將 a 代入得 f (a) = r $\equiv$ 0(mod p). 現另假設 x $\equiv$ b(mod p) 也是一個解, 則由 f (b) = (b - a)h(b) + r 知 (b - a)h(b) $\equiv$ 0(mod p). 換言之, 若 b $\not\equiv$ a(mod p), 即 p $\nmid$ (b - a), 則由 Lemma 1.4.2 知, p| h(b), 也就是說 x $\equiv$ b(mod p) 是 h(x) $\equiv$ 0(mod p) 的一個解. 因此我們知道 k 次 congruence equation f (x) $\equiv$ 0(mod p) 的解為 x $\equiv$ a(mod p) 或 h(x) $\equiv$ 0(mod p) 的解. 然而 h(x) $\equiv$ 0(mod p) 是一個次數小於 k 的 congruence equation, 故依歸納法假設其至多有 k - 1 個解, 故得證 f (x) $\equiv$ 0(mod p) 至多有 k 個解. $\qedsymbol$

最後我們再次提醒, 要解 congruence equation f (x) $\equiv$ 0(mod m) 需將解的所有情況寫下來, 一般會將解以 x $\equiv$ a(mod m) 這樣的形式寫下來. 不過有時為了方便我們會將解以 modulo 別的數的方式寫下. 例如解 x² $\equiv$ 1(mod 8), 我們發現所有的奇數都滿足, 所以為了方便我們可以將解以 x $\equiv$ 1(mod 2) 寫下. 不過要注意這種形式寫下後當我們提及解的個數時需提及在 modulo 什麼之下的解的個數. 例如在此例中我們可以說 x² $\equiv$ 1(mod 8) 在 modulo 8 之下有 x $\equiv$ 1, 3, 5, 7(mod 8), 4 個解, 也可以說在 modulo 2 之下有一個解.