Chapter 17 Quadratic Reciprocity
So far, we have determined at least when some quadratic congruences have solutions, but at the pace set thus far, most cases should seem beyond reach. We certainly won't want to use Theorem 16.5.2 directly for every single one.
It turns out that finding out when numbers have square roots (mod \(p\)) is not hopeless – quite the opposite is true! After raising our spirits with some simple but powerful observations, we will make our way to the great theorem that is the title of this chapter. Using it, we will derive almost effortlessly results regarding quadratic residues that originally took a great deal of work.
Summary: Quadratic Reciprocity
Here, we harness the power of the Legendre symbol to find a deep correlation between solutions of two seemingly unrelated congruences – a correlation that enables us to tell very quickly whether any quadratic congruence has a solution!
Section 17.1 reinterprets and extends some of our work with quadratic residues in terms of the Legendre symbol.
Next, there is a long buildup to the challenging, but rewarding, power of Eisenstein's Criterion for the Legendre Symbol.
We use this criterion to compute when \(3\) is a quadratic residue in Proposition 17.3.4.
The next section has the core of the chapter. Not only do we state Quadratic Reciprocity, we interpret it (such as in Figure 17.4.4) and show how to use it efficiently to compute (such as in Example 17.4.7). Finally, we introduce the Jacobi symbol in Definition 17.4.9.
Section 17.5 gives several interesting applications.
Section 17.6 has a geometric proof of the main theorem.
The Exercises encourage not just computation of a wide variety of Legendre symbols using quadratic reciprocity, but filling in gaps in proofs (such as about Germain primes) and proving your own facts about when certain numbers are quadratic residues.