一次的 Congruence Equations

給定 m $\in$ $\mathbb {N}$ 所謂 modulo m 的一次 congruence equation 即 ax $\equiv$ b(mod m) 這樣形式的 congruence equation, 其中 a, b $\in$ $\mathbb {Z}$ 且 m $\nmid$ a. 首先我們來看看如何判別一個一次的 congruence equation 是否有解.

証明. 因為 d = gcd(m, a) 故由 Corollary 1.2.5 知存在 r, s $\in$ $\mathbb {Z}$ 使得 d = rm + sa.

現假設 d| b, 即存在 b' $\in$ $\mathbb {Z}$ 使得 b = b'd. 因此 b = b'd = b'rm + b'sa, 故若令 x = sb', 則 ax = asb' = b - b'rm. 也就是說 m| ax - b, 得證 x $\equiv$ sb'(mod m) 為 ax $\equiv$ b(mod m) 之一解.

反之, 若 x $\equiv$ c(mod m) 為 ax $\equiv$ b(mod m) 之一解, 即 m| ac - b. 換言之, 存在 r $\in$ $\mathbb {Z}$ 使得 ac - b = mr, 也就是說 b = ac - mr. 現由於 d = gcd(m, a), 我們有 d| m 且 d| a, 故得證 d| b. $\qedsymbol$

由 Proposition 4.3.1 的證明我們知道, 給定 m $\in$ $\mathbb {N}$ , 且 a, b $\in$ $\mathbb {Z}$ . 假設 gcd(m, a) = d 且 d| b. 若 r, s, b' $\in$ $\mathbb {Z}$ 滿足 d = rm + sa 且 b = b'd, 則 x $\equiv$ sb'(mod m) 為 ax $\equiv$ b(mod m) 的一個解. 不過這並不表示所有的解都可依此得到. 要如何找到所有的解呢? 按照以前我們常用的方法就是先探討兩解之間的關係, 再利用已知的一個解來找到所有的解. 接下來我們來看 ax $\equiv$ b(mod m) 其解之間的關係.

Proposition 4.3.2 給定 m $\in$ $\mathbb {N}$ , 考慮一次的 congruence equation ax $\equiv$ b(mod m). 假設 d = gcd(m, a) 且已知 x $\equiv$ c(mod m) 是 ax $\equiv$ b(mod m) 的一個解, 則對任意 ax $\equiv$ b(mod m) 的解 c' 都會滿足 c' $\equiv$ c(mod m/d). 反之, 對任意的 t $\in$ $\mathbb {Z}$ ,

x = c + $\displaystyle {\frac{m}{d}}$ t

亦為 ax $\equiv$ b(mod m) 的一個解.

証明. 假設 x $\equiv$ c'(mod m) 亦為 ax $\equiv$ b(mod m) 的一個解, 則由於已知 x $\equiv$ c(mod m) 為一解, 故得 ac $\equiv$ b $\equiv$ ac'(mod m). 因此由 Proposition 3.2.3 知 c $\equiv$ c'(mod m/d).

反之, 若 c' = c + (m/d )t, 其中 t $\in$ $\mathbb {Z}$ , 則 ac' = ac + (a/d )mt. 因 d = gcd(m, a), 故知 a/d $\in$ $\mathbb {Z}$ , 也就是說 ac' $\equiv$ ac(mod m). 不過已知 ac $\equiv$ b(mod m), 所以得證 ac' $\equiv$ b(mod m). $\qedsymbol$

Proposition 4.3.2 告訴我們考慮 congruence equation ax $\equiv$ b(mod m). 若 x $\equiv$ c(mod m) 是一個解, 則其它的解皆為 c + (m/d )t 這樣的形式, 其中 d = gcd(m, a) 且 t $\in$ $\mathbb {Z}$ . 因此知在 modulo m 之下 x $\equiv$ c + (m/d ), x $\equiv$ c + 2(m/d ),..., x $\equiv$ c + (d - 1)(m/d ) 都會是 ax $\equiv$ b(mod m) 的解. 我們將會證明這些解在 modulo m 之下皆相異, 而且在 modulo m 之下所有的解都可表為這些形式, 因此綜合 Proposition 4.3.1 以及 Proposition 4.3.2, 我們有以下之結果.

Theorem 4.3.3 給定 m $\in$ $\mathbb {N}$ , a, b $\in$ $\mathbb {Z}$ 考慮一次的 congruence equation ax $\equiv$ b(mod m). 令 d = gcd(m, a).

若 d $\nmid$ b, 則 ax $\equiv$ b(mod m) 無解.
若 d $\nmid$ b, 則 ax $\equiv$ b(mod m), 在 modulo m 之下有 d 個解. 且若已知 x $\equiv$ c(mod m) 為一解, 則

