Proofs of quadratic reciprocity

Of the elementary combinatorial proofs, there are two which apply types of double counting.

The point of departure is "Eisenstein's lemma", which states that for odd prime p and positive integer a not divisible by p, where

[1] The conclusion is that where μ is the total number of lattice points in the interior of AXY.

Switching p and q, the same argument shows that where ν is the number of lattice points in the interior of WYA.

Since there are no lattice points on the line AY itself (because p and q are relatively prime), and since the total number of points in the rectangle WYXA is we obtain For an even integer u in the range 1 ≤ u ≤ p−1, denote by r(u) the least positive residue of au modulo p. (For example, for p = 11, a = 7, we allow u = 2, 4, 6, 8, 10, and the corresponding values of r(u) are 3, 6, 9, 1, 4.)

The numbers (−1)r(u)r(u), again treated as least positive residues modulo p, are all even (in our running example, they are 8, 6, 2, 10, 4.)

Multiplying them together, we obtain Dividing out successively by 2, 4, ..., p−1 on both sides (which is permissible since none of them are divisible by p) and rearranging, we have On the other hand, by the definition of r(u) and the floor function, and since p is odd and u is even, implies that

Finally this shows that We are finished because the left hand side is just an alternative expression for (a/p), per Euler's criterion.

This lemma essentially states that the number of least residues after doubling that are odd gives the value of (q/p).

and r(u) are either congruent modulo 2, or incongruent, depending solely on the parity of u.

These proofs work by comparing computations of single values in two different ways, one using Euler's Criterion and the other using the Binomial theorem.

As an example of how Euler's criterion is used, we can use it to give a quick proof of the first supplemental case of determining

is an algebraic integer, if p is an odd prime it makes sense to talk about it modulo p. (Formally we are considering the commutative ring formed by factoring the algebraic integers

Because the cross terms in the binomial expansion all contain factors of p, we find that

The idea for the general proof follows the above supplemental case: Find an algebraic integer that somehow encodes the Legendre symbols for p, then find a relationship between Legendre symbols by computing the qth power of this algebraic integer modulo q in two different ways, one using Euler's criterion the other using the binomial theorem.

To put this in context of the next proof, the individual elements of the Gauss sum are in the cyclotomic field

but the above formula shows that the sum itself is a generator of the unique quadratic field contained in L. Again, since the quadratic Gauss sum is an algebraic integer, we can use modular arithmetic with it.

The proof presented here is by no means the simplest known; however, it is quite a deep one, in the sense that it motivates some of the ideas of Artin reciprocity.

The basic theory of cyclotomic fields informs us that there is a canonical isomorphism which sends the automorphism σa satisfying

(In fact it is the unique quadratic extension of Q contained in L.) The Gaussian period theory determines which one; it turns out to be

, where At this point we start to see a hint of quadratic reciprocity emerging from our framework.

consists precisely of the (nonzero) quadratic residues modulo p. On the other hand, H is related to an attempt to take the square root of p (or possibly of −p).

, choose any unramified prime ideal β of lying over q, and let

is that (The existence of such a Frobenius element depends on quite a bit of algebraic number theory machinery.)

Now, since the pth roots of unity are distinct modulo β (i.e. the polynomial Xp − 1 is separable in characteristic q), we must have that is,

elementary theory of quadratic fields implies that the ring of integers of K is precisely

Two are especially noteworthy: Lemmermeyer (2000) has many proofs (some in exercises) of both quadratic and higher-power reciprocity laws and a discussion of their history.

Its immense bibliography includes literature citations for 196 different published proofs.

Ireland & Rosen (1990) also has many proofs of quadratic reciprocity (and many exercises), and covers the cubic and biquadratic cases as well.

Exercise 13.26 (p 202) says it all Count the number of proofs to the law of quadratic reciprocity given thus far in this book and devise another one.