Quadratic Reciprocity

The law of quadratic reciprocity, noticed by Euler and Legendre and proved by Gauss, helps greatly in the computation of the Legendre symbol.

First, we need the following theorem:

Theorem: Let \(p\) be an odd prime and \(q\) be some odd integer coprime to \(p\). Let \(m = \lfloor q/p \rfloor + \lfloor 2q/p \rfloor +...+ \lfloor ((p-1)/2)q/p \rfloor\).

Then \(m = u \pmod 2\), where as in Gauss' Lemma, \(u\) is the number of elements of \( \{q, 2q,...,q(p-1)/2\} \) which have a residue greater than \(p/2\).

Proof: For each \(i = 1,...,(p-1)/2\), the equation \(i q = p \lfloor i q/p \rfloor + r_i\) holds for some \(0 < r_i < p\). Reading the proof of Gauss' Lemma, we see these are precisely the \(b_i\) and \(c_i\).

Then summing these equations modulo 2 gives

That is,

Since \(p\) and \(q\) are odd, we have \(m = u \pmod 2\).∎

Theorem (Law of Quadratic Reciprocity): Let \(p, q\) be distinct odd primes. If \(p = q = -1 \pmod {4}\), then

otherwise

which we can state as

Proof: From above, we need only show

where \(m = \lfloor q/p \rfloor + \lfloor 2q/p \rfloor +...+ \lfloor ((p-1)/2)q/p \rfloor\), and \(n\) is similarly defined by swapping \(p\) and \(q\).

Eisenstein found an elegant geometrical proof. Consider the line \(L\) from \((0,0)\) to \((p,q)\), and the rectangle \(R\) with corners at \((0,0)\) and \((p/2, q/2)\). How many lattice points lie strictly in \(R\)?

Simply computing the area of a rectangle gives \((p-1)(q-1)/4\). Alternatively, we can count the number of points above and below \(L\) inside \(R\), since no lattice points can lie on \(L\) in \(R\) since \(p, q\) are coprime.

Consider the points below \(L\) on the line \(x = 1\). They have \(y\)-coordinates of \(1, 2, ..., \lfloor q/p \rfloor\). When \(x = 2\), there are \(\lfloor 2q/p \rfloor\) points, and so on, giving a total of \(m\) points below the \(L\). Similarly there are \(n\) points above \(L\) in \(R\), proving the result.

We can restate the proof algebraically. Consider the numbers \(p y - q x\) for \(x = 1,...,(p-1)/2\) and \(y = 1,...,(q-1)/2\). There are a total of \((p-1)(q-1)/4\) numbers, not necessarily distinct. None are zero, since \(p, q\) are coprime. The result follows after observing that \(n\) of them are positive, and \(m\) are negative.

Example:

We have:

and:

Hence \(31\) is a quadratic nonresidue modulo \(103\).

This method is flawed because it relies on factoring, but it turns out all is well once we extend the Legendre symbol.