Congruence and Congruence Classes

1 LECTURE 11 Congruence and Congruence relation on a setSis a rule or test applicable to pairs of elementsofSsuch that(i)a a , a S(reflexive property)(ii)a b b a(symmetric property)(iii)a bandb c a c(transitive property).You should think of an equivalence relation as a generalization of the notion of equality. Indeed, the usualnotion of equality among the set of integers is an example of an equivalence relation. The next definitionyields another example of an equivalence , b, n Zwithn >0. Thenaiscongruent tobmodulon;a b(modn)provided thatndividesa 5 (mod 6)The following theorem tells us that the notion of Congruence defined above is an equivalence relation on theset of a positive integer. For alla, b, c Z(i)a a(modn)(ii)a b(modn) b a(modn)(iii)a b(modn)andb c(modn) a c(modn).Proof.(i)a a= 0 andn|0, hencea a(modn).(ii)a b(modn) means thata b=nkfor somek Z.

2 Therefore,b a= nk=n( k); henceb a(modn).(iii) Ifa b(modn) andb c(modn), thena b=nkb c=nk .Adding these two equations yieldsa c=n(k+k ) ;and soa c(modn). 3811. Congruence AND Congruence b(modn)andc d(modn), then(i)a+c b+d(modn)(ii)ac bd(modn).Proof.(i) By the definition of Congruence there are integerssandtsuch thata b=snandc d=tn. Therefore,a b+c d=sn+tn=n(s+t)or, addingb+dto both sides of this equation,a+c=b+d+n(s+t).Hence,a+c b+d(modn).(ii) Using the fact that bc+bc= 0 we haveac bd=ac+ 0 bd=ac+ ( bc+bc) bd=c(a b) +b(c d)=c(sn) +b(tn)=n(cs+bt)and son|(ac bd). Hence,ac bd(modn). integers withn >0. Thecongruence class ofamodulon, denoted[a]n, is the set of all integers that are congruent toamodulon; ,[a]n={z Z|a z=knfor somek Z}.Example:In Congruence modulo 2 we have[0]2={0, 2, 4, 6, }[1]2={ 1, 3, 5, 7, }.Thus, the Congruence Classes of 0 and 1 are, respectively, the sets of even and odd Congruence modulo 5 we have[3]5={3,3 5,3 10,3 15, }={ , 12, 7, 2,3,8,13,18, }.

3 C(modn) if and only if[a]n= [c] c(modn). Letb [a]n. Then by definitionb a(modn). By the transitivity property ofcongruence we then havea b(modn) anda c(modn) b c(modn).Sob [c]n. Thus, any elementbof [a]nis also an element of [c]n. Reversing the roles ofaandcin theargument above we similarly conclude that any element of [c]nis also an element of [a]n. Therefore[a]n= [c] Congruence AND Congruence CLASSES40 Conversely, suppose [a] = [c]. Sincea a(modn), by the reflexive property of Congruence , we havea [a]and so, since by hypothesis [a] = [c],a [c]. Hence,a c(modn). Recall that ifAandCare arbitrary sets, there are in general three possibilities:(i)A C6= andA=C(ii)A C6= andA6=C(iii)A C= .In the last case we say that the setsAandCaredisjoint. The following corollary says that for congruenceclases the immediary case (ii) does not Congruence Classes modulonare either disjoint or [a]nand [b]nare disjoint there is nothing to prove.

4 Suppose then that [a]n [b]n6= . Then there is anintegerbsuch thatb [a]nandb [c]n. Sob a(modn) andb cmodn). By the symmetry andtransitivity properties of Congruence we then havea c(modn).Hence [a]n= [c]nby Theorem are exactlyndistinct Congruence Classes modulon; namely,[0]n,[1]n,[2]n,..,[n 1] first show that no two of 0,1,2, .. , n 1 are congruent modulon. To see this, suppose that0 s < t < n .Thent sis a positive integer andt s < n. Thus,ndoes not dividet sand sotis not congruent tosmodulon. Since no two of 0,1,2, .. , n 1 are congruent, the Classes [0]n,[1]n, .. ,[n 1]nare all distinct,by Theorem complete the proof we need to show that every Congruence class is one of these Classes . Leta Z. Bythe Division Algorithm,( )a=nq+ror with 0 r < n. The condition onrimpliesr {0,1,2, .. , n 1}. If we rewrite ( ) asa r=nqit is clear thata r(modn).

