Question

Show that equivalence modulo n in Z+ is an equivalence relation.

Answer 1

Solution:

To show: Congruence modulo in Z is an equivalence relation.

Reflexive:

Given, equal numbers are congruent.

$\forall x, y, z \in \mathbb{Z}: x=y \Longrightarrow x \equiv y(\bmod z)$

so it implies that:

$\forall x \in \mathbb{Z}: x \equiv x(\bmod z)$

and so congruence modulo z is reflexive.

Symmetric:

$\begin{aligned} x & \equiv y \bmod z \\ \Rightarrow \quad x-y &=k z \\ \Rightarrow \quad y-x &=(-k) z \\ \Rightarrow y & \equiv x \bmod z \end{aligned}$

So congruence modulo z is symmetric.

Transitive:

$\begin{aligned} x_{1} & \equiv x_{2} \quad(\bmod z) \\ x_{2} & \equiv x_{3} \quad(\bmod z) \\ \left(x_{1}-x_{2}\right) &=k_{1} z \end{aligned}$

$\begin{aligned} \wedge &\left(x_{2}-x_{3}\right)=k_{2} z \\ \Rightarrow &\left(x_{1}-x_{2}\right)+\left(x_{2}-x_{3}\right)=\left(k_{1}+k_{2}\right) z \\ \Rightarrow &\left(x_{1}-x_{3}\right)=\left(k_{1}+k_{2}\right) z \end{aligned} x_{1} \equiv x_{3} \quad(\bmod z)$

$\Rightarrow x_{1} \equiv x_{3} \quad(\bmod z)$

So congruence modulo z is transitive.

Thus, it is an equivalence relation.

Hence, proved.