**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 ≡_{m}z. 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.