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`

Approved by eNotes Editorial Team

Videos

We’ll help your grades soar

Start your 48-hour free trial and unlock all the summaries, Q&A, and analyses you need to get better grades now.

  • 30,000+ book summaries
  • 20% study tools discount
  • Ad-free content
  • PDF downloads
  • 300,000+ answers
  • 5-star customer support
Start your 48-Hour Free Trial