同餘的運算

給定 m $\in$ $\mathbb {N}$ , 在 modulo m 之下我們將同一類的元素看成是同樣的東西 (也就是將一整類的元素看成是一個元素), 想看看各類之間要如何相加相乘呢? 很自然的想法是在要相加的兩類中各挑一個代表元素, 然後相加相乘看看落於哪一類. 不過這會碰到一個問題就是每一類中大家挑的代表元素若不同會不會相加相乘後所得結果不同呢? 例如在 modulo 5 之下, 我們要將除以 5 餘數為 2 的這一類和餘數為 3 的這一類相加. 若餘數為 2 和 3 的這兩類我們分別挑 2 和 3 來代表, 那麼由 2 + 3 = 5 及 2×3 = 6 得到相加相乘後會分別落在餘 0 和餘 1 的這兩類中. 如果挑不同的代表元素呢? 比方說餘 2 和餘 3 的這兩類我們分別挑 7 和 -12 當代表, 結果 7 + (- 12) = - 5 及 7×(- 12) = - 84, 我們仍得到相加後落於除以 5 餘 0 這一類, 而相乘後落於除以 5 餘 1 這一類, 和前面結果一致. 我們不能由這個例子就認為這一定對, 需要想個方法來說明這是事實而不是巧合.

Lemma 3.2.1 給定 m $\in$ $\mathbb {N}$ , 若 a, b $\in$ $\mathbb {Z}$ 滿足 a $\equiv$ b(mod m), 則對任意 c $\in$ $\mathbb {Z}$ 皆有

a + c $\displaystyle \equiv$ b + c(mod m) and ac $\displaystyle \equiv$ bc(mod m).

証明. 由假設 a $\equiv$ b(mod m) 知 m| a - b. 故得 m|(a + c) - (b + c), 也就是說 a + c $\equiv$ b + c(mod m). 另一方面由於 m|(a - b)c 故知 m| ac - bc, 得證 ac $\equiv$ bc(mod m).. $\qedsymbol$

Lemma 3.2.1 告訴我們兩個同類的數分別加上同一個數後所得之數也會同類. 同類的數同乘一個數後所得之數也同類. 依此我們就可以得到兩個同類的數分別加上(或乘上)另兩個同類的數其結果仍會同類.

Proposition 3.2.2 給定 m $\in$ $\mathbb {N}$ , 若 a, b, c, d $\in$ $\mathbb {Z}$ 滿足 a $\equiv$ b(mod m) 且 c $\equiv$ d(mod m), 則

a + c $\displaystyle \equiv$ b + d(mod m) and ac $\displaystyle \equiv$ bd(mod m).

証明. 因 a $\equiv$ b(mod m), 由 Lemma 3.2.1 知 a + c $\equiv$ b + c(mod m). 同理又因 c $\equiv$ d(mod m) 知 b + c $\equiv$ b + d(mod m), 故利用同餘是 equivalent relation (即 Proposition 3.1.4(3)) 知 a + c $\equiv$ b + d(mod m).

同樣的, 由 a $\equiv$ b(mod m) 及 c $\equiv$ d(mod m) 分別得 ac $\equiv$ bc(mod m) 及 bc $\equiv$ bd(mod m), 故知 ac $\equiv$ bd(mod m). $\qedsymbol$

由此定理, 我們以後要計算 1752 乘以 388 除以 5 之餘數, 我們不必將它們乘開後再看其除以 5 之餘數為何. 我們可以利用 1752 $\equiv$ 2(mod 5) 以及 388 $\equiv$ 3(mod 5) 很快的得到 1752×388 $\equiv$ 6 $\equiv$ 1(mod 5).

Proposition 3.1.4 (即 congruence relation 是 equivalent relation) 告訴我們當固定 m $\in$ $\mathbb {N}$ 時 `` $\equiv$ " 有和等號相同的法則. 另一方面在 Lemma 3.2.1 中若令 c = - 1, 則當 a $\equiv$ b(mod m) 時我們有 - a $\equiv$ - b(mod m). 所以套用 Proposition 3.2.2 知我們可以將 $\equiv$ ``看成"是等號 (即將同餘的元素看成是相同) 而將同餘類的運算如一般整數作加, 減, 乘的運算. 例如在計算 5742 除以 11 的餘數時, 我們可以寫成 5742 = 5×10³ + 7×10² + 4×10 + 2. 由於 10 $\equiv$ - 1(mod 11) 故得 5742 $\equiv$ 5×(- 1)³ + 7×(- 1)² + 4×(- 1) + 2 $\equiv$ - 5 + 7 - 4 + 2 $\equiv$ 0(mod 11). 也就是說 5742 可以被 11 整除, 這和我們中學時代所學判別 11 的倍數法則相同. 同理判別 9 的倍數法則也可由 10 $\equiv$ 1(mod 9) 而得. 你也可以利用 10 $\equiv$ 3(mod 7) 整理出一套判別 7 的倍數之法則 (當然會複雜多了).

