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.