While preparig for the winter exams I am doing some old exam questions, but cannot get past the following question:
Find all $0 \le a \lt 6 \in \mathbb{Z}$ where $x \in \mathbb{Z}: x^2 \equiv \text{a (mod 6)}$
I can do some trial and error solution, but pretty sure it can be done in a more fancy manner... Any help is appreciated
Note that, by the Chinese Remainder theorem, if we know what $x^2$ is equivalent to mod 2 and 3, we know what it is equivalent to mod 6. Note that $ x^2 \not\equiv -1 \pmod 3 $ but $ x^2 \equiv 0, 1 \pmod 2 $.
From here, we see that $ x^2 \equiv 0, 1, 3, 4 \pmod 6 $ are the only possible solutions.
You know that $x \equiv 0,1,2,3,4$ or $5\bmod 6$. Just check through the cases one-by-one: $$\begin{eqnarray*} 0^2 &=& 0 &\equiv& 0 \bmod 6 \\ 1^2 &=& 1 &\equiv& 1 \bmod 6 \\ 2^2 &=& 4 &\equiv& 4 \bmod 6 \\ 3^2 &=& 9 &\equiv& 3 \bmod 6 \\ 4^2 &=& 16 &\equiv& 4 \bmod 6 \\ 5^2 &=& 25 &\equiv& 1 \bmod 6 \end{eqnarray*}$$ It follows that $x^2 \equiv 0,1,3$ or $4 \bmod 6$. In particular: $x^2 \not\equiv 2$ or $5 \bmod 6$.
