See also the version of this post on Blogger at https://explaining-maths.blogspot.com/2021/07/squares-modulo-k.html where the maths (using MathJax) looks a bit clearer.
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 (where is a positive integer which, in this module, is usually relatively small).
My response
Hi,
Squares modulo , 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 ).
Now let’s look at squares modulo .
The idea here is to find out for which integers it is possible to solve (with an integer ) the congruence
But we only need to investigate , because every integer is congruent to (exactly) one of those modulo .
We also only need to check , for the same reason. One way to think about this is that, by the division algorithm, for each integer , we have for some integer and some . Then is congruent to modulo , and so is congruent to modulo . So, once we have checked , all the other squares of integers are just repeats of those modulo .
Another way to think about this, since we are taking an even power (squaring), is that if then , so there is no need to check negative integers. Then we should check modulo . But then the repeats start, because , , etc. modulo .
However there is a further short cut, again because we are looking at an even power.
We have and modulo . As a result, squaring or will also just give us repeats (modulo ) of what we got by squaring and .
As a quick check modulo , and modulo , which is what we expected.
Because of this, we only need to check the values of , , and modulo .
To answer this question, we just have to check these four squares modulo , and explain that all other squares of integers are repeats of these modulo !
Still, let’s make a slightly larger table than necessary just to make sure that this fits with what really happens.
As expected, we see a repeating pattern in the third row, and, as expected, we only needed to check , , and modulo . The rest are just repeats.
No matter which integer you try, is always congruent to one of , , or modulo , and is never congruent to or modulo .
The answer to the question is that , , and are squares modulo , and and are not squares modulo .
For the justification: you just check , , and . (If in doubt, check and too.) Then just say that all other squares are repeats of these modulo . You don’t have to give all of my more detailed explanation above (though saying something about and 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 !
Best wishes,
Dr Feinstein
One thought on “Squares modulo k”