同餘的分類

Congruence relation 是一個equivalent relation. ... 在除以m 之下其餘數相同, 我們稱a, b 在除以m 之下是同餘的(a is congruent to b modulo m), ... 下一頁:同餘的運算 上一頁:Congruences 前一頁:Congruences 同餘的分類 Congruencerelation是一個equivalentrelation.首先我們探討 equivalentrelation的基本概念. 一般來說要將一個集合分類必須符合以下三個要素.第一個就是, 自己和自己是同類的; 另一要素是若甲和乙是同類的則乙也必須和甲是同類的; 最後一個要素是如果甲和乙同類且乙和丙同類,則甲必須和丙同類. 很多同學應該知道這樣的分類同類間的關係稱之為equivalence relation.我們還是用數學的方法給equivalencerelation正式的定義. Definition3.1.1  若一集合S中我們用ab表示a和b是同類的, 則這樣的分類若符合以下性質我們稱之為equivalencerelation: (equiv1) 對所有aS,我們都有aa(reflexivity). (equiv2) 若ab,則ba(symmetry). (equiv3) 若ab且bc,則ac (transitivity). 我們常用的``="就是一個典型的equivalentrelation. 有些同學可能會覺得奇怪既然(equiv2)說:若ab則ba. 那麼再利用(equiv3)我們可得aa.為什麼還要強調(equiv1)呢? 主要原因是(equiv1)強調是S中的任一元素a都須符合aa. 如果我們只要求(equiv2)和(equiv3),那麼如果S中有一元素a在 S中找不到任何的元素b使得ab,那麼a就不一定滿足 aa了.因此會造成有的元素有可能沒有被分類到.而符合 equivalencerelation的分類就確保每一個元素都會被分到某一類 (不過有可能某一類中只有一個元素). 到底用equivalencerelation分類有什麼好處呢?首先當然是如前所說由 (equiv1)可得每一個元素都會被分到某一類.另外由(equiv2)和(equiv3) 知兩個不同類的集合不會有交集;這是因為如果b在A類且在B 類中,則在A類中的任一元素a因和b是同類的故ab而 B類中的任一元素c因也和b同類故bc.故由(equiv2)和 (equiv3)知ac.也就是說A中的所有元素和B 中的所有元素都同類.這和A與B是不同類的假設相矛盾. 總而言之利用一個equivalentrelation 我們可以將一集合分割成兩兩互不相交的類別. 接下來我們就來探討同餘的分類法. Definition3.1.2  給定一正整數m,如果 a,b在除以m之下其餘數相同,我們稱 a,b在除以m之下是同餘的(aiscongruenttobmodulo m),且用符號 ab(modm)來表示.若a和b 在除以m之下不同餘(aisincongruenttobmodulom), 則用 ab(modm)來表示. 要注意在談同餘時一定要先固定一個m才能說.沒有a和b 是同餘的說法,你必須完整的說出a和b 在除以什麼之下是同餘的才對. 雖然檢查a,b在除以m之下是否同餘,依定義要檢查a和b除以 m之餘數是否相同,但事實上只要檢查m是否整除a-b. Lemma3.1.3  給定一正整數m,且 a,b,則 ab(modm)若且唯若 m|a-b. 証明. 依定義若 ab(modm)則依定義存在 h1,h2使得 a=mh1+r及b=mh2+r其中0r