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.

39$\begingroup$ I have to say that I found quadratic reciprocity confusing until I learned the proof using Frobenius elements of $\mathbb{Q}(\sqrt{p^*}) \subseteq \mathbb{Q}(\zeta_p)$. The other proofs seemed to be long and ad hoc combinatorial arguments which somehow came up with the result, but the proof using Galois groups was so simple! $\endgroup$– David CorwinAug 30 '10 at 17:39

8$\begingroup$ @DavidCorwin The first time I have seen your remark was probably over two years ago, when I knew no Galois theory nor algebraic number theory. Today I know enough of these two fields to understand and appreciate the proof you mention, and I have to say  it is really a proof which makes quadratic reciprocity less mysterious! $\endgroup$– WojowuSep 14 '16 at 20:10

$\begingroup$ I confess that, as a student unaware of the history of the subject and unaware of the connection with cyclotomy, I did not find the law or its socalled elementary proofs appealing. I suppose, although I would not have (and could not have) expressed myself in this way that I saw it as little more than a mathematical curiosity, fit more for amateurs than for the attention of the serious mathematician that I then hoped to become. It was only in Hermann Weyl's book on the algebraic theory of numbers that I appreciated it as anything more : R.P. Langlands on QRT proof. $\endgroup$– C.S.Nov 24 '20 at 8:38
I think by far the simplest easiest to remember elementary proof of QR is due to Rousseau (On the quadratic reciprocity law). All it uses is the Chinese remainder theorem and Euler's formula $a^{(p1)/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:
 Take the first half of $(\mathbb{Z}/p)^\times$ and all of the other factor.
 Take all of the first factor and the first half of $(\mathbb{Z}/q)^\times$.
 Take the first half of $(\mathbb{Z}/pq)^\times$.
The three products are then (letting $P = (p1)/2$ and $Q=(q1)/2$):
 $(P!^{q1}, (q1)!^P)$.
 $((p1)!^Q, Q!^{p1})$.
 $\left(\dfrac{(p1)!^Q P!}{q^P P!},\dfrac{(q1)!^P Q!}{p^Q Q!}\right)$.
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{p1}{2} \frac{q1}{2}$ elements. QED

2$\begingroup$ The link you provided to MR1125443 won't work for people outside of the Columbia network. I think this link ams.org/mathscinet/pdf/1125443.pdf should work for anyone with a mathscinet subscription. Or even better, point it here tinyurl.com/3z62fdw where a free PDF copy of Rousseau's paper is available. $\endgroup$ Jul 25 '11 at 17:43

1$\begingroup$ Note that if $M$ is a finite set, $M=n$, then the sign of a permutation $\pi$ of $M$ equals $\prod_{x<y} (f(\pi(x))f(\pi(y)))/(f(x)f(y))$, where $f$ is arbitrary injection from $M$ to any field (with characteristics not 2) and '$<$' is an arbitrary linear order on $M$. And the main property of the sign is that this does not depend on the chosen injection and linear order. Now applying this to Zolotarev's proof we exclude the notion of the sign and I feel (did not check) that we should get Rousseau's proof for the natural choices of orders and injections. $\endgroup$ Apr 1 '18 at 21:21

2$\begingroup$ Thanks for noticing... It's here stacky.net/files/115/RousseauQR.pdf $\endgroup$ Mar 4 '19 at 21:37

4$\begingroup$ I was wondering what is the natural adaptation of this proof to the $p=2$ case? I tried to mimic the proof replacing $Z/(pq)^\times$ by $Z/(8p)^\times$ but it failed. Any idea? $\endgroup$– OblomovOct 1 at 15:33

