同餘的分類

一般來說要將一個集合分類必須符合以下三個要素. 第一個就是, 自己和自己是同類的; 另一要素是若甲和乙是同類的則乙也必須和甲是同類的; 最後一個要素是如果甲和乙同類且乙和丙同類, 則甲必須和丙同類. 很多同學應該知道這樣的分類同類間的關係稱之為 equivalence relation. 我們還是用數學的方法給 equivalence relation 正式的定義.

Definition 3.1.1 若一集合 S 中我們用 a $\sim$ b 表示 a 和 b 是同類的, 則這樣的分類若符合以下性質我們稱之為 equivalence relation:

(equiv1): 對所有 a $\in$ S, 我們都有 a $\sim$ a (reflexivity).
(equiv2): 若 a $\sim$ b, 則 b $\sim$ a (symmetry).
(equiv3): 若 a $\sim$ b 且 b $\sim$ c, 則 a $\sim$ c (transitivity).

有些同學可能會覺得奇怪既然 (equiv2) 說: 若 a $\sim$ b 則 b $\sim$ a. 那麼再利用 (equiv3) 我們可得 a $\sim$ a. 為什麼還要強調 (equiv1) 呢? 主要原因是 (equiv1) 強調是 S 中的任一元素 a 都須符合 a $\sim$ a. 如果我們只要求 (equiv2) 和 (equiv3), 那麼如果 S 中有一元素 a 在 S 中找不到任何的元素 b 使得 a $\sim$ b, 那麼 a 就不一定滿足 a $\sim$ a 了. 因此會造成有的元素有可能沒有被分類到. 而符合 equivalence relation 的分類就確保每一個元素都會被分到某一類 (不過有可能某一類中只有一個元素).

到底用 equivalence relation 分類有什麼好處呢? 首先當然是如前所說由 (equiv1) 可得每一個元素都會被分到某一類. 另外由 (equiv2) 和 (equiv3) 知兩個不同類的集合不會有交集; 這是因為如果 b 在 A 類且在 B 類中, 則在 A 類中的任一元素 a 因和 b 是同類的故 a $\sim$ b 而 B 類中的任一元素 c 因也和 b 同類故 b $\sim$ c. 故由 (equiv2) 和 (equiv3) 知 a $\sim$ c. 也就是說 A 中的所有元素和 B 中的所有元素都同類. 這和 A 與 B 是不同類的假設相矛盾. 總而言之利用一個 equivalent relation 我們可以將一集合分割成兩兩互不相交的類別.

Definition 3.1.2 給定一正整數 m, 如果 a, b $\in$ $\mathbb {Z}$ 在除以 m 之下其餘數相同, 我們稱 a, b 在除以 m 之下是同餘的 (a is congruent to b modulo m), 且用符號 a $\equiv$ b(mod m) 來表示. 若 a 和 b 在除以 m 之下不同餘 (a is incongruent to b modulo m), 則用 a $\not\equiv$ b(mod m) 來表示.

要注意在談同餘時一定要先固定一個 m 才能說. 沒有 a 和 b 是同餘的說法, 你必須完整的說出 a 和 b 在除以什麼之下是同餘的才對.

雖然檢查 a, b 在除以 m 之下是否同餘, 依定義要檢查 a 和 b 除以 m 之餘數是否相同, 但事實上只要檢查 m 是否整除 a - b.

証明. 依定義若 a $\equiv$ b(mod m) 則依定義存在 h₁, h₂ $\in$ $\mathbb {Z}$ 使得 a = mh₁ + r 及 b = mh₂ + r 其中 0 $\le$ r < m. 故得 a - b = m(h₁ - h₂) 也就是說 m| a - b.

反之假設 a, b 除以 m 之餘數分別為 r₁ 及 r₂, 即分別存在 h₁, h₂ $\in$ $\mathbb {Z}$ 使得 a = mh₁ + r₁ 及 b = mh₂ + r₂, 其中 0 $\le$ r₁, r₂ < m, 則知 a - b = m(h₁ - h₂) + (r₁ - r₂). 故由假設 m| a - b 得 m| r₁ - r₂. 又因 0 $\le$ r₁, r₂ < m, 知 - m < r₁ - r₂ < m, 故由 m| r₁ - r₂ 得 r₁ = r₂. $\qedsymbol$

我們可以利用 Lemma 3.1.3 很快的得到 congruent relation 是一個 equivalent relation.

