# Quadratic Reciprocity

## 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.