Quadratic Reciprocity

It is straightforward to decide whether or not the linear equation

$$ax\equiv b\pmod{n}$$

has a solution -- it has a solution if and only if $\gcd(a,n)$ divides $b$ (see Proposition 2.1.14). This chapter is about some amazing mathematics motivated by the search for a criterion for whether or not a given quadratic equation

$$ax^2 + bx + c \equiv 0\pmod{n}$$

has a solution. In many cases, the Chinese Remainder Theorem and the quadratic formula reduce this to the key question of whether a given integer $a$ is a perfect square modulo a prime $p$ .

The quadratic reciprocity law of Gauss provides a precise answer to the following question: For which primes $p$ is the image of $a$ in $(\mathbb{Z}/p\mathbb{Z}{})^*$ a perfect square? Amazingly, the answer depends only on the reduction of $p$ modulo $4a$ .

There are over a hundred proofs of the quadratic reciprocity law (see [#!qrlist!#] for a long list). In this chapter we give two proofs. The first, which we give in Section 4.3, is completely elementary and involves keeping track of integer points in intervals. It is satisfying because one can understand every detail without much abstraction, but it is unsatisfying because it is difficult to conceptualize what is going on. In sharp contrast, our second proof, which we give in Section 4.4, in more abstract and uses a conceptual development of properties of Gauss sums. You should read Sections 4.1 and 4.2, then at least one of Section 4.3 or Section 4.4, depending on your taste and how much abstract algebra you know.

In Section 4.5, we return to the computational question of actually finding square roots and solving quadratic equations in practice.