Question

For my purposes, you may want to interpret "best" as "clearest and easiest to understand for undergrads in a first number theory course," but don't feel too constrained.

Answer 1

I think by far the simplest easiest to remember elementary proof of QR is due to Rousseau. All it uses is the Chinese remainder theorem and Euler's formula $a^{(p-1)/2}\equiv (\frac{a}{p}) \mod p$. The mathscinet review does a very good job of outlining the proof. I'll try to explain how I remember it here (but the lack of formatting is really rough for this argument).

Here's the outline. Consider $(\mathbb{Z}/p)^\times \times (\mathbb{Z}/q)^\times = (\mathbb{Z}/pq)^\times$. We want to split that group in "half", that is consider a subset such that exactly one of x and -x is in it. There are three obvious ways to do that. For each of these we take the product of all the elements in that "half." The resulting three numbers are equal up to an overall sign. Calculating that sign on the $(\mathbb{Z}/p)^\times$ part and the $(\mathbb{Z}/q)^\times$ part give you the two sides of QR.

In more detail. First let me describe the three "obvious" halves:

1. Take the first half of $(\mathbb{Z}/p)^\times$ and all of the other factor
2. Take all of the first factor and the first half of $(\mathbb{Z}/q)^\times$
3. Take the first half of $(\mathbb{Z}/pq)^\times$

The three products are then (letting P = (p-1)/2 and Q=(q-1)/2):

1. $(P!^{q-1}, (q-1)!^P)$
2. $((p-1)!^Q, Q!^{q-1})$
3. $(\frac{(p-1)!^Q P!}{q^P P!},\frac{(q-1)!^P Q!}{p^Q Q!})$

All of these are equal to each other up to overall signs. Looking at the second component it's clear that the sign relating 1 and 3 is $\left(\frac{p}{q}\right)$. Similarly, the sign relating 2 and 3 is $\left(\frac{q}{p}\right)$. So the sign relating 1 and 2 is $\left(\frac{p}{q}\right) \left(\frac{q}{p}\right)$. But to get from 1 to 2 we just changed the signs of $\frac{p-1}{2} \frac{q-1}{2}$ elements. QED

Answer 2

