The Central Problem

The theory of quadratic residues asks a fundamental question:

Given distinct odd primes $p$ and $q$, when does the congruence

have a solution?

Equivalently, when is

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



Equivalently,

$$ \left(\frac{p}{q}\right)

\left(\frac{q}{p}\right) $$

unless both $p$ and $q$ are congruent to

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

quadratic reciprocity predicts

$$ \left(\frac{3}{11}\right)

-\left(\frac{11}{3}\right). $$

Now

and $2$ is not a square modulo $3$. Hence

$$ \left(\frac{11}{3}\right)

\left(\frac{2}{3}\right) =-1. $$

Therefore

Indeed,

So $3$ is a quadratic residue modulo $11$.

A Symmetric Example

Now take

Since

quadratic reciprocity gives

$$ \left(\frac{13}{17}\right)

\left(\frac{17}{13}\right). $$

Reducing modulo $13$,

Since

we have

Therefore

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:

So $-1$ is a quadratic residue modulo $p$ exactly when

Second Supplementary Law

$$ \left(\frac{2}{p}\right)

(-1)^{(p^2-1)/8}. $$

Thus:

Together, these formulas allow efficient computation of Legendre symbols.

Computational Strategy

Quadratic reciprocity reduces complicated symbols to simpler ones.

Suppose we wish to compute

Since

we may reverse the symbol without changing sign:

$$ \left(\frac{101}{383}\right)

\left(\frac{383}{101}\right). $$

Reducing modulo $101$,

Factor:

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

is closely connected to the solvability of

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.