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