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



Asked on

1 Answer | Add Yours

embizze's profile pic

Posted on (Answer #1)

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`


We’ve answered 397,466 questions. We can answer yours, too.

Ask a question