這裡有兩點要特別注意: 首先, 在 modulo 不同的數之下所得的分類法不同, 所以不能將 $\equiv$ 混用. 例如若 a = 3, 我們可以說 a $\equiv$ 3(mod 5) 且 a $\equiv$ 3(mod 7), 但你不能因為 a² $\equiv$ 3² $\equiv$ 4(mod 5) 而說 a² $\equiv$ 4(mod 7). 另外要注意的就是在一般等式中的除(約)在 congruence 並不一定適用. 也就是說若 a $\ne$ 0 且 ab = ac, 我們知 b = c 但這在 congruence 的情況有可能出問題. 例如當 a = 2, b = 2, c = 5 在 modulo 6 之下我們有 a $\not\equiv$ 0(mod 6) 且 ab $\equiv$ ac(mod 6), 但很明顯的 b $\not\equiv$ c(mod 6). 所以在處理 congruence 的問題時要用除法消去一個數時要特別注意. 以下定理告訴我們何時可消, 何時不可消.

Proposition 3.2.3 給定 m $\in$ $\mathbb {N}$ 且假設 a, b, c $\in$ $\mathbb {Z}$ . 令 d = gcd(m, a) 則 ab $\equiv$ ac(mod m) 若且唯若 b $\equiv$ c(mod m/d).

証明. 因 d = gcd(m, a), 我們令 m = m'd 且 a = a'd, 由 Corollary 1.2.3 知 gcd(m', a') = 1.

現假設 ab $\equiv$ ac(mod m), 即 m| ab - ac. 因此由 Lemma 1.1.5(2) 知 (m/d )|(a/d )(b - c), 即 m'| a'(b - c). 故因 gcd(m', a') = 1 利用 Proposition 1.2.7(1) 得證 m'| b - c, 即 b $\equiv$ c(mod m/d).

反之, 若 b $\equiv$ c(mod m/d), 即 m'| b - c. 因此由 Lemma 1.1.5(1) 得 dm'| d (b - c), 即 m| d (b - c). 也就是說 db $\equiv$ dc(mod m). 故由 Lemma 3.2.1 知 a'db $\equiv$ a'dc(mod m), 得證 ab $\equiv$ ac(mod m). $\qedsymbol$

例如之前的例子, 因為 m = 6 且 a = 2, 得 gcd(m, a) = 2. 故由 ab $\equiv$ ac(mod 6) 得 b $\equiv$ c(mod 3). 事實上, 上例中 b = 2, c = 5, 我們確實有 2 $\equiv$ 5(mod 3).

到底在何時才能把 a 消掉且保持原來 modulo m 的 congruence 呢? 由 Proposition 3.2.3 我們知只有在 gcd(m, a) = 1, 即 m 和 a 互質時才可保證對. 我們將這個重要的性質寫下.

Corollary 3.2.4 給定 m $\in$ $\mathbb {N}$ 且假設 a, b, c $\in$ $\mathbb {Z}$ . 若 m 和 a 互質, 則 ab $\equiv$ ac(mod m) 若且唯若 b $\equiv$ c(mod m).

其實若限制在整數時, 若 a $\ne$ 0 且 ab = ac 可將 a 消去推得 b = c, 正確來說不能用``除" 的概念來說, 而是用整數 a $\ne$ 0 且 b $\ne$ 0 則 ab $\ne$ 0 的性質得到. 這個概念在 congruence 的情況就不一定對, 例如 2 $\not\equiv$ 0(mod 6) 且 3 $\not\equiv$ 0(mod 6) 但是 2×3 $\equiv$ 0(mod 6). 這也是一般來說在 congruence 不能用約的方法消去的主要原因. 然而在考慮有理數時, 若 a $\ne$ 0, 因為必存在另一有理數 a^-1 使得 a^.a^-1 = 1, 所以若 ab = bc, 則兩邊同乘 a^-1, 可得 b = c. 這就是用除法`` 約''的概念消去 a. 由於有理數中對任意非 0 元素 a, 其乘法反元素 (即 a^-1) 必存在, 使得我們在解有理數的方程式時更容易找到解. 在一般整數時雖然僅有 ±1 其乘法反元素為整數, 但在討論 congruence 時有更多元素其乘法反元素會存在.

Proposition 3.2.5 給定 m $\in$ $\mathbb {N}$ , 假設 a $\in$ $\mathbb {Z}$ , 則存在 b $\in$ $\mathbb {Z}$ 滿足 ab $\equiv$ 1(mod m) 若且唯若 a 和 m 互質.

証明. 假設 b $\in$ $\mathbb {Z}$ 滿足 ab $\equiv$ 1(mod m), 即 m| ab - 1. 令 d = gcd(m, a), 可得 d| m 且 d| ab. 故利用 m| ab - 1 及 d| m 可得 d| ab - 1, 再利用 d| ab 得 d| 1. 也就是說 a 和 m 互質.

反之, 若 a 和 m 互質, 即 gcd(m, a) = 1, 則由 Corollary 1.2.5 知存在 r, s $\in$ $\mathbb {Z}$ 使得 mr + as = 1. 故令 b = s, 我們有 m| ab - 1, 亦即 ab $\equiv$ 1(mod m). $\qedsymbol$

最後要強調, 當 a 和 m 互質時雖然有無窮多的整數 b 會滿足 ab $\equiv$ 1(mod m), 但是這樣的 b 在 modulo m 之下是唯一的. 也就是說若 c $\in$ $\mathbb {Z}$ 亦滿足 ac $\equiv$ 1(mod m), 則由於 ab $\equiv$ 1 $\equiv$ ac(mod m) 以及 gcd(m, a) = 1, 套用 Corollary 3.2.4 我們得知 b $\equiv$ c(mod m). 有此唯一性, 我們特別稱 b 為 a 在 modulo m 之下的乘法反元素.