Into how many equivalences classes does $R$ partition $\mathbb{Z}$? Let $R= \{ (a,b) \in\mathbb{Z}\times\mathbb{Z} \mid a^2\equiv b^2 \bmod 7\}$.
Into how many equivalences classes does $R$ partition $\mathbb{Z}$?
My best guess is that there are $7$ equivalence classes: $a^2-b^2$ has remainder $0 \bmod 7$, $a^2-b^2$ has remainder $1 \bmod 7$, $a^2-b^2$ has remainder $2 \bmod 7, \ldots, a^2-b^2$ has remainder $6 \bmod 7$.
Am I misunderstanding equivalence class partitions?
 A: The fact that $7$ is prime is relevant here.  A number can have more than two square roots modulo a composite number, but modulo a prime number, each number can have only two square roots.  Thus $a\equiv b\bmod 7$ if and only if $a\equiv\pm b\bmod 7$.
\begin{align}
0^2 & \equiv (-0)^2 \equiv 0 \\
1^2 & \equiv (-1)^2 \equiv 1 \\
2^2 & \equiv (-2)^2 \equiv 4 \\
3^2 & \equiv (-3)^2 \equiv 2
\end{align}
Since the only congruence classes modulo $7$ are $0,\pm1,\pm2,\pm3$, this list is complete.  There are $7-1$ non-zero congruence classes and hence $(7-1)/2$ non-zero squares.  Each non-zero square coresponds to one of the equivalence classes you're looking for, $0$ corresponds to another.
A: HINT: If $a\mathrel{R}b$, then $a^2-b^2$ has remainder $0$ on division by $7$, and you’re not interested in any other value of $(a^2-b^2)\bmod7$. Perhaps you meant that $a^2$ can have remainder $0,1,2,3,4,5$, or $6$, and that each of those corresponds to a different equivalence class. If that’s what you meant, your understanding of the equivalence classes is correct, but your answer isn’t: some of those seven numbers are not possible remainders of $a^2$ on division by $7$. Which ones actually are?
A: You have $a^2\equiv b^2 \bmod 7$ so you should only be interested in whether $a^2-b^2\equiv 0$.
HINT: Here you can factorise as usual as $a^2-b^2=(a+b)(a-b)$ and say that since the left-hand side is divisible by $7$, and $7$ is prime, one of the factors on the right-hand side must be divisible by $7$. Don't forget the case where both are divisible by $7$.
A: Let $r_7\colon \mathbb{Z}\to\mathbb{Z}$ be the function that associates to every integer $x\in\mathbb{Z}$ the remainder of the division of $x$ by $7$, that is, the unique number $r_7(x)$ such that


*

*$x=7y+r_7(x)$ (for some $y\in\mathbb{Z}$)

*$0\le r_7(x)<7$


Another common notation is $r_7(x)=x\bmod 7$.
Then you can also consider the function $f\colon\mathbb{Z}\to\mathbb{Z}$ defined by
$$
f(a)=r_7(a^2)
$$
and your equivalence relation can be described as
$$
R=\{(a,b)\in\mathbb{Z}\times\mathbb{Z}\mid f(a)=f(b)\}
$$
It is well known that there is a unique mapping $\tilde{f}\colon\mathbb{Z}/R\to\mathbb{Z}$ such that
$$
f=\tilde{f}\circ\pi
$$
where $\pi\colon\mathbb{Z}\to\mathbb{Z}/R$ is the canonical projection to the quotient set. Such a mapping is injective and has the same image as $f$, so $|\mathbb{Z}/R|$ is the same as the cardinality of the image of $f$. This image can be described very easily, because
$$
f(a)=r_7(a^2)=r_7\bigl((r_7(a))^2\bigr)=(r_7(a))^2\bmod 7
$$
and so the possible values are $0^2\bmod7=0$, $1^2\bmod7=1$, $2^2\bmod7=4$, $3^2\bmod7=2$, $4^2\bmod7=2$, $5^2\bmod7=4$, $6^2\bmod7=1$. Thus the image of $f$ is $\{0,1,2,4\}$.
Note that this is essentially independent of the modulus: the computation would be exactly the same for any modulus. The key point is that
$$
xy \bmod n = ((x \bmod n)(y\bmod n))\bmod n
$$
which follows from the known property of congruences.
