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

Expert Answers

An illustration of the letter 'A' in a speech bubbles

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`

See eNotes Ad-Free

Start your 48-hour free trial to get access to more than 30,000 additional guides and more than 350,000 Homework Help questions answered by our experts.

Get 48 Hours Free Access
Approved by eNotes Editorial

Videos