The question asked for the nicest proof for a first undergraduate course. Has anyone who offered a proposal used their favorite choice in a course? (Obviously the suggestions referring to K-theory or Hilbert symbols weren't suggested in that spirit.) I've taught an undergrad number theory class several times and initially I gave the Gauss sum proof. But I realized afterwards that to the students this truly comes out of nowhere (it seems too magical), so I hunted around for other proofs, preferably some which build on more basic ideas that I could present earlier in the course. The Eisenstein (sine-function) proof doesn't fit that requirement, and Zolotarev seems too far-out if the students have not had group theory (which most have not). So what else is available?

There is a proof due to V. Lebesgue (not H. Lebesgue!) that is based on counting points on hyperspheres mod p. It can be found in Ireland-Rosen's book. For an odd prime p and positive integer n, let

N_n(p) = #{(x_1,....,x_n) \in (Z/p)^n : x_1^2 + ... + x_n^2 = 1}.

This is the number of mod p points on the sphere in n-space mod p. Earlier in the course I have the students discover numerically that every number mod p is a sum of two squares. That is,

#{(x,y) \in (Z/p)^2 : x^2 + y^2 = a}

is positive for every a in Z/p. This could be shown by the pigeonhole principle, since x^2 and a - y^2 each take (p+1)/2 values mod p and thus have an overlap. But more precisely, if you look at examples, you quickly discover that this 2-variable count is independent of a when a is nonzero (from a more adv. point of view, the independence is because the norm map on unit groups ((Z/p)[t]/(t^2+1))* --> (Z/p)* is a homomorphism so its fibers have the same size, but that is a crazy explanation in an elem. number theory course). Enough data suggests what that uniform value is for any nonzero a mod p, and then we prove that in class. With this 2-variable count we return to the hypersphere count and get a simple recursive formula connecting N_n(p) to N_{n-2}(p). If you let n = q be an odd prime, the recursive formula involves p^((q-1)/2) plus N_{q-2}(p) times a multiple of q, so N_q(p) mod q involves (p|q). [Note: Although the application will use N_q(p), you must think about N_n(p) for general n first since the recursion from n back to n-2 makes no sense in general when the number of variables is only an odd prime: n-2 usu. isn't prime when n is.]

At the same time, the set being counted by N_n(p) is invariant under cyclic shifts of the coordinates. On the very first problem set I have the students discover numerically that the number of cyclic shifts of an n-tuple is always a divisor of n. So when we let n = q be an odd prime, N_n(p) = N_q(p) is the number of constant q-tuples on the unit sphere mod p plus a multiple of q. A constant q-tuple is basically counting whether or not q mod p is a square. So N_q(p) mod q is related to (q|p).

In the two approaches to counting N_q(p) mod q, one involves (p|q) and the other involves (q|p). This implies the QR relation mod q, which is actual equality since 1 is not -1 mod q.

One nice thing about this approach is that it can also be used to prove the supplementary law for (2|p), by counting

#{(x,y) \in (Z/p)^2 : x^2 + y^2 = 1} mod p

in two ways. First there is the exact formula for the count (not just mod p) which I mentioned before. Second, most solutions in this count come in packets of size 8 (permute coordinates and change signs to get 8 solutions out of one solution). The exceptions which don't fall into packets of size 8 (when x is +/-y mod p or x or y is 0 mod p) depend on whether or not 2 mod p is a square (does 2x^2 = 1 mod p have a solution?), and comparing these two formulas mod p implies the usual rule for (2|p).

Since I am able to get the students to work on ideas that are used in the proof much earlier on during the semester (one doesn't need quadratic residues to numerically look at solutions of x^2 + y^2 = a mod p, for instance), this proof nicely ties together things they have seen throughout the course. So that's why this is my vote for the best proof to give in an undergrad course.

Answer 3

The proof involving Gauss sums seems to be the most standard one.

There is also Tim Kuniskys proof using only basic group theory, which for me makes the theorem a bit less misterious.

Answer 4

I'm a fan of Zolotarev's proof, although the proof by Gauss's lemma does have sentimental value.

Answer 5

The proof involving Gauss sums always seemed the best to me. I'm going to run my own undergrad number theory students through that proof, right after we develop some experience with roots of unity.

If you remove the constraint of accessibility to students of a first number theory course, then you can avoid computations with roots of unity altogether: By Galois theory (and some knowledge of discriminants), a square root of p or -p lives inside of the cyclotomic field of index p. An examination of the action of a Frobenius element at q on this square root relates Legendre(p,q) to Legendre(q,p).

Answer 6

I don't think anyone mentioned Eisenstein's classic proof. This presentation of it is pretty good. I find it clear and attractive, especially because it sort of avoids Gauss' Lemma (which is a clever gadget but somehow off-putting).

Answer 7

The following variant of a proof going back to V. Lebesgue and Eisenstein is due to Aurelien Bessard (2010). See also W. Castryck, A shortened classical proof of the quadratic reciprocity law, Amer. Math. Monthly 115 (2008), 550-551.

Let $p = 2m+1$ and $q$ be distinct odd primes and let $N$ denote the number of solutions of the equation $$ x_1^2 + \ldots + x_p^2 = 1 $$ in the finite field ${\mathbb F}_q$.

1. The group ${\mathbb Z}/p{\mathbb Z}$ acts on the solution space $X$ by shifting indices: if $(x_1, \ldots, x_p) \in X$, then so is $(x_a,x_{a+1}, \ldots)$ for each $a \in {\mathbb Z}/p{\mathbb Z}$, where the indices have to be read modulo $p$. Each orbit has exactly $p$ elements except if there is an $x$ with $(x,x,\ldots,x) \in X$: the orbit of this element has $1$ element. Now $(x,x,\ldots,x) \in X$ if and only if $px^2 = 1$ is solvable in ${\mathbb F}_q$, hence $$ N \equiv \Big( \frac pq \Big) + 1 \bmod p. $$

2. We make a change of variables to transform the diagonal equation into an equation where counting the number of solutions is easier. To this end, consider the matrix $$ A = \left( \begin{matrix} 0 & 1 & & & & & & \\ 1 & 0 & & & & & & \\ & & 0 & 1 & & & & \\ & & 1 & 0 & & & & \\ & & & & \ddots & & & \\ & & & & & 0 & 1 & \\
   & & & & & 1 & 0 & \\
   & & & & & & & a
   \end{matrix} \right) $$ with $a = (-1)^{(p-1)/2}$. Since $\det A = 1$, this matrix is congruent to the unit matrix, hence $X$ and the solution spaces $X'$ of the equation $x^T A x = 1$, i.e., of $$ 2(y_1z_1 + \ldots + y_m z_m) + ax_p^2 = 1 $$ are isomorphic (recall that $p = 2m+1$).

   For counting the number of solutions of $X'$, observe that if $(y_1, \ldots, y_m) = 0$, we have $q^m \cdot (1+a^{(q-1)/2})$ possibilities for choosing $z_1, \ldots, z_m$ and $x_p$.

   If $y = (y_1, \ldots, y_m) \ne 0$, on the other hand, then for each choice of $y$ and $x_p$ we have to count the number of points on a hyperplane of dimension $m$; there are $q^{m-1}$ points on such a hyperplane, and the number of overall possibilities in this case is $(q^m-1) \cdot q \cdot q^{m-1} = q^m(q^m-1)$.

3. Thus we find \begin{align*} N & = q^m (1+a^{(q-1)/2} + q^m(q^m-1) = q^m(q^m + (-1)^{\frac{p-1}2 \frac{q-1}2}) \\ & \equiv \Big(\frac qp \Big) \Big[ \Big(\frac qp \Big) + (-1)^{\frac{p-1}2 \frac{q-1}2} \Big] \equiv 1 + (-1)^{\frac{p-1}2 \frac{q-1}2} \Big(\frac qp \Big) \bmod p. \end{align*} Comparing with the congruence from 1. gives the quadratic reciprocity law.

Answer 8

There's a nice proof that involves the computation of $K_2(\mathbb{Q})$ and the interpretation of $K_2$ as a universal symbol (i.e. a bilinear map $\mathbb{Q}^\times\times\mathbb{Q}^\times\to A$ for some abelian group $A$, written multiplicatively, satisfying $(a,1-a)=1$) in Milnor's book on algebraic $K$ theory. The tame symbols are interpreted as Legendre symbols, and by universality of $K_2$ as a symbol Tate claims that this proof is essentially Gauss's original argument. I suspect that this argument can be generalized to other totally real number fields, but explicit computations of $K_2(F)$ aren't very easy for large discriminants.

It's definitely not the easiest to understand, but at the moment, it's my favorite.

Answer 9

A great proof, inspired by Zolotarev's paper mentioned above, can be found in a very nice paper by Duke and Hopkins. http://www.math.ucla.edu/~wdduke/preprints/duke-main.pdf.

Answer 10

I'm told that the Gauss sum argument gets generalized to class field theory, but do any of the other arguments generalize? Do you ever see them again in higher math?

Answer 11

Gauss' original proof is to be in Gauss' Disquisitiones (English translation published by Springer): the residues -1 and +1 on pages 72-73, the residues +2 and -2 on pages 73-77, +3 and -3 on pages77-78, residues +5 and -5 on pages 79-82, +7 and -7 on page 82...the general law of reciprocity is stated on page-87-88, and the proof is carried out on pp 88-98.

There is a very fine presentation of the Gauss' general inductive proof in the textbook Introduction to Number Theory by Daniel E. Flath, on pages 77-80. I have given this proof (Gauss' treatment of the residues +2, -2, +3, -3, and Flath's version of the general proof) repeatedly in my classes in the University of Costa Rica and the students have responded quite positively.

Finally it can also be found in Mathews, Number Theory, but uses properties of the Jacobi symbol. Gauss used and stated these properties, but did not introduce a separate definition, and of course never used the Legendre symbol.

Answer 12

Gauss' original inductive proof is the most natural proof to me. It is a computationally based induction on the maximum of the two primes p and q, and is far and away the most natural. Here, natural does not mean easy or elegant. It means a proof that arises naturally from the numerical patterns. Gauss computes the special cases of quadratic reprocity in a table in the back of his "Disquisitiones" from which it is fairly easy to guess which numbers are residues or non residues of given prime. He carries out the examples of p=2,3,5, 7 and the patterns start to show clearly. He gives an induction proof for some of those cases, indicating the structure of the general induction proof.

Admittedly, Gauss, himself, looked for other proofs. Nevertheless, the first proof shows WHY the theorem is true in a way which the subsequent clever proofs do not.

Answer 13

I don't really know who discovered this proof, but it's interesting. It is taken from Prof. Ram Murty's website:

• http://www.mast.queensu.ca/~murty/quad1.dvi

Answer 14

The easiest to understand line by line are the elementary proofs that go through Gauss' Lemma, and are likely to be seen in any elementary number theory book. I've never actually liked these proofs personally and prefer the one at the start of Serre's "A Course in Arithmetic" for a proof without many technical prerequisites (finite fields only from memory).

Edit: Less elementarily, one could argue that any 'best' proof will necessarily be adelic, proving that the product of the Hilbert symbols over all places at rational arguments is 1. For a geometric example of such an argument, I'm going to throw out arXiv:0804.2142 and references therein, primarily because I don't know if there exists an analogous argument using a central extension of GL_1 in the number field case.

Answer 15

Kevin Brown has a nice expository article Jewel of Arithmetic

and Franz Lemmermeyer has compiled a list of all published proofs

both of which are worth a look.

---

Edit: I just thought I'd add that there are 224 published proofs in Franz Lemmermeyer's list, and if you are using frames and if your institution subscribes to the online version of Mathematical reviews or Zentralblatt, then the reviews will appear in one of the frames.

Answer 16

There was some discussion above about how the proof with Gauss sums is hard to motivate. I disagree, but the motivation involves a little more (mild) algebraic number theory (i.e., Galois theory, algebraic integers, characteristic zero...) than appears in the shortened proof in Serre's book on arithmetic.

(This is of course well-known to number theorists, but I'll write up the full argument just in case somebody has only ever seen the more magical presentation with Gauss sums before.)

Let $p,q$ be odd, distinct primes below.

1) $\mathbb{Q}(\zeta_p)$ has Galois group $(\mathbb{Z}/p\mathbb{Z})^{\times}$, and therefore contains a unique subfield of degree $2$ over $\mathbb{Q}$. It's straight-forward to compute (without knowing what a Gauss sum is) a non-trivial element of this extension with rational square: it's the Gauss sum $G=\sum (\frac{a}{p})\cdot(\zeta_p)^a$.

2) By construction, $G^2\in\mathbb{Q}$. What is it? It's easy to see from the formula above that $|G|^2=p$. Moreover, also by the formula, the complex conjugate $\overline{G}$ equals $G$ iff $p=1\mod 4$ and $\overline{G}=-G$ iff $G=3\mod 4$. Therefore, $G=\pm \sqrt{p}$ or $G=\pm\sqrt{-p}$ depending on the residue class of $p$ modulo $4$.

This is the major upshot: we have a very convenient expression for (a variant of) $\sqrt{p}$ now.

3) Note that $G$ is an algebraic integer. Therefore, we can reduce it modulo $q$. Since $\mathbb{Q}(G)$ is a quadratic extension of $\mathbb{Q}$ (namely: $\mathbb{Q}[\sqrt{\pm p}]$), the induced extension of $\mathbb{F}_q$ is an extension of degree $\leq 2$.

4) Is this extension $\mathbb{F}_q$ or the unique quadratic extension of $\mathbb{F}_q$? Well, it suffices to check whether or not $G\in\mathbb{F}_q$. To do this, you can use the Frobenius at $q$. It's easy to see in this way that $G^q=(\frac{q}{p})\cdot G$ (by the formula for $G$). So the extension has degree one if $(\frac{q}{p})=1$ and degree two if $(\frac{q}{p})=-1$.

5) But since we know that $G=\sqrt{\pm p}$ (again: depending on the residue class of $p$ mod $4$), we see that we can give a second answer to the question in 4): $G$ defines an extension of degree $1$ if: a) $p=1\mod 4$ and $p$ is a quadratic residue mod $q$ or b) $p=3\mod 4$, $\sqrt{-1}\not\in\mathbb{F}_q$ (which is the same as $q=3 \mod 4$) and $\sqrt{p}\not\in\mathbb{F}_q$.

