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

*print*Print*list*Cite

Expert Answers

embizze | Certified Educator

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`