Prove congruence modulo 9 is an equivalence relation. List all of the equivalence classes modulo 9. List five members of [3].

embizze | High School Teacher | (Level 1) Educator Emeritus

Posted on

Prove that congruence modulo 9 is an equaivalence relation, list all equivalence classes, and list 5 members of [3].

(1) An equivalence relation is a binary relation that is reflexive, symmetric, and transitive.

(2) Congruence modulo 9 is defined as a binary relation where `a -=b "(modn)"=>a-b=kn,kinZZ`

(3) Show congruence mod 9 is an equivalence relation:

(i) reflexive: a-a=0*9 so `a-=a`

(ii) symmetric: if `a-=b` then `a-b=9k` for some `kinZZ` . Then `b-a=-9k` so `b-=a`

(iii) transitive: if `a-=b,b-=c` then `a-b=9k => b=a-9k` ; `b-=c=>b-c=9m` ; substituting for `b` we get `a-9k-c=9m=>a-c=9m+9k=9(m+k)=>a-=c`

Therefore congruence modulo 9 is an equivalence relation.

(4) The equivalence classes are [0],[1],[2],[3],[4],[5],[6],[7],[8]

(5) Some members of [3] are -6,3,12,21,30 ** `30-=3` since 30-3=27=3*9 **