Uses of quadratic reciprocity theorem

Question

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.

Answer 1

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.

Answer 2

There is a very nice historical introduction at wikipedia.

This shows how mathematicians started to think in the direction of quadratic reciprocity after seeing the work of Fermat, and later how Legendre "almost" proved it, etc.

A lot of credit has to be attributed to Legendre. It is not Gauss alone who made contributions to arithmetic during that period. In fact, in the preface to his "Disquisitiones", Gauss acknowledges the work of Legendre.

Answer 3

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.

Answer 4

The most interesting applications requiring the services of Quadratic Reciprocity are, in my opinion, related to the field of Mathematical Cryptography!! As mentioned above, Quadratic Reciprocity is a particularly useful tool when you want to see if a number is a square mod p (p prime.) One cryptosystem in particular that requires the help of Quadratic Reciprocity is the Goldwasser-Micali public key cryptosystem; this is the case because it poses the following question based on the following information:

Let p, q be (secret) primes and let N=pq be given. For a given integer a, determine whether a is a square mod N, ie, determine if there exists an integer u satisfying u^2 = a mod N.

In particular, it is especially easy for Bob, the receiver of the message who knows how to factor N, to solve this problem because a is a square mod pq iff (a/p)=1 and (a/q)=1.

This is all from the Springer book entitled An Introduction to Mathematical Cryptography by Hoffstein, Pipher, and Silverman. This is such a great book (it was the course text for a course on Cryptography I took last spring) and I'd recommend it to anyone who is interested in learning more about the practical and totally AWESOME applications of Algebraic Number Theory. There is so much more to be said about Quadratic Reciprocity (mentioned in the end of the 3rd chapter in this book), so be sure to check it out!

Answer 5

Davenport, in "The Higher Arithmetic" Section III.5, asserts that the law of quadratic reciprocity, in its original form as conjectured by Euler, was the following assertion:

Let $a$ be any natural number and $p,q$ any primes such that $p\equiv q$ mod $4a$ or $p\equiv -q$ mod $4a$. Then $a$ is a square mod $p$ if and only if $a$ is a square mod $q$.

Davenport proves that the usual quadratic reciprocity formula for odd primes is equivalent to this assertion.

This suggests what to me is the most impressive of all applications of quadratic reciprocity: that the prime divisors of the values of quadratic polynomials fall into residue classes. One is immediately led to speculate that, more generally, the prime divisors of the values of polynomials have an intelligible structure which is somehow related to residue classes. This is really most surprising, given that polynomials combine addition and multiplication arbitrarily.

As we know, to follow up this idea it was necessary to generalize the idea of "residue class" to rings of algebraic integers, giving birth to a big chunk of modern number theory along the way.

Maybe to understand the importance of quadratic reciprocity, the main thing is not to accumulate a catalogue of specific applications, but to see quadratic reciprocity as a historical gateway to modern Number Theory.

Answer 6

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.

Answer 7

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.