1. The relation 'congruence modulo m' is % 

(i) Reflexive only  (ii) Transitive only  (iii) Symmetric only  (iv) An equivalence relation

Expert Answers

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

Definition of congruence:

`a equiv b(mod m) <=> m|(a-b)`

(i) Reflexivity

`a equiv a(mod m)<=> m|(a-a) <=>m|0` which is true because 0 is divisible by any number. And that proves reflexivity

(ii) Transitivity

If `a equiv b(mod m)` and `b equiv c(mod m)`, then `m|(a-b)` and `m|(b-c)` which means that `m|((a-b)+(b-c))`. So `m|(a-c)` hence `a equiv c(mod m)` which proves transitivity

(iii) Symmetry

`a equiv b(mod m)<=>m|(a-b)<=>m|-(b-a)<=>m|(b-a)<=>b equiv a(mod m)`

And that proves symmetry.

Now by definition equivalence relation is reflexive, transitive and symmetric and since we have proven all three of these properties that means congruence modulo m is an equivalence relation.

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