*In which we continue our study of quadratic residues modulo primes.*

- Notation: for a fixed odd prime and any integer , write for the unique number congruent to that lies in the interval . (Note: this is not standard notation!)
- Proposition 23 (Gauss‘s Lemma):
*Let be an odd prime and let be an integer coprime to . Then , where .*So to find , compute , , …, , and count how many of them are negative. We proved the lemma by showing that the numbers , , …, are the same as , , …, in some order, where each of those has a definite sign (and of them are negative). We then multiplied together the two lists; this is rather reminiscent of one of the proofs of Fermat’s Little Theorem. Euler’s criterion (which we saw in Lecture 6) finishes the argument. - Corollary 24:
*Let be an odd prime. Then .*We deduced this from Gauss’s Lemma. - Theorem 25 (Law of quadratic reciprocity):
*Let and be odd primes. Then . That is, if then , and if not then .*We postponed the proof until next time, but saw a couple of examples that showed how useful the result is for computing Legendre symbols.

#### Further reading

Davenport (*The Higher Arithmetic*), Baker (*A concise introduction to the theory of numbers*), and Jones and Jones (*Elementary number theory*) all deal with these topics, as do many other books. There are several ways to prove the law of quadratic reciprocity; Davenport and Baker (for example) choose different approaches. We’ll see one of them next time.

#### Preparation for Lecture 8

Try your own examples to get a feel for what quadratic reciprocity says. Next time we’ll see how to prove the result, so you might like to start thinking about that. Hint: try using Gauss’s lemma. You could try to prove the result in some special cases (for particular numerical values), to try to find a strategy that might work in general.

We’re then going to start trying to generalise our work on quadratic residues modulo primes to composite moduli. You could usefully think about which of the results we’ve proved for primes will generalise nicely. You could also think about how we might generalise the Legendre symbol.

October 24, 2011 at 12:20 pm

[…] That is, if then , and if not then . We proved this using Gauss‘s lemma (which we saw in Lecture 7), interpreting the quantities that arise in that lemma as counting lattice points in certain […]

November 30, 2011 at 12:11 pm

[…] . Then , and moreover we have . (The angle bracket notation is the same as that introduced in Lecture 7). We proved this using our upper bound on , which in turn we proved in Lecture […]