Given $n \sim r \iff n \equiv r \pmod d$, prove $\sim$ is an equivalence relation.

Question

It is given that n belongs to Z and d belongs to N. How do I prove that n=r mod d defines equivalence relation?

I know I have to prove it is reflexive, symmetric and transitive. But how do I do that?

Answer 1

To prove that congruence $\mod d$ is reflexive, show that $a \equiv a \pmod d$ for all $a \in \mathbb{Z}$.

To prove that congruence $\mod d$ is symmetric, show that $b \equiv a \pmod d$ follows from $a \equiv b \pmod d$ for all $a, b \in \mathbb{Z}$.

To prove that congruence $\mod d$ is transitive, show that $a \equiv c \pmod d$ follows from $a \equiv b \pmod d$ and $b \equiv c \pmod d$ for all $a, b, c \in \mathbb{Z}$.

Can you take it from here?

Answer 2

First of all, try to understand what are you being asked. Given $n,r\in \mathbb{Z}$, it's given that $n\sim r$ iff $n\equiv r$ mod $d$,i.e., $d|(n-r)$. Now to prove reflexivity you need to show that $n\sim n$, i.e., $d|(n-n)$, which is true. For symmetric, you need to show that if $n\sim r$ then $r\sim n$, i.e. given that $d|(n-r)$, you need to show that $d|(r-n)$, which is again true. Now if you have understood that what needs to be done, then try to prove transitivity on you own.

Answer 3

To show that it is reflexive, note that $d| 0 = n - n$ .

To show that it is symmetric, note that $d|(m - n) \implies d|(n -m) = -(m - n)$.

To show that it is transitive, note that $d| (n - m) + (m - k) = (n - k)$ since a number dividing two numbers divides their sum.

By Division algorithm, there exist $q$ and $r$ such that $n = dq +r$, where $0 \leq r \leq d - 1$. Then consider this equation modulo $d$ we get $\left[n\right] = \left[r\right]$. Hence, the equivalence class is $\mathbb{Z}/d \mathbb{Z}$.