6) Comparing the answers to the above questions, we see that $q$ is a quadratic residue mod $p$ if and only if the conditions from 5) are satisfied. But these are exactly the conditions from quadratic reciprocity.

Answer 17

I learned the following proof from Jean-François Mestre, it is a variant of Zolotarev's.

For every prime number $p>2$, let $T_p\in\mathbf Z[X]$ be the monic polynomial such that $T_p(X+1/X)X^{(p-1)/2}=(X^p-1)/(X-1)=1+X+\dots+X^{p-1}$. The complex roots of $T_p$ are $x+1/x$, where $x$ is a primitive $p$th root of unity. The same holds in any field of characteristic $\neq p$. In a field of characteristic $p$, the only root of $T_p$ is $2$, with multiplicity $(p-1)/2$.

Let $p,q$ be two odd prime numbers, with $p\neq q$.

The resultant $\mathop{\rm Res}(T_p,T_q)$ of $T_p$ and $T_q$ is an integer. Since these polynomials have no common root, this integer is non-zero.

Since these polynomials have no common root in every field, in particular modulo every prime number, this integer is $\pm1$.

Compute this resultant modulo $p$. One gets $\mathop{\rm Res}(T_p,T_q)\equiv (-1)^{(p-1)(q-1)/4} T_q(2)^{(p-1)/2}\equiv (-1)^{(p-1)(q-1)/2} q^{(p-1)/2}\pmod p$. Consequently, $\mathop{\rm Res}(T_p,T_q)=\epsilon \left(\frac qp\right)$, with $\epsilon=(-1)^{(p-1)(q-1)/4}$.

