## Number Theory: Lecture 7

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

• Notation: for a fixed odd prime $p$ and any integer $b$, write $\langle b \rangle$ for the unique number congruent to $b \pmod{p}$ that lies in the interval $[-p/2, p/2]$.  (Note: this is not standard notation!)
• Proposition 23 (Gauss‘s Lemma): Let $p$ be an odd prime and let $a$ be an integer coprime to $p$.  Then $\genfrac{(}{)}{}{}{a}{p} = (-1)^{\nu}$, where $\nu := \# \{ k \in \{1, 2, \dotsc, (p-1)/2 \} : \langle ka \rangle < 0 \}$.  So to find $\nu$, compute $\langle a \rangle$, $\langle 2a \rangle$, …, $\langle (\frac{p-1}{2}) a \rangle$, and count how many of them are negative.  We proved the lemma by showing that the $(p-1)/2$ numbers $\langle a \rangle$, $\langle 2a \rangle$, …, $\langle (\frac{p-1}{2})a \rangle$ are the same as $\pm 1$, $\pm 2$, …, $\pm (p-1)/2$ in some order, where each of those has a definite sign (and $\nu$ 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 $p$ be an odd prime.  Then $\genfrac{(}{)}{}{}{2}{p} = (-1)^{\frac{p^2 - 1}{8}}$.  We deduced this from Gauss’s Lemma.
• Theorem 25 (Law of quadratic reciprocity): Let $p$ and $q$ be odd primes.  Then $\genfrac{(}{)}{}{}{p}{q} = (-1)^{\frac{p-1}{2} \frac{q-1}{2}} \genfrac{(}{)}{}{}{q}{p}$.  That is, if $p \equiv q \equiv 3 \pmod{4}$ then $\genfrac{(}{)}{}{}{p}{q} = - \genfrac{(}{)}{}{}{q}{p}$, and if not then $\genfrac{(}{)}{}{}{p}{q} = \genfrac{(}{)}{}{}{q}{p}$.  We postponed the proof until next time, but saw a couple of examples that showed how useful the result is for computing Legendre symbols.

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.