1$\begingroup$ @NoahSnyder I tried that, to no avail. (That is, more precisely, I tried to compute the product of elements of $(\mathbb Z/8p\mathbb Z)^\times/\{\pm1,4p\pm1\}$ in two different ways, but they just turned out to be equal without yielding any nontrivial information. But perhaps there is a better way to arrange the things.) $\endgroup$ Oct 20 at 13:17
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 (sinefunction) proof doesn't fit that requirement, and Zolotarev seems too farout 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 IrelandRosen's book. For an odd prime $p$ and positive integer $n$, let
$$N_n(p) = \#\{(x_1,\dots,x_n) \in ({\mathbf Z}/(p))^n : x_1^2 + \cdots + 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 ({\mathbf Z}/(p))^2 : x^2 + y^2 = a\}$$
is positive for every $a$ in ${\mathbf 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 2variable 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 $(({\mathbf Z}/(p))[t]/(t^2+1))^\times \to ({\mathbf Z}/(p))^\times$ is a homomorphism so its fibers have the same size, but that is a crazy explanation in an elem. number theory course). Enough data suggest what that uniform value is for any nonzero $a \bmod p$, and then we prove that in class. With this 2variable count we return to the hypersphere count and get a simple recursive formula connecting $N_n(p)$ to $N_{n2}(p)$. If you let $n = q$ be an odd prime, the recursive formula involves $p^{(q1)/2}$ plus $N_{q2}(p)$ times a multiple of $q$, so $N_q(p) \bmod q$ involves $(\frac{p}{q})$. [Note: Although the application will use $N_q(p)$, you must think about $N_n(p)$ for general odd $n$ first since the recursion from $n$ back to $n2$ makes no sense in general when the number of variables is only an odd prime: $n2$ usually 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 \bmod p$ is a square. So $N_q(p) \bmod q$ is related to $(\frac{q}{p})$.
In the two approaches to counting $N_q(p) \bmod q$, one involves $(\frac{p}{q})$ and the other involves $(\frac{q}{p})$. This implies the QR relation mod $q$, which is actual equality since $1$ is not $1 \bmod q$.
One nice thing about this approach is that it can also be used to prove the supplementary law for $(\frac{2}{p})$, by counting
$$\#\{(x,y) \in ({\mathbf Z}/(p))^2 : x^2 + y^2 \equiv 1 \bmod 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 $\pm 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 \equiv 1 \bmod p$ have a solution?), and comparing these two formulas mod 8 implies the usual rule for $(\frac{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 \equiv a \bmod 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.

4$\begingroup$ A variant of this proof was recently given by W. Castryck, A shortened classical proof of the quadratic reciprocity law. Amer. Math. Monthly 115 (2008), 550551 $\endgroup$ Feb 9 '10 at 19:20

$\begingroup$ For the supplementary law, when you say "the count mod p" do you mean "the count mod 8"? $\endgroup$ Jul 9 '13 at 6:12

$\begingroup$ @QiaochuYuan: Thanks, I made that fix to mod 8. $\endgroup$– KConradJul 9 '13 at 22:13

6$\begingroup$ Cool. If anyone's curious, I thought this was a really nice proof so I worked through the details as an exercise here: qchu.wordpress.com/2013/07/09/thepgroupfixedpointtheorem $\endgroup$ Jul 9 '13 at 23:04

1$\begingroup$ This seems to be a combinatorialization of Gauss sum proof, is not it? Counting these $q$tuples is the same thing as taking the constant term of $q$th power of the Gauss sum: $(\sum_{k=0}^{p1} z^{k^2})^q$, where polynomials are taken modulo $z^p1$. $\endgroup$ Apr 1 '18 at 20:14
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), 550551.
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$.
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. $$
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)^{(p1)/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^{(q1)/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^{m1}$ points on such a hyperplane, and the number of overall possibilities in this case is $(q^m1) \cdot q \cdot q^{m1} = q^m(q^m1)$.
Thus we find \begin{align*} N & = q^m (1+a^{(q1)/2} + q^m(q^m1) = q^m(q^m + (1)^{\frac{p1}2 \frac{q1}2}) \\\ & \equiv \Big(\frac qp \Big) \Big[ \Big(\frac qp \Big) + (1)^{\frac{p1}2 \frac{q1}2} \Big] \equiv 1 + (1)^{\frac{p1}2 \frac{q1}2} \Big(\frac qp \Big) \bmod p. \end{align*} Comparing with the congruence from 1. gives the quadratic reciprocity law.

$\begingroup$ For odd primes! I guess there is probably a straightforward variant for $p = 2$. $\endgroup$ Jul 25 '11 at 17:11

$\begingroup$ @FranzLemmermeyer I am unable to follow the step where it says that 'since $\det(A)=1$, $A$ is congruent to the identity matrix.' I considered the following example. Let $F=\mathbb F_3$ and let $A=\begin{bmatrix}2& 0\\ 0& 2\end{bmatrix}$. Then $A$ has determinant $1$ in $F$. But if $A=P^tP$ for some $P=\begin{bmatrix}a& b\\ c& d\end{bmatrix}$, then we would have that there are $a^2+b^2=c^2+d^2=2, ab+cd=0$. But the first equation forces $a=b=c=d=1$, and thus $ab+cd=2\neq 0$. So $A$ is not congruent to $I$. $\endgroup$ Apr 22 '20 at 22:44

$\begingroup$ Try $a = b = c = 1$ and $d = 2$. The proof can be found in Caldero & Germoni, Histoire h\'edonistes de groupes et g\'eom\'etries,, p. 185 ff. They use that over finite fields, symmetric matrices with the same rank and the same determinant are congruent. $\endgroup$ Apr 27 '20 at 10:40
I'm a fan of Zolotarev's proof, although the proof by Gauss's lemma does have sentimental value.

3$\begingroup$ Interesting proof! Thanks! :) Conceptually it's very attractive (define three natural permutations, calculate their sign), but the calculations are a bit tedious. Still, nice proof  don't think I've ever seen it. $\endgroup$ Oct 20 '09 at 17:07

1$\begingroup$ John Conway has a nice exposition of a similar proof in the appendix to The Sensual (Quadratic) Form. Unfortunately I don't know any of any writeups of it online. $\endgroup$ Oct 22 '09 at 3:07

4$\begingroup$ There is a slightly more elegant exposition (I think) of Zolotarev's proof written down by Prasolov (tinyurl.com/y9ltg5x  unfortunately, it might only be available in Russian...) $\endgroup$ Feb 2 '10 at 1:02

2

1$\begingroup$ @Qiaochu The link which you have referred for the proof doesn't seem to work :( $\endgroup$– C.S.Dec 6 '18 at 10:30
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).

6$\begingroup$ Jared, there's a sneaky part of that proof which is a big pain if you want to treat it in an undergrad number theory course: at the very end of the proof you get the two sides of the QR formula to be congruent mod p, with p odd, and to justify that the two sides are equal you need to know that 1 \not= 1 mod p. That may look obvious, but in the proof that modulus is not pZ, but is pZ[zeta_p]. So it comes down to knowing 2/p isn't in Z[zeta_p]. I can't think of a short way of proving that, can you? Alg. integers or the norm map will both look far out on that ring, even if they know Z[i]. $\endgroup$– KConradJan 19 '10 at 21:02

1$\begingroup$ Keith: Showing that 2/p doesn't belong to Z[zeta_p] follows from the Qlinear independence of 1, zeta, ... , zeta^(p2), correct? That's not so hard to get across if they've had linear algebra. But in practice, when I gave this proof I wasn't at all "honest" in the sense you use above. In particular, I never gave a full proof that the pth cyclotomic polynomial was irreducible. In fact, a lot of what I did in that class was very impressionistic and left off details that were either relegated to office hours or simply not treated. It would have made you sick to watch, I'm sure! $\endgroup$ Jan 19 '10 at 22:16

1$\begingroup$ I have taught the Gauss sum proof twice in a senior level undergrad number theory course: math.uga.edu/~pete/4400qrproof.pdf. I agree that there is an innocuous but nontrivial algebraic result to prove here, which I farm out to a handout: math.uga.edu/~pete/4400algebra3.pdf. (I cannot remember ever having explicitly discussed any of the material of this handout with a student.)... $\endgroup$ Jun 18 '10 at 5:01

8$\begingroup$ The gauss sums proof can be carried out in an extension of the finite field and not in the cyclotomic field. The only non trivial result in need is that the multiplicative group of a finite field is cyclic. This is carried out very nicely and to the point in Serre's A Course in Arithmetic (he uses the algebraic closure, but appropriate finite extensions suffice). $\endgroup$ Jul 9 '10 at 22:12

1$\begingroup$ I found a more elementary proof of the "innocuous algebraic result" in D. Flath's number theory text and included it in the latest writeup of my notes: see $\S 4.6$ of math.uga.edu/~pete/4400FULL.pdf. This argument uses some linear algebra (eigenvalues, the characteristic polynomial) so is not accessible to the widest possible audience, but it is a lot better than including an appendix on integral elements and extensions! $\endgroup$ Jul 24 '12 at 11:31
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 wellknown 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 straightforward to compute (without knowing what a Gauss sum is) a nontrivial element of this extension with rational square: it's the Gauss sum $G=\sum \left(\frac{a}{p}\right)\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=\left(\frac{q}{p}\right)\cdot G$ (by the formula for $G$). So the extension has degree one if $\left(\frac{q}{p}\right)=1$ and degree two if $\left(\frac{q}{p}\right)=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.
The proof involving Gauss sums seems to be the most standard one.
There is also Tim Kunisky's proof using only basic group theory, which for me makes the theorem a bit less mysterious.

4$\begingroup$ This appears to be the same as the proof due to Rousseau that Noah mentioned, but it's quite impressive that it was rediscovered by a student. $\endgroup$ Oct 20 '09 at 19:37

2$\begingroup$ Maybe this student was aware of Rousseau's proof... $\endgroup$ Nov 6 '09 at 16:47

4$\begingroup$ Jose, I was there  he was not. He's just an impressive guy. :) $\endgroup$ Nov 27 '09 at 5:46

6$\begingroup$ Dave is right. I was emailed the proof in 2008 by Glenn Stevens after Tim showed it to him and Glenn had never seen it before. I forwarded the proof to Dan Shapiro, who then immediately pointed out it is just like Rousseau's proof in the Journal of the Australian Math. Society. It would be nice if this proof could extend to quartic reciprocity in Z[i]. Find suitable quartersystems of representatives in (Z[i]/pi)*. Any thoughts? $\endgroup$– KConradJan 19 '10 at 22:17

2$\begingroup$ The link to Kunisky's proof is dead. Can anyone provide a reference to this proof? $\endgroup$– WojowuApr 2 '16 at 21:06
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,1a)=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.
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 offputting).

