In our previous lesson, we explored the Legendre and Jacobi symbols and saw how the rules of quadratic reciprocity provide a powerful computational shortcut, allowing us to determine quadratic residuosity with an efficiency comparable to the Euclidean algorithm. We took these rules—the "what" and the "how"—on faith. Now, we will justify them by exploring the "why."
Today's lesson fulfills the promise to delve into the proof of the Law of Quadratic Reciprocity, a result Carl Friedrich Gauss called the aureum theorema, the "golden theorem." We will formally state the theorem, explore one of its many elegant proofs, and examine how it can be applied not just to compute symbols, but to answer deeper theoretical questions about the structure of prime numbers. This exploration will provide a fitting capstone to our study of elementary number theory before we move to more abstract algebraic structures.
The Law of Quadratic Reciprocity: Statement and Application
Let's begin by formally restating the law and its essential companions, which you used for computation in the last lesson. These are cornerstones of number theory.
[PDF] Quadratic reciprocity and computing modular square roots
This chapter from Victor Shoup's A Computational Introduction to Number Theory and Algebra provides a concise and formal statement of the Law of Quadratic Reciprocity and its supplements.
Please review Theorem 12.1 in the section titled "The Legendre symbol". You are already familiar with these rules from our previous lesson, but pay close attention to the formal statement: Part (i) is Euler's Criterion. Parts (ii) and (iii) describe the multiplicative and congruence properties. Part (iv) is the second supplement for (\frac{2}{p}). Part (v) is the Law of Quadratic Reciprocity itself. The text also clarifies an important detail: (\frac{p}{q}) = (\frac{q}{p}) unless both primes are congruent to 3 \pmod 4, in which case (\frac{p}{q}) = -(\frac{q}{p}).
While we've applied these rules to compute specific Legendre symbols, their power extends to revealing broad patterns among prime numbers. A classic application is to characterize the primes p for which a fixed integer a is a quadratic residue. This goes beyond a single calculation and describes an entire class of numbers.
The following examples from the same text demonstrate this beautifully. They require careful case analysis and combine the reciprocity law with the Chinese Remainder Theorem, which we studied earlier.
[PDF] Quadratic reciprocity and computing modular square roots
These examples show how to use the law to derive general conditions on primes.
Please read Example 12.1 and Example 12.2. Example 12.1 characterizes primes p for which 5 is a quadratic residue. Notice how the condition 5 \equiv 1 \pmod 4 simplifies the application of the law. Example 12.2 does the same for 3. Here, since 3 \equiv 3 \pmod 4, the analysis splits into two cases depending on whether p \equiv 1 \pmod 4 or p \equiv 3 \pmod 4. This leads to a final characterization modulo 12.
These examples illustrate the profound structural information encoded in the Law of Quadratic Reciprocity. It connects the behavior of a prime p modulo q with the behavior of q modulo p, a surprising and deep symmetry.
Proving the Golden Theorem
There are over 200 published proofs of the Law of Quadratic Reciprocity. We will explore a particularly elegant one based on a geometric argument by Eisenstein, which is a refinement of one of Gauss's original proofs. The core idea is to count the number of integer points inside a specific rectangle in two different ways.
The proof is elementary but has several steps. We will use the same text from Victor Shoup, which lays out the argument with precision.
Step 1: Gauss's Lemma
The first tool we need is Gauss's Lemma. It provides an alternative way to compute the Legendre symbol by counting how many of the integers have a least positive residue modulo p that is greater than .
[PDF] Quadratic reciprocity and computing modular square roots
This section introduces and proves Gauss's Lemma.
Find Theorem 12.2 (Gauss' lemma) and read its statement and proof. The key idea in the proof is to cleverly rearrange a set of residues to form the product (\frac{p-1}{2})! and relate it back to Euler's criterion.
Step 2: From Counting to a Sum of Floors
The next step connects the count from Gauss's Lemma to a sum involving the floor function. This might seem like a purely technical step, but it is the bridge that allows us to use a geometric counting argument.
[PDF] Quadratic reciprocity and computing modular square roots
This theorem establishes the crucial link between the Legendre symbol and a sum of floor functions.
Now, please read the statement and proof of Theorem 12.3. The proof is an algebraic manipulation that builds directly on the notation and results from the proof of Gauss's Lemma. The final result is: \left(\frac{a}{p}\right) = (-1)^t \quad \text{where} \quad t = \sum_{j=1}^{(p-1)/2} \lfloor ja/p \rfloor for an odd integer a. This theorem also proves the second supplement, (\frac{2}{p}) = (-1)^{(p^2-1)/8}, as a byproduct.
Step 3: The Geometric Proof
We now have all the pieces to prove the main law. The proof counts the integer lattice points in a rectangle of size in two distinct ways.
- Directly: The number of points is simply .
- Geometrically: The line cuts the rectangle into two regions. The number of points in each region can be expressed using the sum-of-floors formula from Theorem 12.3.
By equating these two counts, the law emerges.
[PDF] Quadratic reciprocity and computing modular square roots
This is the final step, proving the main theorem.
Read the statement and proof of Theorem 12.4. The proof is remarkably concise. It defines a set S of integer pairs (x, y) which are the lattice points in the rectangle. It then partitions S into two subsets based on whether they are above or below the line qx = py. The size of these subsets directly corresponds to the sums we found in Theorem 12.3, leading to the final result.
To help visualize this geometric argument, the following video provides an excellent walkthrough of the same proof strategy.
Number Theory | Quadratic Reciprocity
This video from the channel Michael Penn walks through the geometric proof of quadratic reciprocity.
Watch the segment from the proof, which starts by setting up the geometric framework of counting lattice points in a rectangle. The logic closely follows the proof you just read in Theorem 12.4.
For Further Exploration: A Combinatorial Proof
The proof we studied is just one of many. For a completely different and highly inventive perspective, you might enjoy a proof based on the properties of permutations, known as Zolotarev's Lemma. The Mathologer channel presents this proof in the context of a card-dealing trick.
Why did they prove this amazing theorem in 200 different ways? Quadratic Reciprocity MASTERCLASS
This video offers a very different, combinatorial proof of quadratic reciprocity. It is a more advanced take, but your background in discrete mathematics should make it accessible.
If you're curious, watch the main body of the video starting from the proof section. The argument translates the Legendre symbols and the sign factor of the LQR into properties (specifically, the sign) of certain permutations of a deck of p \times q cards. This approach provides a beautiful link between number theory and combinatorial/algebraic structures, which is a perfect preview for our next module.
Conclusion
In this lesson, we have not only stated the Law of Quadratic Reciprocity but have also rigorously proven it, moving from its application to its justification. This journey into one of number theory's most celebrated results highlights the deep, often surprising, connections that govern the world of integers.
Key Takeaways:
- The Law of Quadratic Reciprocity, along with its supplements, establishes a fundamental relationship between pairs of prime numbers, determining whether one is a square modulo the other.
- The law can be applied to characterize entire sets of primes, for instance, by determining for which primes
pa number like 3 is a quadratic residue. - We explored an elegant proof based on Gauss's Lemma and a geometric argument of counting lattice points within a rectangle in two different ways. This method connects the algebraic statement of the law to a spatial configuration.
- The existence of over 200 proofs hints at the theorem's centrality and its connections to many different areas of mathematics.
This lesson concludes our foundational module on number theory. We have built a solid toolkit, from the Extended Euclidean Algorithm to the Law of Quadratic Reciprocity. In our next lesson, we will begin Module 2, moving to a higher level of abstraction to study the fundamental algebraic structures—groups, rings, and fields—that form the language of modern cryptography.