It is no exaggeration to call the Quadratic Reciprocity Theorem one of the most important in number theory. The theorem describes when a prime \(p\) “is a square” modulo another prime \(q.\) The simplest nontrivial example concerns the prime \(q=7.\) Modulo \(7,\) it turns out that \(p=2\) is a square, because
\[3^2 = 9 \equiv 2\,{\rm{(mod}}\,7);\]
in this case, \(2\) is called a quadratic residue \({\rm{(mod}}\,7).\) There are several equivalent formulations of quadratic reciprocity; one of the clearest is due to Adrien-Marie Legendre [13]:
Theorem 2.1. Let \(p\) and \(q\) be odd primes. Then:
Legendre published the first proof of this theorem in his Essai sur la théorie des nombres in 1798 [13]. Gauss had apparently found a proof in 1796 (see [3]), although this wasn't published until 1801, in his Disquisitiones Arithmeticae. Gauss was very fond of this theorem—he eventually gave six different proofs! Efforts to extend the theorem to higher degrees (e.g., cubic reciprocity) and to rings beyond the integers formed a crucial part of the development of number theory in the nineteenth century. In fact, David Hilbert's ninth problem, to “Find the most general law of the reciprocity theorem in any algebraic number field,” reflects that even at the dawn of the 20th century, reciprocity continued to vex number theorists. (A part of this story can be found in [17, pp. 163–257].)