What is equivalence relation? Prove that relation 'congruence modulo' ( ≡mod m) is an equivalence relation.
Ans: A relation R illustrated on a nonempty set A is said to be an equivalence relation if R is Reflexive, Symmetric and Transitive on A.
Any integer x is said to 'congruence modulo m' other integer y, if both x and y yield similar remainder while divided by m. Let R be the relation 'congruence modulo m' over set of integers Z.
Reflexivity: Let x ∈ Z be any integer, after that x ≡m x since both yield similar remainder while divided by m. Thus, (x, x) ∈ R ∀ x ∈ Z. This proves that R is a reflexive relation.
Symmetry: Let x and y be any two integers and (x, y) ∈ R. This depicts that x ≡m y and hence y ≡m x. So, (y, x) ∈ R. Therefore R is a symmetric relation also.
Transitivity: Let x, y and z be any three elements of Z like (x, y) and (y, z) ∈ R. So, we have x ≡3y and y ≡mz. It defines that (x-y) and (y-z) are divisible by m. Hence, (x - y) + (y - z) = (x - z) is as well divisible by m i.e. x ≡m z. Therefore, (x, y) and (y, z) ∈ R ⇒ (x, z) ∈ R. Thus R is a transitive relation.
Hence, R is an equivalence relation.