Similarly, $\mathop{\rm Res}(T_q,T_p)=\epsilon \left(\frac pq\right)$.

Now, $ \mathop{\rm Res}(T_p,T_q) = (-1)^{\deg(T_p)\deg(T_q)} \mathop{\rm Res}(T_q,T_p), $ hence the quadratic reciprocity law.

Answer 18

I think my favorite proof that's accessible to undergrads is Eisenstein's proof using the sine function. If we raise the bar on the prerequisites though, my favorite proof (the one that I would give if someone demanded a proof!) is the one using basic algebraic number theory and Galois theory. That's largely because this is a family of ideas that is useful for much more than "just" proving quadratic reciprocity.

Answer 19

Several people above have mentioned the proof above using Gauss sums. In a recent assignment for our Galois theory course, we were asked to prove quadratic reciprocity using Galois theory. I would like to remark that in determining the fixed field of degree 2 over $\Bbb{Q}$ corresponding to the subgroup of index $2$ in $\textrm{Gal}(\Bbb{Q}(\zeta_p)/\Bbb{Q})$, one does not need to know about Gauss sums. Instead notice that $\Bbb{Q}(\zeta_p)$ is the splitting field of $x^p -1$, so that the discriminant of this polynomial $(-1)^{p(p-1)/2}p^p$ is in $ \Bbb{Q}(\zeta_p)$. The discriminant can be computed easily using the Vandermonde determinant and some knowledge about power sums.

