I think this theorem has a wonderful name. I thought that when I first heard the name, even before I’d heard what the theorem says! It just rolls off the tongue. It’s also a very lovely theorem.

When I wrote about sums of squares (in my post about Lagrange’s theorem), I tried to persuade you that thinking about squares and modular arithmetic is a good idea. In particular, we saw that a number (like 7 or 103) that leaves remainder 3 on division by 4 (is 3 (mod 4)) cannot be written as the sum of two squares, because squares are always divisible by 4 or 1 more than a multiple of 4: squares are 0 (mod 4) or 1 (mod 4). We say that 1 is a *quadratic residue* (good name!) (mod 4), and that 3 is a *quadratic non-residue* (mod 4) (because 3 is not a square (mod 4)). 0 and 2 are not coprime to the modulus 4, so we don’t call them quadratic residues or quadratic non-residues.

How can we find the quadratic residues (mod 7), say? We simply square each number from 0 to 6 and take the remainder on division by 7. We don’t need to go beyond 6, because we’ll just get the same again: (mod 7), so (mod 7) and so on. Let’s list some quadratic residues mod various small numbers. For each n, I’ll list , , …, , and then we can see whether we see anything interesting. Please do check my numbers!

2: 0, 1

3: 0, 1, 1

4: 0, 1, 0, 1

5: 0, 1, 4, 4, 1

6: 0, 1, 4, 3, 4, 1

7: 0, 1, 4, 2, 2, 4, 1

8: 0, 1, 4, 1, 0, 1, 4, 1

9: 0, 1, 4, 0, 7, 7, 0, 4, 1

10: 0, 1, 4, 9, 6, 5, 6, 9, 4, 1

11: 0, 1, 4, 9, 5, 3, 3, 5, 9, 4, 1

12: 0, 1, 4, 9, 4, 1, 0, 1, 4, 9, 4, 1

13: 0, 1, 4, 9, 3, 12, 10, 10, 12, 3, 9, 4, 1

14: 0, 1, 4, 9, 2, 11, 8, 7, 8, 11, 2, 9, 4, 1

15: 0, 1, 4, 9, 1, 10, 6, 4, 4, 6, 10, 1, 9, 4, 1

16: 0, 1, 4, 9, 0, 9, 4, 1, 0, 1, 4, 9, 0, 9, 4, 1

17: 0, 1, 4, 9, 16, 8, 2, 15, 13, 13, 15, 2, 8, 16, 9, 4, 1

18: 0, 1, 4, 9, 16, 7, 0, 13, 10, 9, 10, 13, 0, 7, 16, 9, 4, 1

19: 0, 1, 4, 9, 16, 6, 17, 11, 7, 5, 5, 7, 11, 17, 6, 16, 9, 4, 1

20: 0, 1, 4, 9, 16, 5, 16, 9, 4, 1, 0, 1, 4, 9, 16, 5, 16, 9, 4, 1

There are lots of interesting patterns to explore there; I encourage you to look for them and try to explain them before you read on! (I’m not going to go into most of them here, because I don’t have space in this post; I might return to them later. I’m going to focus on just one in this post.)

As you might have already noticed, there are some particularly nice things that happen with quadratic residues to prime moduli (things that don’t necessarily happen with composite moduli). I’d like to concentrate on prime moduli here. I think it’ll be convenient to have lists of quadratic residues (QRs) and quadratic non-residues (QNRs) to prime moduli, written in numerical order (rather than the order in which they occur, which is what I gave above). So here they are.

2: QRs 1

3: QRs 1; QNRs 2

5: QRs 1, 4; QNRs 2, 3

7: QRs 1, 2, 4; QNRs 3, 5, 6

11: QRs 1, 3, 4, 5, 9; QNRs 2, 6, 7, 8, 10

13: QRs 1, 3, 4, 9, 10, 12; QNRs 2, 5, 6, 7, 8 11

17: QRs 1, 2, 4, 8, 9, 13, 15, 16; QNRs 3, 5, 6, 7, 10, 11, 12, 14

19: QRs 1, 4, 5, 6, 7, 9, 11, 16, 17; QNRs 2, 3, 8, 10, 12, 13, 14, 15, 18

Perhaps that will help you see more interesting patterns (if you hadn’t already seen them).

Let’s think about linking rows. For example, I see that 5 is a quadratic residue (mod 19). Is 19 a quadratic residue (mod 5)? Well, 19 = 4 (mod 5), and 4 is a quadratic residue (mod 5), so we say that 19 is a quadratic residue (mod 5).

OK, what else? 3 is not a quadratic residue (mod 17); is 17 a quadratic residue (mod 3)? Quick check: 17 = 2 (mod 3), so 17 is not a quadratic residue (mod 3).

This is all getting a bit clumsy to write out. Fortunately, there’s some notation that can help us: the *Legendre symbol*. We write it as . It is defined to be 1 if a is a quadratic residue (mod p), -1 if a is a quadratic non-residue (mod p), and 0 if p divides a. (This is for prime p. There is a generalisation, called the *Jacobi symbol*, that is defined for composite p, but I shan’t go into the details now.)

So we’ve seen that , and . I suggest you try computing some more of these pairs, for practice.

Is it always the case that for primes p and q?

We can quickly see that it isn’t (if you haven’t already): , but .

Hopefully your examples showed that quite often and are the same, but sometimes they are different (which necessarily means that one is the negative of the other). Can we be more precise about this? Can we predict in advance when they’ll be the same and when they’ll be different? You might like to try this for yourself, using your earlier computations and any more that you feel necessary.

(more…)