# Finding the equivalence classes if $\left\{ (x,y)\,:\,x\equiv y\mod5\right\}$

I have the following relation $$R\subseteq\mathbb{N}\times\mathbb{N}$$: $$R=\left\{ (x,y)\,:\,x\equiv y\mod5\right\}$$ I have proved that $$R$$ is a equivalence relation. I would like to find the equivalence classes. As I understand the classes are $$[i]$$ where $$i\in \{0,\ldots,4\}$$. I'm struggling of proving it formally. Is it possible to show how to prove it formally?

• For you, is $0$ an element of $\mathbb N$? Dec 28 '19 at 20:27
• @JoséCarlosSantos Yes Dec 28 '19 at 20:30

You have to show that these classes are disjoint and their union is the set of natural numbers. Make sure to chose $$5$$ instead of $$0$$ as the representative of that class.

Yes, it is correct. If $$x\in\mathbb N$$, then let $$r_x$$ be the remainder of the division of $$x$$ by $$5$$. Then:

1. $$r_x\in\{0,1,2,3,4\}$$;
2. $$x\equiv r_x$$.

Furthermore, if $$i,j$$ are distinct elements of $$\{0,1,2,3,4\}$$, then $$i\not\equiv j$$.

It can be proved that an equivalence relation partitions the set it's defined on.

In this case, the equivalence classes partition $$\Bbb N$$ into $$5$$ equivalence classes. For each $$n\in\Bbb N$$, $$\exists! k\in\{0,1,2,3,4\}$$ such that $$n=k+5l$$ for some $$l$$.

This is the result of Euclidean division.