Since the square root of the discriminant is a product of differences of roots, it too is in the splitting field. Hence we see that $\Bbb{Q}(\sqrt{\pm p })$ is the unique subfield of index 2 contained in $\Bbb{Q}(\zeta_p)$, depending on whether $p \equiv 1$ or $3$ mod $4$.

Keith Conrad remarked above that in the usual proof using Gauss sums, we need to show that $1 \equiv -1 \mod(p\Bbb{Z}[\zeta_p])$ gives us our desired contradiction, or that $2/p \in \Bbb{Z}[\zeta_p]$ gives a contradiction. I believe one can do this without invoking anything about integral bases. Instead we can say by Proposition 5.1(iii) of Atiyah - Macdonald that $2/p$ is integral over $\Bbb{Z}$ and since $\Bbb{Z}$ is integrally closed in its field of fractions (the proof of which can be rephrased entirely without any commutative algebra) this forces $2/p$ to be an integer. But by assumption $p$ was a prime not equal to 2 so this is a contradiction.

Answer 20

The pdf version of the Eisenstein's proof mentioned by Alon above can be download from jstor: link text

Answer 21

I found this connection with linking numbers very fascinating and this discussion of generalizations.

Answer 22

I recommend Gauss's third proof with modifications by Eisenstein. In my opinion, it is by far the clearest and most straight-forward proof of Quadratic Reciprocity even though it is not the shortest. The proof makes no use of any mathematical discipline other than elementary number theory. That is, it uses no abstract algebra or combinatorics. Its charm is that it uses the greatest integer function in an advanced way in place of any advanced theory. The proof uses the greatest integer function to express a variety of number-theoretic concepts and statements involving integers mathematically. Then, using properties of the greatest integer function, the proof works with these concepts and statements concretely (by manipulating them mathematically) to achieve the result. Gauss invented the greatest integer function for his third proof of QR in 1808 for this very purpose. Since it was long and messy, it was simplified by Eisenstein in 1844.

How a proof is presented by the author is also important. In my online text, "A Mathematical Analysis of the Greatest Integer Function", I include a full treatment of QR. For Gauss's third proof, I used Dence. His book, "Elements of the Theory of Numbers" is an advanced text and I felt that his presentation of the proof contained gaps. While his presentation might be appropriate for his objectives and target audience, I felt that it would seem more like an outline to undergraduate students. For this reason, when rewriting the proof, I took three measures to provide clarity. I put a lot of effort into closing every gap and providing a thorough explanation for certain parts, which accounts for a lot of its length. Since the proof has many components even after modifications by Eisenstein, I organized it by dividing it into sub-objectives and providing sub-proofs for each. I also include all three lattice-point diagrams with a numerical example in full detail. So, if you want to savor Gauss's third proof with modifications by Eisenstein, then you want to read my online text at www.greatestintegerfunctionresearch.org. My online text is also an excellent resource for various topics in number theory and analysis and is chockfull of original research.