Note 4 for MATH 300 at UMass
Note 4 for MATH 300 at UMass
Popular in Course
Popular in Department
This 6 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 13 views.
Reviews for Note 4 for MATH 300 at UMass
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
Math 300 Fall 2008 Note 4 Zhigang Han7 Urnass at Amherst 1 Congruences 11 Congruence Def 1 Let m be a xed positive integer7 011 6 Z If mla E b7 we say a is congruent to b modulo m 7 and write a E 1 mod m If m l a E b7 we say a is not congruent to b modulo m 7 and write LEI modm Rink aEb modmifandonlyifabkmforsomekEZ Eg 1 77E37 mod 107 and 7737410 Prop 1 Let a7 90 E Z Then i a E a mod m ii lfa E 1 mod m7 then b E a mod m iii If a E 1 mod m7 and b E 0 mod m7 then a E 0 mod m Prop 2 Let a E a mod m and b E 13 mod m Then i abEab mod m ii aEbEaEb mod m iii a I E 01 13 mod m Rink Using iii7 one can easily show that if a E 1 mod m7 then a E 1 mod m for all n E N Eg 3 Show that 32 E 2 mod 7 for all n E N Rink Another corollary is that if a E 1 mod m then ac E be mod m The converse however does not hold in general For instance 9 5 E 5 5 mod 10 but 9 E 5 mod 10 Module Cancellation law If ac E be mod m and gcdc m 1 then a E 1 mod m Eg2 95E55 mod4andgcd541soQE5 mod4 Prop 3 a E 1 mod m if and only if a and b have the same remainders when divided by m Rink This implies that every integer must be congruent precisely to one of012 mE 1 modulo m Eg 4 What day is 22008 days from today Tests for Divisibility i A number is divisible by 9 if and only ifthe sum of its digits is divisible by 9 ii A number is divisible by 3 if and only if the sum of its digits is divisible by 3 iii A number is divisible by 11 if and only if the alternating sum of its digits is divisible by 11 12 Equivalence Relations Def 1 A relation on a set A is a subset S of A x A We say a is related to b7 and write aRb7 if 11 6 S We say a is not related to b7 and write a 1 if 11 S Eg 1 Examples of Relations i Greater Than Let A R and Sab E R x R10 gt 1 Then aRb means a gt 1 ii Divisibility Let A Z and Sa7 b E Z x Z l a divides 1 Then aRb means all iii Equality Let A be any set7 and Saa la 6 A C A x A Then aRb means a 1 iv Congruence modulo m For 071 6 Z7 aRb when a E 1 mod m Def 2 Let R be a relation on a set A i R is symmetric if aRb implies 131 ii R is transitive if aRb and bRc implies aRc iii R is re exive if aRa for all a E A Def 3 An equivalence relation on a set A is a relation R which is symmetric7 transitive and re exive Rmk When R is an equivalence relation7 we also say a is equivalent to b if aRb Eg 2 iii and iv in Eg 1 are equivalence relations7 while and ii are not Eg 3 Let R be a relation on R such that aRb if and only if ail E Q Show that R is an equivalence relation Def 4 Let R be an equivalence relation on a set A The equivalence class of a7 denoted by a7 is the subset of A consisting of all elements in A that are equivalent to a That is7 a m E AlzRa The element a is called a representative of the equivalence class a Eg 4 Let R be the relation of congruence modulo 2 Then 0 95 9520 mod 2 7472024 1 95 9521 mod 2 7371135 2 95 9522 mod 2 7472024 In fact there are only two distinct equivalence classes even integers and odd integers Any even number is a representative of 0 and any odd number is a representative of And every integer lies in exactly one congruence class Prop 4 Let R be an equivalence relation on a set A If a b E A then i a E a ii a b if and only if aRb iii a O b 0 if and only if a 1 Rink This proposition says that two equivalence classes under any equiv alence relation R are either identical or disjoint and the set of equivalence classes gives a disjoint decomposition of A as A A1 U A2 U U Ak which is called a partition of A Eg 5 Let R be a relation on A 1 2 34 such that aRb if and only if a E 1 mod 2 Show that R is an equivalence relation Then there are two distinct equivalence classes 1 1 3 and 2 2 4 which gives a partition of A as A 13 U 24 13 Modulo Arithmetic Def 5 The congruence class modulo m of the integer a is the set of integers a zEZlmEa modm The set of congruence classes of integers under the congruence relation modulo m is called the set of integers modulo m and is denoted by Zm That is 2m 0 1H21 me 1 Def 6 Modular Arithmetic Let a b E Zm We de ne the addition and the multiplication on Zm by a b a b and a 1 ab Rmk Since these operations are de ned in terms of representatives we need to show that these operations are well de ned That is the de nition is independent of the choice of representatives Show it Rmk 1 The neutral element for in Zm is 0 in the sense that 0 a a 0 a for all a E Zm The neutral element for in Zm is 1 in the sense that 1 a a 0 a for all a E Zm Eg 6 Write the addition and multiplication table for Z4 and Z5 Def 7 Let a E Zm An element 1 E Zm is called an additive inverse or a negative of a if a b b a Rmk There exists a unique additive inverse for each a E Zm In fact the negative of a is 7a Def 8 Let a E Zm be a nonzero element An element 1 E Zm is called an multiplicative inverse or simply an inverse of a if a 1 1 a Rmk The multiplicative inverse does not necessarily exist For instance 2 E Z4 does not have an inverse Prop a E Zm has an inverse if and only if gcda m 1 The inverse is unique Cor Let p be a prime Then every nonzero element a E 217 has a unique inverse Rink To nd the inverse of a in 217 one needs to solve a This means ax E 1 mod 197 which is equivalent to axpy 1 The last equation can be solved by extended Euclidean algorithm Eg 7 Find the inverse of 4 in 213 Fermat7s little Theorem Let p be a prime which does not divide a E Z Then ap l E 1 mod p Cor 1 Let p be a prime Then a E a mod p for all a E Z Cor 2 Let p be a prime Then every nonzero element a 6 217 has an inverse Rink One can de ne the subtraction in Zm using the negative7 namely7 one de ne a minus 1 to be a plus the negative of Rink lfp is a prime7 one can de ne the division in 217 using the inverse7 namely7 one de ne a divide b to be a times the inverse of ln fact7 instead of calling it a division we often directly mention it as multipli cation by the inverse77 in advanced mathematics such as the group theory
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'