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.

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.

Like this:

Be the first to like this post.

This entry was posted on October 21, 2011 at 12:08 pm and is filed under Cambridge Maths Tripos, II Number Theory, Lecture. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

2 Responses to “Number Theory: Lecture 7”

Number Theory: Lecture 8 « Theorem of the week Says:
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 [...]
Number Theory: Lecture 24 « Theorem of the week Says:
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 [...]

Theorem of the week