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

          n2a   (mod 6).

But we only need to investigate a{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{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×6+r for some integer q and some r{0,1,2,3,4,5}. Then n is congruent to r modulo 6, and so n2 is congruent to r2 modulo 6. So, once we have checked 02,12,,52, 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 n2=(n)2, so there is no need to check negative integers. Then we should check 02,12,,52 modulo 6. But then the repeats start, because 60, 71, 82 etc. modulo 6.

However there is a further short cut, again because we are looking at an even power. We have 51 and 42 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 52=251=(1)2=12 modulo 6, and 42=164=(2)2=22 modulo 6, which is what we expected. Because of this, we only need to check the values of 02, 12, 22 and 32 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
n2 4 1 0 1 4 9 16 25 36 49 64 81 100
n2  (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 02, 12, 22 and 32 modulo 6. The rest are just repeats. No matter which integer n you try, n2 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 02, 12, 22 and 32. (If in doubt, check 42 and 52 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 42 and 52 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

Comments

Popular posts from this blog

A rule of thumb for when to use the Ratio Test

The Extreme Value Theorem: a bootstrap approach

An introduction to the Hahn-Banach extension theorem: Part VI