Proposition 3.1.4 給定一正整數 m, 則整數在除以 m 同餘的分類之下是一個 equivalent relation. 也就是說符合以下三個性質.

若 a $\in$ $\mathbb {Z}$ 則 a $\equiv$ a(mod m).
若 a $\equiv$ b(mod m) 則 b $\equiv$ a(mod m).
若 a $\equiv$ b(mod m) 且 b $\equiv$ c(mod m), 則 a $\equiv$ c(mod m).

証明. (1) 若 a $\in$ $\mathbb {Z}$ , 因 a - a = 0, 得 m| a - a. 故由 Lemma 3.1.3 知 a $\equiv$ a(mod m).

(2) 若 a $\equiv$ b(mod m) 由 Lemma 3.1.3 知 m| a - b, 故由 m| b - a 得證 b $\equiv$ a(mod m).

(3) 若 a $\equiv$ b(mod m) 且 b $\equiv$ a(mod m), 則知 m| a - b 且 m| b - c. 故知 m|(a - b) + (b - c), 即 m| a - c. 也就是說 a $\equiv$ c(mod m). $\qedsymbol$

由於同餘的概念用分類的看法是很好的分類且這樣的看法談論一些性質很方便, 今後我們經常會用 ``a 和 b 在 modulo m 之下是同類"的說法來表達: a 和 b 除以 m 之餘數相同.

既然用同餘的概念可將整數分類, 我們自然會問給定 m $\in$ $\mathbb {N}$ , 在 modulo m 之下可以分成幾類呢? 所有整數在除以 m 之下的餘數總共可能為 0, 1,..., m - 1, 所以得知共有 m 類. 分類好後在每一類中我們可以挑一個代表元素來代表這一類, 且每類中僅挑出一個代表而不重複, 這樣所挑出的代表我們給它一個特別名稱.

Definition 3.1.5 給定一正整數 m, 若集合 S 有 m 個元素, 其中元素在 modulo m 之下兩兩不同類, 則稱 S 是一個 complete residue system modulo m.

若 S 是一個 complete residue system modulo m, 則因整數在 modulo m 之下是一個 equivalent relation, 所以 S 中的元素都會被分到某一類, 而且又已知 S 中的元素兩兩不同類, 再加上已知 $\mathbb {Z}$ 在 modulo m 之下共能被分成 m 類, 所以由 S 的元素個數為 m 知, 每一類中都可在 S 中找到唯一的元素代表此類. 換言之, S 中的元素足以代表 $\mathbb {Z}$ 在 modulo m 之下之分類. 例如 {0, 1,..., m - 1} 就是一個常用的 complete residue system modulo m. 不過有時我們會因問題的需要選擇別種 complete residue system modulo m.

利用同餘分類除了是一個 equivalent relation 之外, 還有許多很好的性質. 例如在下一節我們會介紹可以在各類之間定義運算. 另外在 modulo m 之下, 我們發現其實同類的元素和 m 之最大公因數其實是相同的.

証明. 若 a $\equiv$ b(mod m), 由定義知 a 和 b 在除以 m 之下之餘數相同, 設其為 r. 故由 Lemma 1.3.1 知 gcd(a, m) = gcd(r, m) = gcd(b, m). $\qedsymbol$

特別的若 a 和 m 是互質的, 則在 modulo m 之下和 a 同類的元素都和 m 互質. 也就是說若 S 是一個 complete residue system modulo m, 只要找出 S 中有哪些元素和 m 互質, 那麼這些元素所代表的分類裡每個元素都和 m 互質. 在 modulo m 之下到底有幾類的元素會和 m 互質呢? 我們就考慮 S = {0, 1,..., m - 1} 這個 complete residue system modulo m 吧! S 中和 m 互質的元素個數依 Euler $\phi$ -function 的定義就是 $\phi$ (m) 個, 故知整數在 modulo m 之下共有 $\phi$ (m) 類的元素和 m 是互質的. 有時在處理問題時我們需要將這 $\phi$ (m) 類的代表元素列出, 所以我們也給它一個特別名稱.

Definition 3.1.7 給定一正整數 m, 若集合 S 有 $\phi$ (m) 個元素, 其中的元素皆與 m 互質且在 modulo m 之下兩兩不同類, 則稱 S 是一個 reduced residue system modulo m.

當 m 是一質數 p 時, {1,..., p - 1} 就是最常用的 reduced residue system modulo p.