$\begingroup$ The pdf version of the Eisenstein's proof mentioned by Alon above can be download from jstor: [link text](jstor.org/stable/… $\endgroup$– user808Oct 20 '09 at 17:32

2$\begingroup$ This classic "elementary" proof can be found in Niven & Zuckerman's book  An Introduction to the theory of numbers. +1. $\endgroup$ Jul 10 '10 at 4:02

$\begingroup$ It's available for free through the author's page. $\endgroup$ Jul 10 '10 at 6:11

$\begingroup$ This approach appears to be more and more widely spread, doesn't it? $\endgroup$– awllowerFeb 17 '11 at 9:49

$\begingroup$ I agree that this particular proof is better than using Gauss' Lemma  similar in style, but less annoying  and gives a great chance to mention Eisenstein in a number theory class with no algebra prerequisites. I use it now myself, and relegate Gauss to an appendix. $\endgroup$– kcrismanApr 9 '13 at 19:08
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.

7$\begingroup$ "Why" means different things to different people. I can imagine number theorists saying that the "why" is only cleared up by class field theory. I also don't know what proof you're referring to. Could you provide a reference or a short description? $\endgroup$ Feb 1 '10 at 21:04

7$\begingroup$ The reference "Disquisitiones" was already given. For an English version, see Carlitz, <em> A note on Gauss' first proof of the quadratic reciprocity theorem</em>, Proc. Am. Math. Soc. 11, 563565 (1960). The basic idea was known to Fermat: if p = 3n+2 is prime, then 3 is a nonsquare. If not, x^2+3 =pm; choosing x carefully you can make sure that m is small and divisible by a prime q = 3k+2 modulo which 3 is a square; now do descent. $\endgroup$ Feb 2 '10 at 14:08
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/dukemain.pdf.

