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.

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.


2 Responses to “Number Theory: Lecture 7”

  1. Number Theory: Lecture 8 « Theorem of the week Says:

    […] 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 […]

  2. Number Theory: Lecture 24 « Theorem of the week Says:

    […] .  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 […]

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: