## Number Theory: Lecture 8

In which we prove the law of quadratic reciprocity and generalise the Legendre symbol.

• 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 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 regions of the plane.
• Exercise: Let $p$ and $q$ be odd primes, and let $a$ be an integer.  Show that if there is an integer $k$ such that $p = q + 4ak$ or $p = -q + 4ak$, then $\genfrac{(}{)}{}{}{a}{p} = \genfrac{(}{)}{}{}{a}{q}$.
• Definition: Jacobi symbol $\genfrac{(}{)}{}{}{a}{n}$ for an integer $a$ and an odd natural number $n$.  We noted the important point that $\genfrac{(}{)}{}{}{a}{n} = 1$ does not mean that $a$ is a quadratic residue modulo $n$.  (Find your own examples to be clear about this.)
• Lemma 26: The Jacobi symbol is totally multiplicative: for any integers $a$, $b$ and any odd natural number $n$, we have $\genfrac{(}{)}{}{}{a}{n} \genfrac{(}{)}{}{}{b}{n} = \genfrac{(}{)}{}{}{ab}{n}$.  We also have $\genfrac{(}{)}{}{}{a}{mn} = \genfrac{(}{)}{}{}{a}{m} \genfrac{(}{)}{}{}{a}{n}$ for any integer $a$ and odd natural numbers $m$ and $n$.  The former follows from the definition of the Jacobi symbol and the multiplicative property of the Legendre symbol (which we saw in Lecture 6), and the latter from the definition of the Jacobi symbol.
• Lemma 27: Let $n$ be an odd natural number.  Then $\genfrac{(}{)}{}{}{-1}{n} = (-1)^{(n-1)/2}$ and $\genfrac{(}{)}{}{}{2}{n} = (-1)^{(n^2-1)/8}$.  These are the direct analogues of Corollary 22 and Corollary 24, and follow from them.
• Theorem 28 (Quadratic reciprocity for the Jacobi symbol): Let $m$ and $n$ be odd natural numbers.  Then $\genfrac{(}{)}{}{}{m}{n} = (-1)^{\frac{m-1}{2} \frac{n-1}{2}} \genfrac{(}{)}{}{}{n}{m}$.  Note that by stating it in this way we have a result that is true even if $m$ and $n$ are not coprime.  If you prefer to state it another way, then you may need to be more careful.  Please try to prove this for yourself before next time; I’ll start the next lecture with a proof.

These results make it relatively straightforward to compute Legendre symbols and Jacobi symbols; try some examples for yourself to get a feel for the types of calculation involved.

The exercise above is to deduce a result from the law of quadratic reciprocity.  I encourage you to try to prove the result directly from Gauss’s lemma, and then to deduce the law of quadratic reciprocity from the result.  This is the approach that Davenport (The Higher Arithmetic) describes, and that Gareth Taylor has summarised in these online notes.  Baker (A concise introduction to the theory of numbers) and Jones and Jones (Elementary Number Theory) both give the lattice-point proof of quadratic reciprocity that we saw in lectures.

I see that there is also a CATAM project that invites you to explore some of the computational questions arising from the study of quadratic (and other polynomial) congruences — that would be a particularly interesting thing to investigate now that you’ve seen some of the theory.

#### Preparation for Lecture 9

Next time, once we’ve proved quadratic reciprocity for the Jacobi symbol, we’ll move on to something slightly different: binary quadratic forms.  These are objects of the form $ax^2 + bxy + cy^2$, where the coefficients $a$, $b$ and $c$ are integers (and we think of $x$ and $y$ as integer variables).  We are going to be interested in questions to do with which numbers can be represented by such forms (that is, as $x$ and $y$ range over the integers, which values do we get from $ax^2 + bxy + cy^2$?).  Here are some questions that you could usefully try yourself before the lecture.

• Which numbers are represented by the form $4x^2 + 12xy + 9y^2$?
• Which numbers are represented by the form $x^2 + y^2$?  (That is, which numbers can be written as a sum of two squares?)
• When do two forms represent the same set of numbers?  For example, can you find any forms that give the same set of numbers as the form $4x^2 + 12xy + 9y^2$, or the same set of the numbers as the form $x^2 + y^2$?
• What is the link between binary quadratic forms $ax^2 + bxy + cy^2$ and $2 \times 2$ integer matrices with determinant 1 (that is, elements of $SL_2(\mathbb{Z})$)?