2$\begingroup$ I like the DukeHopkins theorem a lot too. I wrote up a slightly simplified version when the finite group $G$ is assumed to be abelian: math.uga.edu/~pete/morequadrec.pdf $\endgroup$ Jun 17 '10 at 20:32

1$\begingroup$ Notice that the link seems to be broken. Per chance it is my problem? Regards. $\endgroup$– awllowerApr 16 '13 at 16:40

I learned the following proof from JeanFranç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^{(p1)/2}=(X^p1)/(X1)=1+X+\dots+X^{p1}$. 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 $(p1)/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 nonzero.
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)^{(p1)(q1)/4} T_q(2)^{(p1)/2}\equiv (1)^{(p1)(q1)/2} q^{(p1)/2}\pmod p$. Consequently, $\mathop{\rm Res}(T_p,T_q)=\epsilon \left(\frac qp\right)$, with $\epsilon=(1)^{(p1)(q1)/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.
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.
Gauss' original proof is to be in Gauss' Disquisitiones (English translation published by Springer): the residues 1 and +1 on pages 7273, the residues +2 and 2 on pages 7377, +3 and 3 on pages7778, residues +5 and 5 on pages 7982, +7 and 7 on page 82...the general law of reciprocity is stated on page8788, and the proof is carried out on pp 8898.
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 7780. 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.

1$\begingroup$ It seems you have a problem of getting a sepearate userid each time you login. The solution is to merge your accounts and get an OpenID. For the former, one can contact the moderators. $\endgroup$– AnweshiFeb 1 '10 at 22:14
I don't really know who discovered this proof, but it's interesting. It is taken from Prof. Ram Murty's website:

1$\begingroup$ As indicated in the references, this proof goes back to Isai Schur. $\endgroup$ Apr 16 '17 at 17:29

$\begingroup$ @FranzLemmermeyer Thanks for letting me know. Sorry it missed my eye :( $\endgroup$– C.S.Apr 20 '17 at 5:36
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.

1$\begingroup$ I think the most motivated proof that goes through Gauss' Lemma is the one that appears in Davenport's "Higher Arithmetic" ; it's close to Euler's approach. $\endgroup$ Jun 3 '10 at 0:51
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(p1)/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.

$\begingroup$ Concerning the last paragraph, methods related to integral extensions are a bit beyond the usual syllabus of a first number theory course for undergraduates. That's why proving $2/p$ is not in $\mathbf Z[\zeta_p]$ is a bit tedious for such a course. $\endgroup$– KConradSep 10 at 23:05
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.

$\begingroup$ Now that I think of it, I'm not sure of the sine proof that I'm thinking of is Eisenstein's . . . anyway, there's a nice proof involving the sine function. $\endgroup$ Oct 20 '09 at 18:49

$\begingroup$ It's Eisenstein (unless there's more than one sine proof). $\endgroup$ Oct 20 '09 at 18:59
A nice proof was given by Dirichlet (see Dirichlet P.G.L., Lectures on number theory). Poisson summation proves that (see also Davenport, Multiplicative number theory) $$S(q)=\sum_{k=1}^qe(k^2/q)=\dfrac{1+i^{q}}{1+i^{1}}\cdot\sqrt{q}.$$ Together with multiplicative property $$S(pq)=\left(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right)S(p)S(q)$$ it proves the law: $$\left(\dfrac{p}{q}\right)\left(\dfrac{q}{p}\right)=\frac{1+i^{pq}}{1+i^{p}} \cdot\frac{1+i^{1}}{1+i^{q}}=(1)^{\frac{p1}{2}\cdot\frac{q1}{2}}.$$
I recommend Gauss's third proof with modifications by Eisenstein. In my opinion, it is by far the clearest and most straightforward 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 numbertheoretic 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 subobjectives and providing subproofs for each. I also include all three latticepoint 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.
Well, I certainly don't know all the different proofs presented here, but the "natural", unoriginal and very elementary one you'll find p. 7778 of Hardy and Wright "Theory of Numbers" (4th edition) is assuredly quite pleasant to teach...