Into how many equivalences classes does $R$ partition $\mathbb{Z}$?

Question

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?

Answer 1

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.

Answer 2

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?

Answer 3

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$.

Answer 4

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

1. $x=7y+r_7(x)$ (for some $y\in\mathbb{Z}$)
2. $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.