Uses of quadratic reciprocity theorem

I want to motivate the quadratic reciprocity theorem, which at first glance does not look too important to justify it being one of Gauss' favorites. So far I can think of two uses that are basic enough to be shown immediately when presenting the theorem:

1) With the QRT, it is immediate to give a simple, efficient algorithm (that can be done even by hand) for computing Legendre symbols.

2) In Euler's proof of Fermat's claim on the conditions in which a prime $p$ is of the form $x^2+ny^2$ (for certain small values of $n$) the proof is reduced to finding the conditions under which $p$ divides $x^2+ny^2$ for some $x,y$, hence to the question under which conditions is $-n$ a quadratic residue modulo $p$, which leads immediately to the QTR (for example, for $n=3$, where we get that $p\equiv_3 1$). I really like this example since it begins with an "historic" problem and proceeds to "discover" the QTR through special cases (which is what Euler did in practice - see Cox's book on "Primes of the form $x^2+ny^2$").

However, I am sure there are many more examples (and I'm especially curious as to how Gauss reached the theorem himself). I'd love to hear about them and receive references for further reading.

This is a good question.

My own take on motivating quadratic reciprocity is recorded here (these are lecture notes from an undergraduate course on introductory number theory). If you look there, you will find that most of what I have said is an elaboration of the two points you bring up. I think a crisp way of explaining what QR does for you is in the idea of the "direct" and "inverse" problems attached to the Legendre symbol $(\frac{n}{p})$.

Namely, for the direct problem we fix $p$ and ask which integers $n$ are squares modulo $p$. This is clearly a finite problem. On the other hand there is the inverse problem: we fix an integer $n$ and ask for which primes $p$ we have that $n$ is a square modulo $p$. This is, a priori, an infinite problem. However, it is one of great relevance to classical number theory: e.g. all of the many proofs I have seen of Fermat's Two Squares theorem pass through the fact that $-1$ is a square modulo an odd prime $p$ iff $p \equiv 1 \pmod 4$. More generally, if you look at the Diophantine equation $x^2 - n y^2 = p$, for $n$ a nonzero integer and $p$ a prime with $\operatorname{gcd}(p,n) = 1$, then reducing modulo $p$ gives the necessary condition $(\frac{n}{p}) = 1$. Quadratic reciprocity to the rescue!

Secondly, as you also say, quadratic reciprocity gives an efficient algorithm for answering whether a particular $n$ is a square modulo $p$, much faster than computing all $\frac{p-1}{2}$ squares modulo $p$.

In my experience, this is more than enough for students to appreciate the usefulness of Gauss' aureum theorema.

Quadratic reciprocity allows you to make precise certain intuitions about the primes. More precisely, it tells you that for every finite set $p_1, p_2, ... p_n$ of primes and every function $f : \{ 1, 2, ... n \} \to \{ -1, 1 \}$ there exists an arithmetic progression such that any prime $q$ in that progression satisfies $\left( \frac{p_i}{q} \right) = f(i)$. In other words, you can get primes to behave locally independently (with respect to being or not being a quadratic residue). You can use this idea to give one proof that, for example, $\mathbb{Q}(\sqrt{2}, \sqrt{3}, ... \sqrt{p_n})$ has the degree over $\mathbb{Q}$ that you think it does; this is described here.

I guess this might as well be a separate answer. You can use quadratic reciprocity to give elementary proofs of certain special cases of Dirichlet's theorem. First, you should be aware of the following nice result and its "Euclidean" proof.

Lemma: Let $f(x) \in \mathbb{Z}[x]$ and let $P_f$ be the set of primes $p$ such that $p | f(n)$ for some $n$. Then $P_f$ is infinite.

Proof. If $f(0) = 0$ then this is obvious, so suppose otherwise. Let $p_1, p_2, ... p_n$ be a finite set of primes in $P_f$. Then for any $k$, $\frac{1}{f(0)} f(k f(0) p_1 ... p_n)$ must be divisible by a prime which is not one of the $p_i$, and choosing $k$ sufficiently large we can find a new prime $p_{n+1}$ in $P_f$.

An alternate proof is given here. Using this lemma and properties of the cyclotomic polynomials, you can prove that there exist infinitely many primes congruent to $1 \bmod n$ for any $n$ without any heavy machinery, so I will skip these cases.

Using quadratic reciprocity, you can prove that the following arithmetic progressions also contain infinitely many primes:

• $11 \bmod 12$: Let $f(x) = 3x^2 - 1$. Then $p | f(n)$ implies $\left( \frac{3}{p} \right) = 1$. However, we can modify the proof of the lemma to prove that infinitely many of the primes dividing $f$ must be congruent to $3 \bmod 4$. To see this, let $p_1, .. p_n$ be finitely many primes with this property and consider $f(2 p_1 ... p_n) \equiv 3 \bmod 4$. It follows that infinitely many primes $p$ satisfy $\left( \frac{3}{p} \right) = 1$ and $p \equiv 3 \bmod 4$, so by quadratic reciprocity $\left( \frac{p}{3} \right) = -1$, so $p \equiv 2 \bmod 3$. Hence $p \equiv 11 \bmod 12$. In particular, there are infinitely many primes congruent to $2 \bmod 3$ and infinitely many primes congruent to $3 \bmod 4$.

• $4 \bmod 5$: Let $f(x) = x^2 - 5$. Then $p | f(n)$ implies $\left( \frac{5}{p} \right) = 1$. Again, we can modify the proof of the lemma to prove that infinitely many of these primes are not congruent to $1 \bmod 5$. To see this, let $p_1, ... p_n$ be finitely many primes with this property, none of which are equal to $5$, and consider either $f(p_1 ... p_n)$ or $f(2 p_1 ... p_n)$, one of which is not congruent to $1 \bmod 5$ and which therefore has a prime factor which is not congruent to $1 \bmod 5$. So infinitely many primes $p$ satisfy $\left( \frac{5}{p} \right) = 1$ and $p \not \equiv 1 \bmod 5$. By quadratic reciprocity this gives $\left( \frac{p}{5} \right) = 1$, hence $p \equiv 4 \bmod 5$.

• $3 \bmod 8$: Let $f(x) = x^2 + 2$. Then $p | f(n)$ implies $\left( \frac{-2}{p} \right) = 1$. Again, we can modify the proof of the lemma to prove that infinitely many of these primes are not congruent to $1 \bmod 8$. To see this, let $p_1, ... p_n$ be finitely many primes with this property, all of which are odd, and consider $f(2p_1 ... p_n) \equiv 6 \bmod 8$. So infinitely many primes $p$ satisfy $\left( \frac{-2}{p} \right) = 1$ and $p \not \equiv 1 \bmod 8$. By quadratic reciprocity this gives $p \equiv 3 \bmod 8$.

And so on. For what progressions is it possible to give these kinds of proofs? It turns out this is possible for the progression $a \bmod n$ if and only if $a^2 \equiv 1 \bmod n$. For details, see Keith Conrad's Euclidean proofs of Dirichlet's theorem.

More generally, quadratic reciprocity is the key to writing down the Dedekind zeta functions of quadratic number fields explicitly, and trying to generalize this leads you into class field theory and so forth.

The quadratic reciprocity law in any of its forms shows that there is an un-obvious correlation between different primes. The $(p,q)$ symbol constrains the $(q,p)$ symbol. This is astonishing compared to other more "linear" theorems about congruences or unique factorization. In its 20th-century reformulations quadratic reciprocity is seen as an avatar of other reciprocity laws in geometry (reciprocity for tame symbols) and even geometric topology (linking numbers where knots play the role of primes) and although these other theorems are in some ways easier to prove, the analogies between all of them are mysterious.

Basically, if you are not shocked by this theorem, you don't completely understand it. Historically it was a hard-won, prize result and not an inevitable universal discovery like the Pythagorean formula or other theorems that were difficult in their time but found independently in many times and places. Many cultures had knowledge of basic number theoretic facts but quadratic reciprocity is one of the first signs of number theory as a science.