1

Let A = {−6, −5, −4, −3, −2, −1, 0, 1, 2, 3, 4} and define a relation R on A as follows: For all m, n is in Z,

$m R n ⇔ 3|(m^2 − n^2)$ It is a fact that R is an equivalence relation on A. Use set-roster notation to list the distinct equivalence classes of R.

I believe I can go through each element and find all the pairs that satisfy $3|m^2-n^2$, however, this seems like it will take a while. I know I just have to find $3|(m-n)$ or $3|(m+n)$, but this still doesn't seem like the best method. What is the most efficient way of doing this?

Scott Adamson
  • 241
  • 1
  • 8

2 Answers2

1

$m,n$ belong to the same equivalence class iff $m^2\equiv_3n^2$ i.e. $m^2,n^2$ belong to the same equivalence class with respect to modulo $3$ relation. So simply square all the elements in $A$ and form classes of the squares according to modulo $3$ relation. Then simply replace each square number by the original element in each class.

Edit: In effect, replace each element of $A$ by the non-negative remainder its square leaves when divided by $3$.

$$\begin{align*}A&=\{-6,-5,-4,-3,-2,-1,0,1,2,3,4\}\\ B&=\{~~~0,~~~1,~~~1,~~~0,~~~1,~~~~1,0,1,1,0,1\}\end{align*}$$

Now two elements of $A$ belong to the same equivalence class iff they have the same $B$ values i.e. just group the elements with $B$ value $1$ and $0$ in two equivalence classes.$$E_1=\{-6,-3,0,3\},E_2=A-E_1$$

Shubham Johri
  • 17,659
0

Your goal is to find representatives of each equivalence class. Write $m=3k+r$ where $r\in\{0,1,2\}$. If $r=0$, then $n\equiv 0\pmod{3}$ is equivalent to $m$. So the first representative is $\{r=0\}$.

If $r=1$, then $n\equiv 1,2\pmod{3}$ are equivalent to $m$, so the next representative is $\{r=1\}$.

Since equivalence is reflexive, we don't need to consider $r=2$.

Alex R.
  • 32,771