Abstract Algebra MATH 212 Lecture Notes PDF

Mathematics Department Faculty of Science Abstract Algebra MATH 212 Lecturer: Dr. Safi Saber Lecture 2  Partition and Equivalence Relation A partition of a set 𝑆 is a collection of nonempty subsets of 𝑆 such that every element of...

Mathematics Department Faculty of Science Abstract Algebra MATH 212 Lecturer: Dr. Safi Saber Lecture 2  Partition and Equivalence Relation A partition of a set 𝑆 is a collection of nonempty subsets of 𝑆 such that every element of 𝑆 is in exactly one of the subsets.  That is the sets 𝑀1 , 𝑀2 , … , 𝑀𝑛 form a Partition of a set 𝑆 if 𝑀𝑖 ⊆ 𝑆, 𝑀𝑖 ∩ 𝑀𝑗 = ∅, ∀𝑖 ≠ 𝑗, 𝑆 =∪𝑛𝑖=1 𝑀𝑖. For Example: The sets 𝐴1 = 1,3,5,7,9 and 𝐴2 = *2,4,6,8,10+ form a partition of the set S =. *1,2,3,4,5,6,7,8,9,10+ Theorem (Equivalence Relations and Partitions) Let 𝑆 be a nonempty set and let ~ be an equivalence relation on S. Then ~ yields a partition of S, where the partition sets 𝑎 = *𝑥 ∈ 𝑆|𝑥~ 𝑎+. Also, each partition of 𝑆 gives rise to an equivalence relation ~ on 𝑆 where 𝑎 ~ 𝑏 if and only if 𝑎 and 𝑏 are in the same cell of the partition Example 9 Determine whether the given relation is an equivalence relation on the set. Describe the partition a rising from each equivalence relation. 𝑥𝜌𝑦 in ℝ if 𝑥 ≥ 𝑦 Solution  Example 10 Determine whether the given relation is an equivalence relation on the set. Describe the partition a rising from each equivalence relation. (𝑥1 , 𝑦1 )𝜌(𝑥2 , 𝑦2 ) in ℝ × ℝ if 𝑥12 + 𝑦12 = 𝑥22 + 𝑦22 Solution  Example 11 Determine whether the given relation is an equivalence relation on the set. Describe the partition a rising from each equivalence relation. 𝑎 =𝑛 𝑏 in ℤ if 𝑎 = 𝑏 𝑚𝑜𝑑 𝑛 or equivalently 𝑛|(𝑏 − 𝑎) Solution Definition  The sets defined using the equivalence class 𝑎 ≡ 𝑏 mod 𝑛 , in the form 𝑎 = 𝑥 ∈ ℤ; 𝑥 = 𝑎 mod 𝑛 , are called the residue classes (congruence classes \ equivalence classes) modulo 𝒏 in ℤ and 𝑛 is called the modulus.  In other words, ,𝑎- is the set of all integers that are congruent to a modulo 𝑚.  We define the set ℤ𝑛 = ℤ/ 𝑛ℤ as the set containing all these classes (sets). So, for example, ℤ3 = ℤ/ 3ℤ = *0, 1, 2+. As we can see, ℤ𝑛 = ℤ/𝑛ℤ = *0, 1, 2, … , 𝑛 − 1+ has exactly 𝑛 elements.  If 𝑚 = 3 and 𝑎 = 7, we see ,7- = *𝑥: 𝑥 ≡ 7(𝑚𝑜𝑑3)+ = *… , −5, −2,1,4,7,10,13,16,19, … +.  Keeping 𝑚 = 3, we also see that 0 = 𝑥: 𝑥 ≡ 0 mod3 = … , −9, −6, −3,0,3,6,9, … ; 1 = 𝑥: 𝑥 ≡ 1 mod3 = … , −8, −5, −2,1,4,7,10, … ; ,2- = *𝑥: 𝑥 ≡ 2(mod3)+ = *… , −7, −4, −1,2,5,8,11, … +. So every integer belongs to one of the residue classes modulo 3.  Note also that ,7- = ,1-, since ,7- and ,1- are both sets containing exactly the same elements; think of ,7- and ,1- as different names for the same set. (With this perspective, each residue class has infinitely many names.) Theorem 1 For 𝑚 > 0 and any integer 𝑎 we have 𝑎 = 𝑚𝑞 + 𝑎 𝑞 ∈ 𝑍. Proof 𝑥 ∈ 𝑎 ⇔ 𝑥 ≡ 𝑎 mod𝑚 ⇔ 𝑚 ∣ 𝑥 − 𝑎 ⇔ 𝑥 − 𝑎 = 𝑚𝑞, for some 𝑞 ∈ ℤ ⇔ 𝑥 = 𝑚𝑞 + 𝑎 for some 𝑞 ∈ ℤ. So the required equation follows from the definition.  Note that the definition of ,𝑎- depends on the value of 𝑚. It would be accurate to write 𝑎 𝑚 but for simplicity, we write ,𝑎- while keeping in mind that ,𝑎- in ℤ𝑛 is different from 𝑎 in ℤ𝑚. Theorem 2 For a given modulus 𝑚 > 0, we have: ,𝑎- = ,𝑏- ⇔ 𝑎 ≡ 𝑏 mod 𝑚. Proof “⇒” Assume ,𝑎- = ,𝑏-. Note that since 𝑎 ≡ 𝑎 𝑚𝑜𝑑𝑚 , we have 𝑎 ∈ ,𝑎-. Since ,𝑎- = ,𝑏- we have 𝑎 ∈ ,𝑏-. By definition of ,𝑏- this gives 𝑎 ≡ 𝑏 mod𝑚 , as desired. “⇐” Assume 𝑎 ≡ 𝑏(mod𝑚). We must prove that the sets ,𝑎- and ,𝑏- are equal ( 𝑎 = ,𝑏-). To do this we prove that every element of ,𝑎- is in ,𝑏- and vice-versa. ( 𝑎 ⊂ 𝑏 , and 𝑏 ⊂ ,𝑎-) Let 𝑥 ∈ ,𝑎-. Then 𝑥 ≡ 𝑎(mod𝑚). Since 𝑎 ≡ 𝑏(mod𝑚), by transitivity 𝑥 ≡ 𝑏(mod𝑚), so 𝑥 ∈ ,𝑏-. Conversely, if 𝑥 ∈ ,𝑏-, then 𝑥 ≡ 𝑏(mod𝑚). By symmetry since 𝑎 ≡ 𝑏(mod𝑚), 𝑏 ≡ 𝑎(mod𝑚), so again by transitivity 𝑥 ≡ 𝑎(mod𝑚) and 𝑥 ∈ ,𝑎-. This proves that ,𝑎- = ,𝑏-. Theorem 3 For every 𝑎 there is a unique 𝑟 such that ,𝑎- = ,𝑟- and 0 ≤ 𝑟 < 𝑚. Proof Let 𝑟 = 𝑎 mod 𝑚. Note that 𝑎 mod 𝑚 is the remainder given by the Division Algorithm when 𝑎 is divided by 𝑚, hence it is clear that 0 ≤ 𝑟 < 𝑚 and also that 𝑟 ≡ 𝑎 (mod 𝑚). Since 𝑎 ≡ 𝑟(mod 𝑚) by Theorem 2, ,𝑎- = ,𝑟-. To prove that 𝑟 is unique, suppose also 𝑎 = 𝑟 ′ , where 0 ≤ 𝑟′ < 𝑚. By Theorem 2, this implies that 𝑎 ≡ 𝑟 ′ mod 𝑚. This, together with 0 ≤ 𝑟′ < 𝑚, implies by that 𝑟 ′ = 𝑎 mod𝑚 = 𝑟. Theorem 4 Given 𝑚 > 0, there are exactly 𝑚 distinct residue classes modulo m, namely, ,0-, ,1-, ,2-, … , ,𝑚 − 1-. Proof By Theorem 3, we know that every residue class ,𝑎- is equal to one of the residue classes: ,0-, ,1-, … , ,𝑚 − 1-. So there are no residue classes not in this list. These residue classes are distinct by the uniqueness part of Theorem 3, namely if 0 ≤ 𝑟1 < 𝑚 and 0 ≤ 𝑟2 < 𝑚 and ,𝑟1 - = ,𝑟2 -, then by the uniqueness part of Theorem 3 we must have 𝑟1 = 𝑟2. We now show how to define addition and multiplication of residue classes modulo m. Definition For 𝑎 , 𝑏 ∈ ℤ𝑛 , we define ,𝑎- + ,𝑏- = ,𝑎 + 𝑏- and ,𝑎-,𝑏- = ,𝑎𝑏-. For 𝑛 = 5 we have ,2- + ,3- = ,5-, and ,2-,3- = ,6-. Note that since 5 ≡ 0(mod5) and 6 ≡ 1 mod5 , we have ,5- = ,0- and ,6- = ,1-. So we can also write 2 + 3 = 0, ,2-,3- = ,1-. Definition For 𝑚 > 0, define 𝑍𝑛 = *0,1,2, … , 𝑛 − 1+ and for 𝑎, 𝑏 ∈ ℤ𝑛 𝑎 + 𝑏 = 𝑎 + 𝑏 mod𝑚, 𝑎𝑏 = 𝑎𝑏 mod𝑚, where the addition and multiplication inside the parentheses are the usual addition and multiplication of integers; what is new in our redefinition is the practice of always reducing the result modulo m. The addition and multiplication tables for ℤ4 are here: +𝟒 𝟎 𝟏 𝟐 𝟑 ×𝟒 0 𝟏 𝟐 𝟑 0 0 0 0 0 0 0 1 2 3 1 0 1 2 3 1 1 2 3 0 2 0 2 0 2 2 2 3 0 1 3 3 0 1 2 3 0 3 2 1 Example Solve the congruence 272𝑥 ≡ 901(mod9). Solution Using residue classes modulo 9, this congruence is equivalent to ,272𝑥- = ,901-, which is equivalent to ,272-,𝑥- = ,901-, which is equivalent to ,2-,𝑥- = ,1-. Now we know ,𝑥- ∈ *,0-, ,1-, … , ,8-+ so by trial and error we see that 𝑥 = 5 is a solution; actually, every integer in the residue class ,5- is a solution. Exercise 1. For any 𝑚 > 0, show that if ,𝑎- ∩ ,𝑏- ≠ ∅, then ,𝑎- = ,𝑏-. 2. For any 𝑚 > 0, show that if ,𝑎- ≠ ,𝑏- then ,𝑎- ∩ ,𝑏- = ∅. 3. If 𝑝 is a prime, show that 𝑥 2 ≡ 1(𝑚𝑜𝑑 𝑝) if and only if 𝑥 ≡ −1(mod 𝑝)or 𝑥 ≡ 1(mod 𝑝). (Hint: as part of your answer, explain why 𝑥 2 ≡ 1(mod 𝑝) implies that 𝑝|(𝑥 + 1)(𝑥 − 1) and apply Euclid’s Lemma.) 2 4. Conclude that, modulo a prime 𝑝, the congruence 𝑥 = ,1- has solutions ,𝑥- = ,1- and ,𝑥- = ,−1-. 4. Find an example of a modulus 𝑚 and a residue class ,𝑎- such that 2 𝑎 = ,1- but ,𝑎- ≠ ,1- and ,𝑎- ≠ ,−1- in ℤ𝑛. 5. Solve the congruence 544𝑥 ≡ 863(mod 7). 2 6. Compute the value of 2 ∗ 7 + 5 +5 ∗ 3 in ℤ4. 7. Compute the value of 2 ∗ 7 + 5 2 +5 ∗ 3 in ℤ7. 2 8. Compute the value of 2 ∗ 7 + 5 +5 ∗ 3 in ℤ5.