Complete representative set of squares modulo $15$.

Question

$2.\,\,$Do the following computations.

$\text{(a)}$ Solve the equation $x^2\equiv 1\mod15$

Solution:
We only need to choose a complete representative set modulo $15$ and verify the equation over such a set. In the following table, we choose the representative set $$\{0,\pm1,\pm2,\pm3,\pm4,\pm5,\pm6,\pm7\}$$ and verify the equation as follows: $$ \begin{array}{c|c} x & 0 & \pm 1 & \pm 2 & \pm 3 & \pm 4 & \pm 5 & \pm 6 & \pm 7 \\ \hline x^2 & 0 & 1 & 4 & -6 & 1 & -5 & 6 & 4 \\ \end{array} $$

We see that the equation has four solutions: $\pm1$ and $\pm 4$.

(Note that $15$ is not a prime, so we do not just have two square roots!)

I understand that if you do $8^2 \mod 15 $, $9^2 \mod 15$, $10^2 \mod 15$, and so forth, you get repetitions of the above representative set. What I don't understand is how you could know this before doing those calculations manually.

Answer 1

If you really wanted to, you could choose the set $\{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\}$, but notice that $8 \equiv -7 \mod 15$, $9 \equiv -6 \mod 15$, etc. So then it is more convenient to choose the representative set $\{0, \pm 1, \pm 2, \pm 3, \pm 4, \pm 5, \pm 6, \pm 7\}$. This cuts down the amount of work from $15$ computations to $8$, as clearly $a^2 \equiv (-a)^2$.

Answer 2

The set $\{1,2,3,...n-1\}$ is called complete residue set for number $n$. And all conguence relation modulo $n$ can be reduced to elements of this set.

Now for your question you can write $24$ as $(15 + 9)$ so $24^2 \equiv (15 + 9)^2 \equiv 15^2 + 270 + 9^2 \equiv 9^2 \pmod {15}$

And you need to check only the first $\frac{n}{2}$ numbers because we have: $9\equiv-6 \pmod{15}$ Now square and you'll get $(-6)^2 \equiv 6^2 \equiv 36 \pmod {15}$$