5 Thus, any integerais congruent modulonto somer {0,1,2, .. , n 1}. set of all Congruence Classes modulonis denotedZn(which is read Zmodn ).Thus,Zn={[0],[1],[2], .. ,[n 1]}.Note that while the setZ={.. , 3, 2, 1,0,1,2,3, ..}has an infinite number of elements, the setZnhas onlynelements. Note also that the individual elementsofZnare not integers, but rather infinte sets of integers; ,[2] ={.. ,2 3n,2 2n,2 n,2,2 +n,2 + 2n,2 + 3n, ..}.11. Congruence AND Congruence CLASSES41We proved last time that Congruence modulonis an equivalence relation; ,(i)a a(modn)(ii)a b(modn) b a(modn)(iii)a b(modn) andb c(modn) a c(modn),and that Congruence modulonalso is compatible with the addition and multiplication of b(modn)andc d(modn), then(i)a+c b+d(modn)(ii)ac bd(modn). integers withn >0. Thecongruence class ofamodulon, denoted[a], is the set of all integers that are congruent toamodulon; ,[a] ={z Z|a z=knfor somek Z}.

6 Example:In Congruence modulo 2 we have[0]2={0, 2, 4, 6, }[1]1={ 1, 3, 5, 7, }.Thus, the Congruence Classes of 0 and 1 are, respectively, the sets of even and odd Congruence modulo 5 we have[3] ={3,3 5,3 10,3 15, }={ , 12, 7, 2,3,8,13,18, }. c(modn) if and only if[a]n= [c] c(modn). Letb [a]. Then by definitionb a(modn). By the transitivity property ofcongruence we then havea b(modn) anda c(modn) b c(modn).Sob [c]n. Thus, any elementbof [a]nis also an element of [c]. Reversing the roles ofaandcin theargument above we similarly conclude that any element of [c]nis also an element of [a]n. Therefore[a] = [c].Conversely, suppose [a] = [c]. Sincea a(modn), by the reflexive property of Congruence , we havea [a]and so, since by hypothesis [a] = [c],a [c]. Hence,a c(modn). Recall that ifAandCare arbitrary sets, there are in general three possibilities:(i)A C6= andA=C(ii)A C6= andA6=C(iii)A C=.

7 In the last case we say that the setsAandCaredisjoint. The following corollary says that for congruenceclases the immediary case (ii) does not Congruence Classes modulonare either disjoint or Congruence AND Congruence [a]nand [b]nare disjoint there is nothing to prove. Suppose then that [a]n [b]n6= . Then there is anintegerbsuch thatb [a]nandb [c]n. Sob a(modn) andb cmodn). By the symmetry andtransitivity properties of Congruence we then havea c (modn).Hence [a]n= [c]nby Theorem are exactlyndistinct Congruence Classes modulon; namely, [0], [1], [2],..,[n-1]. first show that no two of 0,1,2, .. , n 1 are congruent modulon. To see this, suppose that0 s < t < n .Thent sis a positive integer andt s < n. Thus,ndoes not dividet sand sotis not congruent tosmodulon. Since no two of 0,1,2, .. , n 1 are congruent, the Classes [0]n,[1]n.

8 ,[n 1]nare all distinct,by Theorem complete the proof we need to show that every Congruence class is one of these Classes . Leta Z. Bythe Division Algorithm,( )a=nq+ror with 0 r < n. The condition onrimpliesr {0,1,2, .. , n 1}. If we rewrite ( ) asa r=nqit is clear thata r(modn). Thus, any integerais congruent modulonto somer {0,1,2, .. , n 1}. set of all Congruence Classes modulonis denotedZn(which is read Zmodn ).Thus,Zn={[0]n,[1]n,[2]n, .. ,[n 1]n}.Note that while the setZ={.. , 3, 2, 1,0,1,2,3, ..}has an infinite number of elements, the setZnhas onlynelements. Note also that the individual elementsofZnare not integers, but rather infinte sets of integers; ,[2]n={.. ,2 3n,2 2n,2 n,2,2 +n,2 + 2n,2 + 3n, ..}.