Homework Help

Prove the congruence modulo n is an equivalent relation on the set of integers.

user profile pic

eric82275 | eNoter

Posted August 31, 2013 at 10:13 PM via web

dislike 1 like

Prove the congruence modulo n is an equivalent relation on the set of integers.

1 Answer | Add Yours

user profile pic

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

Posted September 1, 2013 at 2:09 AM (Answer #1)

dislike 0 like

To show that congruence modulo n is an equivalence relation, we must show that it is reflexive, symmetric, and transitive.

Note: `a -=b ("mod"n) ==> n|a-b` (If a is congruent modulo n to b, then their difference is a multiple of n.)

(1) Reflexive `a-=a("mod"n)` since a-a=0 is a multiple of any n.

(2) Symmetric `a-=b("mod"n) => b-=a("mod"n)`

`a-=b==>n|a-b==>n|b-a ==> b-=a`

Ex. `2-=7("mod"5)` since `5|(2-7)=-5` and `7-=2("mod"5)` since `5|(7-2)=5`

(3) Transitive: `a-=b,b-=c ==> a-=c`

`a-=b==>n|a-b` `b-=c ==> n|b-c`

`n|((a-b)+(b-c))==>n|a-c==>a-=c`

Join to answer this question

Join a community of thousands of dedicated teachers and students.

Join eNotes