## Theorem 29: the law of quadratic reciprocity

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: $7 \equiv 0$ (mod 7), so $7^2 \equiv 0^2$ (mod 7) and so on.  Let’s list some quadratic residues mod various small numbers.  For each n, I’ll list $0^2$, $1^2$, …, $(n-1)^2$, 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

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 $\left( \frac{a}{p} \right)$.  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 $\left( \frac{5}{19} \right) = \left( \frac{19}{5} \right) = 1$, and $\left(\frac{3}{17}\right)=\left(\frac{17}{3}\right)=-1$.  I suggest you try computing some more of these pairs, for practice.

Is it always the case that $\left(\frac{p}{q} \right) = \left( \frac{q}{p} \right)$ for primes p and q?

We can quickly see that it isn’t (if you haven’t already): $\left( \frac{7}{11} \right ) = -1$, but $\left( \frac{11}{7} \right) = \left( \frac{4}{7} \right) = 1$.

Hopefully your examples showed that quite often $\left(\frac{p}{q} \right)$ and $\left( \frac{q}{p} \right)$ 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.

This week’s theorem tells us for which primes p and q we have $\left(\frac{p}{q}\right) = \left(\frac{q}{p}\right)$.  It seems that various people (Euler, Legendre, perhaps others) had noticed this fact, but as far as I know Gauss was the first to prove it (he gave many different proofs during his lifetime).

Theorem (the law of quadratic reciprocity) Let p and q be distinct odd primes.  Then $\left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{(\frac{p-1}{2})(\frac{q-1}{2})}$.

That is, if $p \equiv q \equiv 3$ (mod 4), then $\left(\frac{p}{q} \right) = - \left(\frac{q}{p}\right)$, and otherwise $\left(\frac{p}{q}\right)=\left(\frac{q}{p}\right)$.  So the Legendre symbols are the same unless p and q are both 3 (mod 4).

To put that another way, there are two cases.  If p and q are not both 3 (mod 4), then the congruence $x^2 \equiv q$ (mod p) has a solution if and only if the congruence $y^2 \equiv p$ (mod q) has a solution.  If p and q are both 3 (mod 4), then the congruence $x^2 \equiv q$ (mod p) has a solution if and only if the congruence $y^2 \equiv p$ (mod q) does not have a solution.

Which, I hope you’ll agree, is a simple and elegant criterion.

This can be generalised to a result about Jacobi symbols (I mentioned them above), but the proof of that really comes down to this result about primes: this is where the main ideas happen.  One can use this to compute Legendre/Jacobi symbols quite quickly, even for large numbers (without having to square lots of numbers to find all the quadratic residues).  To give a very simple example: since 7 and 11 are both congruent to 3 (mod 4), quadratic reciprocity tells us that $\left(\frac{7}{11}\right) = - \left(\frac{11}{7}\right) = -\left(\frac{4}{7}\right)$.  But 4 is obviously a quadratic residue (mod 7), so we have $\left(\frac{7}{11}\right) = - 1$ — as we saw earlier, but hopefully you’ll see that this was easier than listing all the squares, and would be much easier if we’d started with larger numbers.

I’m not going to give a proof here; you should be able to find one in an introduction to number theory (such as Davenport’s The Higher Arithmetic).  There is also lots of information about the law of quadratic reciprocity on Wikipedia, and there’s a separate page about proofs of the law.  Those Wikipedia pages give some hints of how quadratic reciprocity leads on to more sophisticated ideas in algebraic number theory — interesting stuff!

### 8 Responses to “Theorem 29: the law of quadratic reciprocity”

1. Theorem 30: Pythagorean triples « Theorem of the week Says:

[…] Theorem of the week Expositions of interesting mathematical results « Theorem 29: the law of quadratic reciprocity […]

2. Olof Says:

“3 is not a quadratic residue (mod 17); is 3 a quadratic residue (mod 17)?”: I think you meant to swap 3 and 17 after the semi-colon!

3. theoremoftheweek Says:

Thanks Olof — hopefully it’s fixed now. It’s rather irritating that I did that: I was sure that I was going to make a silly mistake in this post (just because there were so many numbers), but I’d rather not have been proved right!

4. Theorem 33: the size of Gauss sums « Theorem of the week Says:

[…] the point of this?  It tells us something about the distribution of the quadratic residues modulo a prime.  We’ve seen three quite different types of behaviour with these mystery […]

5. franklin juarez Says:

beautiful examples of what the quadratic reciprocity is all about.I never understood the meaning of that theorem before.

6. Number Theory: Lecture 7 « Theorem of the week Says:

[…] 25 (Law of quadratic reciprocity): Let and be odd primes.  Then .  That is, if then , and if not then .  We postponed the […]

7. Theorem 41: Gauss’s lemma « Theorem of the week Says:

[…] Gauss’s lemma called Gauss’s lemma?  Well, Gauss proved it on the way to proving the law of quadratic reciprocity (something that he did surprisingly often).  And the law of quadratic reciprocity really is a good […]

8. Number Theory: Lecture 7 | Theorem of the week Says:

[…] Theorem 25 (Law of quadratic reciprocity): Let and be odd primes.  Then .  We proved this using Gauss’s lemma, thinking about counting lattice points in regions within a rectangle. […]