Squares modulo k

This post was first published on WordPress at
https://explainingmaths.wordpress.com/2021/07/25/squares-modulo-k/

Here is another post from my introductory pure maths Piazza forum from autumn 2020. This time I was asked how we determine, in general, which integers are squares modulo $k$ (where $k$ is a positive integer which, in this module, is usually relatively small).

My response

Hi,
Squares modulo $k$, also known as quadratic residues, are the subject of the famous law of quadratic reciprocity, proved by Gauss. See https://en.wikipedia.org/wiki/Quadratic_reciprocity for more on that. We had a look at some special cases in Workshop 6 and Workshop 7 (where we also looked at fourth powers modulo $k$).

Now let's look at squares modulo $6$.

The idea here is to find out for which integers $a$ it is possible to solve (with an integer $n$) the congruence

          $n^2 \equiv a~~~ (\textrm{mod}~6)\,.$

But we only need to investigate $a \in \{0,1,2,3,4,5\}$, because every integer is congruent to (exactly) one of those modulo $6$.

We also only need to check $n \in \{0,1,2,3,4,5\}$, for the same reason. One way to think about this is that, by the division algorithm, for each integer $n$, we have $n =q \times 6 + r$ for some integer $q$ and some $r \in \{0,1,2,3,4,5\}$. Then $n$ is congruent to $r$ modulo $6$, and so $n^2$ is congruent to $r^2$ modulo $6$. So, once we have checked $0^2, 1^2,\dots, 5^2$, all the other squares of integers are just repeats of those modulo $6$.

Another way to think about this, since we are taking an even power (squaring), is that if $n<0$ then $n^2=(-n)^2$, so there is no need to check negative integers. Then we should check $0^2, 1^2,\dots, 5^2$ modulo $6$. But then the repeats start, because $6 \equiv 0$, $7 \equiv 1$, $8 \equiv 2$ etc. modulo $6$.

However there is a further short cut, again because we are looking at an even power. We have $5 \equiv -1$ and $4 \equiv -2$ modulo $6$. As a result, squaring $5$ or $4$ will also just give us repeats (modulo $6$) of what we got by squaring $1$ and $2$. As a quick check $5^2=25 \equiv 1 = (-1)^2=1^2$ modulo $6$, and $4^2=16 \equiv 4 = (-2)^2 = 2^2$ modulo $6$, which is what we expected. Because of this, we only need to check the values of $0^2$, $1^2$, $2^2$ and $3^2$ modulo $6$.

To answer this question, we just have to check these four squares modulo $6$, and explain that all other squares of integers are repeats of these modulo $6$! Still, let's make a slightly larger table than necessary just to make sure that this fits with what really happens.

$n$	$-2$	$-1$	$0$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$n^2$	$4$	$1$	$0$	$1$	$4$	$9$	$16$	$25$	$36$	$49$	$64$	$81$	$100$
$n^2~~(\textrm{mod}~6)$	$4$	$1$	$0$	$1$	$4$	$3$	$4$	$1$	$0$	$1$	$4$	$3$	$4$

As expected, we see a repeating pattern in the third row, and, as expected, we only needed to check $0^2$, $1^2$, $2^2$ and $3^2$ modulo $6$. The rest are just repeats. No matter which integer $n$ you try, $n^2$ is always congruent to one of $0$, $1$, $3$ or $4$ modulo $6$, and is never congruent to $2$ or $5$ modulo $6$.

The answer to the question is that $0$, $1$, $3$ and $4$ are squares modulo $6$, and $2$ and $5$ are not squares modulo $6$.

For the justification: you just check $0^2$, $1^2$, $2^2$ and $3^2$. (If in doubt, check $4^2$ and $5^2$ too.) Then just say that all other squares are repeats of these modulo $6$. You don't have to give all of my more detailed explanation above (though saying something about $4^2$ and $5^2$ is worth doing). But you must make sure that you check enough values that all other squares really are just repeats of the values you have already found modulo $6$!

Best wishes,

Dr Feinstein