x $\displaystyle \equiv$ c + $\displaystyle {\frac{m}{d}}$ t, t = 0, 1,..., d - 1
為 ax $\equiv$ b(mod m) 在 modulo m 之下所有的解.

特別地, 當 a 和 m 互質時, 對於所有 b $\in$ $\mathbb {Z}$ , ax $\equiv$ b(mod m) 皆有解, 且其解在 modulo m 之下是唯一的.

証明. 依 Proposition 4.3.1 以及 Proposition 4.3.2, 我們只剩下要證明 ax $\equiv$ b(mod m) 若有解, 則在 modulo m 之下共有 d 個解. 因此我們需證明兩件事: (一) 當 0 $\le$ i, j $\le$ d - 1 且 i $\ne$ j 時 c + mi/d $\not\equiv$ c + mj/d(mod m) (如此便可得當 0 $\le$ i $\le$ d - 1 時 c + mi/d 在 modulo m 之下皆相異). (二) 對任意 t $\in$ $\mathbb {Z}$ , 皆存在 i $\in$ {0, 1,..., d - 1} 使得 c + mt/d $\equiv$ c + mi/d(mod m) (如此便得證所有的解確可寫為 c + mi/d, 其中 0 $\le$ i $\le$ d - 1 的形式).

假設 0 $\le$ i, j $\le$ d - 1 且 i $\ne$ j. 不失一般性我們假設 i > j, 此時 1 $\le$ i - j $\le$ d - 1. 若 c + mi/d $\equiv$ c + mj/d(mod m), 即 (m/d )i $\equiv$ (m/d )j(mod m). 由於 gcd(m/d, m) = m/d, 故由 Proposition 3.2.3 知 i $\equiv$ j(mod m/(m/d )), 即 i $\equiv$ j(mod d). 也就是說 d| i - j. 此和 1 $\le$ i - j $\le$ d - 1 矛盾, 故得證 c + mi/d $\not\equiv$ c + mj/d(mod m).

現已知 ax $\equiv$ b(mod m) 的解皆為 c + mt/d, 其中 t $\in$ $\mathbb {Z}$ 這樣的形式. 對任意 t $\in$ $\mathbb {Z}$ , 由 Theorem 1.2.1 知存在 h, r $\in$ $\mathbb {Z}$ 使得 t = hd + r, 其中 0 $\le$ r $\le$ d - 1. 因此得

c + mt/d = c + m(hd + r)/d = c + mh + mr/d.

故令 i = r, 我們有 0 $\le$ i $\le$ d - 1 且 c + mt/d $\equiv$ c + mi/d(mod m). 也就是說 ax $\equiv$ b(mod m) 的解皆為 c + mi/d, 其中 0 $\le$ i $\le$ d - 1 這樣的形式. $\qedsymbol$

由 Theorem 4.3.3 我們知若 ax $\equiv$ b(mod m) 有解, 只要解出其中一個解, 其他的解就可得到. 至於找解的方法, 除了 Proposition 4.3.1 的證明中所介紹的方法外, 事實上我們可以利用 Proposition 4.2.1 所提的方法來解. 因為此時若 d = gcd(m, a), 則 d| b, 也就是說 d 是 a, b 和 m 的公因數. 故若將 a, b, m 分別寫成 a = a'd, b = b'd 和 m = m'd 的形式 (其中 a', b', m' $\in$ $\mathbb {Z}$ 且 gcd(m', a') = 1), 利用 Proposition 4.2.1 我們知可以先解 a'x $\equiv$ b'(mod m') 這一個 congruence equation. 由於 gcd(a', m') = 1, 依 Proposition 3.2.5 知存在 e $\in$ $\mathbb {Z}$ 使得 a'e $\equiv$ 1(mod m'). 故將 a'x $\equiv$ b'(mod m') 之兩邊乘上 e 得

Example 4.3.4 我們要解 16x $\equiv$ 8(mod 52). 因 gcd(52, 16) = 4 且 4| 8, 故知此 congruence equation 必有解, 且在 modulo 28 之下共有 4 個解.

首先我們先解 4x $\equiv$ 2(mod 13). 由於 4×10 $\equiv$ 1(mod 13), 我們得知 x $\equiv$ 2×10 $\equiv$ 7(mod 13) 為 4x $\equiv$ 2(mod 13) 的一個解. 因而得 x $\equiv$ 7(mod 52) 為 16x $\equiv$ 8(mod 52) 的一個解 (即 16×7 = 112 = 52×2 + 8).

至於其他的解, 由於 52/4 = 13 故依 Theorem 4.3.3 知在 modulo 52 之下 x $\equiv$ 7, 20, 33, 46(mod 52) 為 16x $\equiv$ 8(mod 52) 的所有解.