# Finding distinct equivalence classes.

I am going through some practice questions and am having trouble to finding distinct equivalence classes and this is my understanding so far.

Let S be a nonempty subset of Z, and let R be a relation defined on $S$ by $xRy$ if $3 | (x + 2y)$.

Find the distinct equivalence classes for $S=\{−7, −6, −2, 0, 1, 4, 5, 7\}$

Now, I understand that for $3 | (x + 2y) \equiv$ $$x\equiv -2y(mod 3)$$

So that means, I would have to find combinations of elements from the set S such that $-2y$ must have a remainder $x$ when divided by 3? However for one of the solutions given, $$[5] = \{5,-7\}$$

If I am not mistaken, for $-2(5) = - 10; -2(-7) = 14$ and $$-10(mod3)=2$$ $$14(mod3)=2$$.

So, then $[2] = \{5,-7\}$ right? Or am I missing something that I don't understand. Also, from further observation, anything divided by 3 can only have remainder of 0,1 and 2. Then [5] = ... doesn't make sense. If anyone could clarify, that would be helpful! Thanks.

So that means, I would have to find combinations of elements from the set S such that $−2y$ must have a remainder $x$ when divided by $3$?

No; this means that $x$ and $-2y$ must have the same remainder when divided by $3$. For example, both $5$ and $-2(-7)$ have the remainder $2$ when divided by $3$, so $5$ and $-7$ are in the same class.

So, then $[2] = \{5,-7\}$ right?

$2$ doesn't belong to $S$, so technically the "class of $2$", which you denoted $[2]$, is meaningless in this context.

Then $[5]$ doesn't make sense

By definition, $[5]$ means "the equivalence class that contains $5$." Hopefully the above remarks make it clearer that this does makes sense.

• $[5]={x∈S: xR5}={x∈S: x≡-10(mod3)} = {x ∈ S : 3 | (x +10)} = \{5,-7\}$ Is that correct? – misheekoh Dec 15 '15 at 20:03
• @misheekoh You want to replace all your instances of $Z$ with $S$ since here $S$ is the set on which the equivalence relation is defined. So by definition $[5] = \{ x \in S : xR5 \} = \{ x \in S : 3 |(x+10) \} = \{5, -7 \}$. But you have the right idea. – Alex Provost Dec 15 '15 at 20:05
• So the idea is that for [5], the remainder of the elements in that class will have a remainder of 2 then right? – misheekoh Dec 15 '15 at 20:12
• @misheekoh Yes, because $x \equiv -10 \mod 3 \iff x \equiv 2 \mod 3$. – Alex Provost Dec 15 '15 at 21:10

It's easier if you convert $3 \mid x+2y$ to $x + 2y \equiv 0 \pmod 3$. We then "solve" for $y$ in terms of $x$. $y \equiv x \pmod 3$. In other words, $$xRy \iff x \equiv y \pmod 3$$

It helps to make a table of $s \pmod 3$ for all $s \in S$.

\begin{array}{|c|rrrrrrrr|} \hline s & −7 & −6 & −2 & 0 & 1 & 4 & 5 & 7 \\ s \pmod 3 & 2 & 0 & 1 & 0 & 1 & 1 & 2 & 1 \\ \hline \end{array}

The partition of $S$ is therefore $\big\{\{-6,0\}, \{-2,1,4,7 \}, \{-7,5\} \big\}$