The Law of Quadratic Reciprocity: History, Statement, and Significance

Introduction

Among the most celebrated results in elementary number theory is the Law of Quadratic Reciprocity (LQR). First discovered by Carl Friedrich Gauss in 1796 at the age of nineteen, and later published in his Disquisitiones Arithmeticae (1801), the theorem reveals a deep and unexpected symmetry in the behavior of quadratic residues. Gauss himself referred to it as the Theorema Aureum ("Golden Theorem"), and throughout his lifetime he produced no fewer than eight distinct proofs, including some regarded as masterpieces of mathematical elegance.

Quadratic Residues and the Legendre Symbol

Let $p$ be an odd prime. An integer $a$ is called a quadratic residue modulo $p$ if there exists an integer $x$ such that \[ x^2 \equiv a \pmod{p}. \] Otherwise, $a$ is called a quadratic nonresidue modulo $p$.

The Legendre symbol is a convenient notation for expressing this property: \[ \left( \frac{a}{p} \right) = \begin{cases} 0 & \text{if } p \mid a, \\ 1 & \text{if $a$ is a quadratic residue modulo $p$}, \\ -1 & \text{if $a$ is a quadratic nonresidue modulo $p$}. \end{cases} \] In the Law of Quadratic Reciprocity, we consider only distinct odd primes $p$ and $q$, so the zero case does not occur.

Statement of the Law

The Law of Quadratic Reciprocity states that for distinct odd primes $p$ and $q$, \[ \left( \frac{p}{q} \right) \cdot \left( \frac{q}{p} \right) = \begin{cases} 1 & \text{if at least one of $p$ or $q$ is congruent to $1 \pmod{4}$}, \\ -1 & \text{if both $p$ and $q$ are congruent to $3 \pmod{4}$}. \end{cases} \] This remarkable relation connects the question “Is $p$ a square modulo $q$?” with the question “Is $q$ a square modulo $p$?” in a precise and predictable way.

A Correct Worked Example

Consider $p = 7$ and $q = 3$, both primes congruent to $3 \pmod{4}$.

Step 1: Evaluate $\left( \frac{7}{3} \right)$

Since $7 \equiv 1 \pmod{3}$ and $1$ is a quadratic residue modulo $3$ (indeed, $1^2 \equiv 1$), we have: \[ \left( \frac{7}{3} \right) = 1. \]

Step 2: Evaluate $\left( \frac{3}{7} \right)$

The quadratic residues modulo $7$ are: \[ 1^2 \equiv 1,\quad 2^2 \equiv 4,\quad 3^2 \equiv 2. \] Thus, the set of quadratic residues modulo $7$ is $\{1, 2, 4\}$. Since $3$ is not among them, \[ \left( \frac{3}{7} \right) = -1. \]

Step 3: Verify the Law

We compute: \[ \left( \frac{7}{3} \right) \cdot \left( \frac{3}{7} \right) = (1) \cdot (-1) = -1. \] Since both $p$ and $q$ are congruent to $3 \pmod{4}$, the law predicts the product should be $-1$, which agrees perfectly with our computation.

Historical Significance

The Law of Quadratic Reciprocity stands as a cornerstone of number theory, influencing vast areas such as higher reciprocity laws, algebraic number theory, and modern cryptography. Gauss's fascination with the theorem led to numerous innovative proofs, each illuminating the result from a different perspective.

Applications

• Cryptography: Algorithms such as the Goldwasser--Micali cryptosystem rely on properties of quadratic residues.
• Primality Testing: Tests like the Solovay--Strassen algorithm incorporate reciprocity to verify large primes efficiently.
• Mathematical Structure: It underpins patterns in modular arithmetic and inspires results in algebraic number theory.

Conclusion

The Law of Quadratic Reciprocity is an elegant and profound statement about the symmetry of quadratic residues between two odd primes. Gauss's designation of it as the Golden Theorem remains apt: it is a shining example of how deep truths can emerge from simple numerical questions.