Quadratic Reciprocity
The theory of quadratic residues asks a fundamental question:
The Central Problem
The theory of quadratic residues asks a fundamental question:
Given distinct odd primes $p$ and $q$, when does the congruence
$$ x^2\equiv q\pmod p $$
have a solution?
Equivalently, when is
$$ \left(\frac{q}{p}\right)=1? $$
At first glance, the residue behavior of $q$ modulo $p$ and the residue behavior of $p$ modulo $q$ appear unrelated. The law of quadratic reciprocity reveals a remarkable symmetry between them.
This theorem is one of the deepest and most beautiful results in elementary number theory.
Statement of the Law
Theorem (Quadratic Reciprocity). Let $p$ and $q$ be distinct odd primes. Then
$$ \left(\frac{p}{q}\right) \left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2}\frac{q-1}{2}}. $$
$$ \left(\frac{p}{q}\right)\left(\frac{q}{p}\right)=(-1)^{\frac{p-1}{2}\frac{q-1}{2}} $$
Equivalently,
$$ \left(\frac{p}{q}\right)
\left(\frac{q}{p}\right) $$
unless both $p$ and $q$ are congruent to
$$ 3\pmod4. $$
If both are congruent to $3\pmod4$, then
$$ \left(\frac{p}{q}\right)
-\left(\frac{q}{p}\right). $$
Thus the residue relationship between two primes is almost symmetric.
First Examples
Consider $p=3$ and $q=11$.
Since
$$ 3\equiv3\pmod4, \qquad 11\equiv3\pmod4, $$
quadratic reciprocity predicts
$$ \left(\frac{3}{11}\right)
-\left(\frac{11}{3}\right). $$
Now
$$ 11\equiv2\pmod3, $$
and $2$ is not a square modulo $3$. Hence
$$ \left(\frac{11}{3}\right)
\left(\frac{2}{3}\right) =-1. $$
Therefore
$$ \left(\frac{3}{11}\right)=1. $$
Indeed,
$$ 5^2=25\equiv3\pmod{11}. $$
So $3$ is a quadratic residue modulo $11$.
A Symmetric Example
Now take
$$ p=13, \qquad q=17. $$
Since
$$ 13\equiv1\pmod4, $$
quadratic reciprocity gives
$$ \left(\frac{13}{17}\right)
\left(\frac{17}{13}\right). $$
Reducing modulo $13$,
$$ 17\equiv4\pmod{13}. $$
Since
$$ 2^2=4, $$
we have
$$ \left(\frac{4}{13}\right)=1. $$
Therefore
$$ \left(\frac{13}{17}\right)=1. $$
Hence $13$ is a quadratic residue modulo $17$.
Supplementary Laws
Quadratic reciprocity is accompanied by two supplementary laws describing the symbols for $-1$ and $2$.
First Supplementary Law
$$ \left(\frac{-1}{p}\right)
(-1)^{(p-1)/2}. $$
Thus:
| $p \pmod4$ | $\left(\frac{-1}{p}\right)$ |
|---|---|
| $1$ | $1$ |
| $3$ | $-1$ |
So $-1$ is a quadratic residue modulo $p$ exactly when
$$ p\equiv1\pmod4. $$
Second Supplementary Law
$$ \left(\frac{2}{p}\right)
(-1)^{(p^2-1)/8}. $$
Thus:
| $p \pmod8$ | $\left(\frac{2}{p}\right)$ |
|---|---|
| $1,7$ | $1$ |
| $3,5$ | $-1$ |
Together, these formulas allow efficient computation of Legendre symbols.
Computational Strategy
Quadratic reciprocity reduces complicated symbols to simpler ones.
Suppose we wish to compute
$$ \left(\frac{101}{383}\right). $$
Since
$$ 101\equiv1\pmod4, $$
we may reverse the symbol without changing sign:
$$ \left(\frac{101}{383}\right)
\left(\frac{383}{101}\right). $$
Reducing modulo $101$,
$$ 383\equiv80\pmod{101}. $$
Factor:
$$ 80=2^4\cdot5. $$
Thus
$$ \left(\frac{80}{101}\right)
\left(\frac{2}{101}\right)^4 \left(\frac{5}{101}\right). $$
Since the fourth power is $1$,
$$ \left(\frac{80}{101}\right)
\left(\frac{5}{101}\right). $$
Reciprocity and reduction continue until only small symbols remain.
This process resembles the Euclidean algorithm and makes quadratic residue computations practical even for large primes.
Gauss and the Theory of Congruences
Quadratic reciprocity was first conjectured by entity["people","Leonhard Euler","Swiss mathematician"] and entity["people","Adrien-Marie Legendre","French mathematician"], but the first rigorous proof was given by entity["people","Carl Friedrich Gauss","German mathematician"].
Gauss called it the “fundamental theorem” of arithmetic modulo primes.
He later discovered several different proofs. Over time, mathematicians found hundreds of proofs using methods from:
- elementary number theory,
- algebra,
- finite fields,
- Fourier analysis,
- geometry,
- topology,
- algebraic number theory.
The theorem became a gateway to modern reciprocity laws.
Structural Meaning
Quadratic reciprocity reveals that quadratic residue behavior is not random. The solvability of
$$ x^2\equiv p\pmod q $$
is closely connected to the solvability of
$$ x^2\equiv q\pmod p. $$
This hidden symmetry reflects deeper algebraic structures inside number fields.
Modern reciprocity laws generalize quadratic reciprocity to higher powers and more general fields. These generalizations eventually lead to class field theory and the Langlands program.
Thus quadratic reciprocity stands at the beginning of one of the main structural themes of modern number theory.