1 Answer | Add Yours
Definition of congruence:
`a equiv b(mod m) <=> m|(a-b)`
`a equiv a(mod m)<=> m|(a-a) <=>m|0` which is true because 0 is divisible by any number. And that proves reflexivity
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
`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.
We’ve answered 319,199 questions. We can answer yours, too.Ask a question