Equivalence relations

Question

Let n > 1 be an integer. Let $\equiv$ be the congruence relation modulo n on integer. Prove that $\equiv$ is an equivalence relation on $\mathbb{Z}$. I understand you would prove if it is reflexive, symmetric and transitive. But not sure how to approach this.

Answer 1

We have to show that congruence $\equiv$ is reflexive, symmetric, and transitive.

Reflexive: $$ x \equiv x \ ({\rm mod}\ m) $$ (Two equal numbers $x$ and $x$ give the same remainder when divided by $m$.)

Symmetric: $$ x \equiv y \ ({\rm mod}\ m) \qquad\Leftrightarrow\qquad y \equiv x \ ({\rm mod}\ m) $$ ($x$ and $y$ give the same remainder $\Leftrightarrow$ $y$ and $x$ give the same remainder when divided by $m$.)

Transitive: $$ x \equiv y \ ({\rm mod}\ m) \quad\mbox{and}\quad y \equiv z \ ({\rm mod}\ m) \qquad\Rightarrow\qquad x \equiv z \ ({\rm mod}\ m). $$ ($x$ and $y$ give the same remainder, $y$ and $z$ give the same remainder $\ \Rightarrow\ $ $x$ and $z$ give the same remainder.)

Answer 2

x≡ y (mod n) if and only if x- y is a multiple of n, x- y= kn for some integer k.

A relation, R, is "reflexive" if and only xRx for all x in the set. For any integer x, x- x= 0= 0n so this relation is reflexive.

A relation, R, is "symmetric" if and only if whenever xRy then yRx. If x≡ y then x- y= kn. In that case, y- x= -(x- y)= -kn= (-k)n so this relation is symmetric.

A relation, R, is "transitive if and only if whenever xRy and yRz then xRz. If xRy then x- y= kn. If yRz then y- z= jn. Then x- z= (x- y)- (y- z)= kn- jn= (k- j)n so this relation is transitive.