Number theory — quadratic reciprocity

Quadratic reciprocity relates whether an odd prime

p

is a square modulo another odd prime

q

to whether

q

is a square modulo

p

. In words: for distinct odd primes

p, q

, the two Legendre symbols

(\frac{p}{q})

and

(\frac{q}{p})

are equal unless both

p \equiv q \equiv 3 (mod 4)

, in which case they differ in sign. It applies to solving congruences

x^{2} \equiv a (mod m)

. Conjectured by Euler and Legendre, first fully proved by Gauss (1796–1801), who called it the "golden theorem."

The law of quadratic reciprocity is one of the central results of elementary number theory. For an odd prime $p$ and an integer $a$ not divisible by $p$ , we say $a$ is a quadratic residue mod $p$ if $x^{2} \equiv a (mod p)$ has a solution, and a non-residue otherwise. The Legendre symbol $(\frac{a}{p})$ encodes this as $+ 1$ or $- 1$ . The remarkable, deeply non-obvious fact is that the solvability of $x^{2} \equiv p (mod q)$ controls and is controlled by the solvability of $x^{2} \equiv q (mod p)$ — a hidden symmetry between two apparently independent questions. The surprising fact: a question about primes "looking forward" (is $q$ a square mod $p$ ?) is answered by a question "looking backward" (is $p$ a square mod $q$ ?), with the parity of $(p - 1) /2$ and $(q - 1) /2$ as the only obstruction. Gauss alone gave eight different proofs, and the theorem became the seed of class field theory and the entire reciprocity program of modern number theory.

The Core Insight

Whether one prime is a square modulo another is not an isolated arithmetic accident — it is governed by a reciprocal relationship. The "exchange" of $p$ and $q$ in the Legendre symbol costs only a sign, and that sign is determined entirely by the residues of $p$ and $q$ modulo $4$ . Two supplementary laws handle the special cases $a = - 1$ and $a = 2$ , and together with multiplicativity these three rules let you evaluate any Legendre symbol by repeated reduction, much like the Euclidean algorithm computes a GCD.

Formal Statement

Quadratic Residue and the Legendre Symbol

Let $p$ be an odd prime and $a \in Z$ . An integer $a$ with $g cd (a, p) = 1$ is a quadratic residue mod $p$ if there exists $x$ with $x^{2} \equiv a (mod p)$ ; otherwise it is a quadratic non-residue. The Legendre symbol is defined by

(\frac{a}{p}) = ⎩ ⎨ ⎧ 0 + 1 - 1 if p ∣ a, if a is a QR mod p, if a is a non-QR mod p .

⟳This is a definition; the three-way split exhausts all residue classes since

a

is either divisible by

p

, or a nonzero square, or a nonzero non-square mod

p

Here $p$ is the (odd prime) modulus, $a$ is the integer being tested, and the symbol takes values in ${- 1, 0, + 1}$ .

Euler's Criterion

For an odd prime $p$ and $g cd (a, p) = 1$ ,

(\frac{a}{p}) \equiv a^{(p - 1) /2} (mod p) .

⟳The cyclic group

(Z / p Z)^{\times}

has order

p - 1

; squares form the unique index-2 subgroup, exactly the kernel of

a \mapsto a^{(p - 1) /2}

, whose values are

\pm 1

since

(a^{(p - 1) /2})^{2} = a^{p - 1} \equiv 1

by Fermat.

Multiplicativity of the Legendre Symbol

For an odd prime $p$ and integers $a, b$ ,

(\frac{ab}{p}) = (\frac{a}{p}) (\frac{b}{p}) .

⟳Multiply Euler's criterion [2] for

a

and for

b

;

a^{(p - 1) /2} b^{(p - 1) /2} = (ab)^{(p - 1) /2}

modulo

p

, and

\pm 1

values determined mod

p

are determined exactly.

Law of Quadratic Reciprocity

Let $p$ and $q$ be distinct odd primes. Then

(\frac{p}{q}) (\frac{q}{p}) = (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}} .

Equivalently,

(\frac{q}{p}) = (\frac{p}{q}) \cdot (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}},

so the two symbols agree unless $p \equiv q \equiv 3 (mod 4)$ , in which case they are opposite. The two supplementary laws are

(\frac{- 1}{p}) = (- 1)^{(p - 1) /2} = {+ 1 - 1 p \equiv 1 (mod 4), p \equiv 3 (mod 4),

(\frac{2}{p}) = (- 1)^{(p^{2} - 1) /8} = {+ 1 - 1 p \equiv \pm 1 (mod 8), p \equiv \pm 3 (mod 8) .

Derivation hint for [4]: the exponent $\frac{p - 1}{2} \cdot \frac{q - 1}{2}$ is odd iff both $\frac{p - 1}{2}$ and $\frac{q - 1}{2}$ are odd iff both $p, q \equiv 3 (mod 4)$ . Hints for [6],[7]: [6] is Euler's criterion at $a = - 1$ ; [7] follows from Gauss's lemma counting lattice points.

Why It Holds / Derivation

:::proof[Eisenstein's Lattice-Point Proof of [4]] We sketch the classical proof via Gauss's Lemma and lattice-point counting, the cleanest elementary route.

Step 1 — Gauss's Lemma. Let

p

be odd and

g cd (a, p) = 1

. Consider the multiples

a, 2 a, \dots, \frac{p - 1}{2} a

, each reduced to its least positive residue mod

p

. Let

μ

be the number of these residues exceeding

p /2

. Then

(\frac{a}{p}) = (- 1)^{μ} .

⟳Each reduced residue

r

with

r > p /2

is replaced by

p - r < p /2

; the resulting set is exactly

{1, \dots, (p - 1) /2}

, and the product introduces

(- 1)^{μ}

relative to

a^{(p - 1) /2} \cdot \frac{p - 1}{2}!

; cancel the factorial and apply Euler's criterion [2].

Step 2 — Count via floor functions. For odd

a

, one shows

μ \equiv \sum_{k = 1}^{(p - 1) /2} ⌊ \frac{k a}{p} ⌋ (mod 2)

, hence

(\frac{a}{p}) = (- 1)^{\sum_{k = 1}^{(p - 1) /2} ⌊ k a / p ⌋} .

⟳Write

k a = p ⌊ k a / p ⌋ + r_{k}

; summing over

k

and reducing mod 2 reorganizes the residue/non-residue counting from Step 1 into the floor sum.

Step 3 — Lattice points in a rectangle. Apply [9] with

a = q

and the symmetric expression with

a = p

. The sum

\sum_{k = 1}^{(p - 1) /2} ⌊ k q / p ⌋

counts lattice points

(k, j)

with

1 \leq k \leq \frac{p - 1}{2}

1 \leq j < k q / p

, i.e. points below the line

p y = q x

inside the rectangle

R = [1, \frac{p - 1}{2}] \times [1, \frac{q - 1}{2}]

. The symmetric sum for

p

counts points above the line. Step 4 — Add the counts. No lattice point lies on the line

p y = q x

inside

R

(that would force

p ∣ x

, impossible). So the two sums together count all lattice points of

R

k = 1 \sum (p - 1) /2 ⌊ \frac{k q}{p} ⌋ + j = 1 \sum (q - 1) /2 ⌊ \frac{j p}{q} ⌋ = \frac{p - 1}{2} \cdot \frac{q - 1}{2} .

⟳Partition the

\frac{p - 1}{2} \cdot \frac{q - 1}{2}

lattice points of the rectangle by whether they fall below or above the diagonal line, which has no interior lattice points.

Step 5 — Conclude. Multiplying the two instances of [9]:

(\frac{q}{p}) (\frac{p}{q}) = (- 1)^{\sum ⌊ k q / p ⌋ + \sum ⌊ j p / q ⌋} = (- 1)^{\frac{p - 1}{2} \cdot \frac{q - 1}{2}},

which is exactly [4].

■

Eisenstein's lattice-point count: points of the rectangle split by the diagonal $py=qx$, here $p=7,\ q=5$.

<svg viewBox="0 0 420 320" xmlns="http://www.w3.org/2000/svg">
<rect width="420" height="320" fill="#0a0e17"/>
<!-- axes -->
<line x1="40" y1="280" x2="380" y2="280" stroke="#94a3b8" stroke-width="1.5"/>
<line x1="40" y1="280" x2="40" y2="40" stroke="#94a3b8" stroke-width="1.5"/>
<text x="360" y="300" fill="#e2e8f0" font-size="12">x (k)</text>
<text x="10" y="55" fill="#e2e8f0" font-size="12">y (j)</text>
<!-- rectangle [1,3] x [1,2] in math coords, scaled -->
<!-- map: x: 1..3 -> 90..330 ; y: 1..2 -> 240..120 -->
<rect x="90" y="120" width="240" height="120" fill="none" stroke="#94a3b8" stroke-dasharray="4 3"/>
<!-- diagonal line py=qx => 7y=5x => y=(5/7)x ; through origin -->
<line x1="40" y1="280" x2="380" y2="40" stroke="#d4a853" stroke-width="2"/>
<text x="300" y="70" fill="#d4a853" font-size="12">py = qx</text>
<!-- lattice points k=1,2,3 ; j=1,2 -->
<!-- below line: count -->
<circle cx="90" cy="240" r="4" fill="#e2e8f0"/>
<circle cx="210" cy="240" r="4" fill="#e2e8f0"/>
<circle cx="330" cy="240" r="4" fill="#e2e8f0"/>
<circle cx="90" cy="120" r="4" fill="#e2e8f0"/>
<circle cx="210" cy="120" r="4" fill="#e2e8f0"/>
<circle cx="330" cy="120" r="4" fill="#e2e8f0"/>
<text x="150" y="270" fill="#94a3b8" font-size="11">below: &#8721;&#8970;kq/p&#8971;</text>
<text x="150" y="105" fill="#94a3b8" font-size="11">above: &#8721;&#8970;jp/q&#8971;</text>
<text x="90" y="305" fill="#e2e8f0" font-size="11">total = ((p-1)/2)((q-1)/2) = 3&#183;2 = 6</text>
</svg>

Carl Friedrich Gauss | 1777–1855

Gauss proved quadratic reciprocity at age 19 (April 1796) after a year of effort, calling it the theorema aureum — the golden theorem. He published the first complete proof in his 1801 masterwork Disquisitiones Arithmeticae, and over his lifetime found eight distinct proofs, driven by his quest to generalize the result to higher powers (cubic and biquadratic reciprocity). His introduction of congruence notation, his systematic theory of forms, and his Gauss sums created the language in which all later reciprocity laws are expressed. The pursuit of a "general reciprocity law" became the organizing problem of 19th- and 20th-century number theory, culminating in Artin reciprocity.

Building Intuition

Think of the Legendre symbol $(\frac{q}{p})$ as a "yes/no question about the prime $q$ , asked in the world of arithmetic mod $p$ ." Quadratic reciprocity says this question has a mirror in the world mod $q$ , and the two answers are linked. The miracle is that there's any link at all: a priori, being a square mod $p$ and being a square mod $q$ live in totally different finite worlds.

A useful mental model: the symbol behaves like a homomorphism in its top argument (multiplicativity [3]), so it suffices to know its values on $- 1$ , on $2$ , and on odd primes — and reciprocity reduces an odd prime in the top to a smaller modulus in the bottom. This makes evaluation an algorithm: each application of [5] flips and shrinks the numbers, exactly like the Euclidean algorithm, terminating quickly. The deeper modern view: $(\frac{q}{p})$ tells you how the prime $p$ splits in the field $Q (q^{*})$ , and reciprocity is the statement that splitting is governed by a congruence condition on $p$ — the first instance of "primes split according to Frobenius classes."

Worked Examples

Is 30 a quadratic residue mod 53?

Given: Evaluate

(\frac{30}{53})

; note

53

is prime,

53 \equiv 1 (mod 4)

. Step 1 — Factor and use multiplicativity [3]:

30 = 2 \cdot 3 \cdot 5

, so

(\frac{30}{53}) = (\frac{2}{53}) (\frac{3}{53}) (\frac{5}{53}) .

Step 2 — The factor $(\frac{2}{53})$ via [7]:

53 \equiv 5 (mod 8)

, and

5 \equiv - 3 (mod 8)

, so

(\frac{2}{53}) = - 1

. Step 3 — The factor $(\frac{3}{53})$ via reciprocity [5]: Since

53 \equiv 1 (mod 4)

, the sign is

+

, so

(\frac{3}{53}) = (\frac{53}{3}) = (\frac{2}{3})

. Now

(\frac{2}{3}) = - 1

(since

3 \equiv 3 (mod 8)

). So

(\frac{3}{53}) = - 1

. Step 4 — The factor $(\frac{5}{53})$ via [5]: Both with

5 \equiv 1 (mod 4)

→ sign

+

, so

= (\frac{53}{5}) = (\frac{3}{5})

. Check

3

mod

5

: squares mod 5 are

{1, 4}

, so

(\frac{3}{5}) = - 1

. Thus

(\frac{5}{53}) = - 1

. Step 5 — Combine:

(\frac{30}{53}) = (- 1) (- 1) (- 1) = - 1.

(\frac{30}{53}) = - 1 \Rightarrow 30 is a non-residue mod 53.

Solvability of $x^2 \equiv 17 \pmod{101}$

Given:

101

is prime; determine if a solution exists by computing

(\frac{17}{101})

. Step 1 — Apply reciprocity [5]:

17 \equiv 1 (mod 4)

, so the sign is

+

and

(\frac{17}{101}) = (\frac{101}{17}) .

Step 2 — Reduce the top mod 17:

101 = 5 \cdot 17 + 16

, so

101 \equiv 16 (mod 17)

, giving

(\frac{101}{17}) = (\frac{16}{17})

. Step 3 — Recognize a perfect square:

16 = 4^{2}

, hence

(\frac{16}{17}) = + 1

automatically. Step 4 — Conclude existence:

(\frac{17}{101}) = + 1.

A solution exists; in fact $x \equiv \pm 22 (mod 101)$ since $2 2^{2} = 484 = 4 \cdot 101 + 80$ ... (checking: $484 - 4 (101) = 80 \neq = 17$ ; a direct search gives $x \equiv \pm 38$ , since $3 8^{2} = 1444 = 14 \cdot 101 + 30$ — the symbol guarantees solvability without exhibiting the root).

x^{2} \equiv 17 (mod 101) is SOLVABLE, since (\frac{17}{101}) = + 1.

Common Misconceptions

The Legendre symbol is NOT defined for composite lower entries — use the Jacobi symbol carefully. The Legendre symbol

(\frac{a}{p})

requires

p

to be an odd prime. The generalized Jacobi symbol

(\frac{a}{n})

(defined for odd

n > 1

via multiplicativity over the prime factorization of

n

) also satisfies reciprocity and the supplementary laws — but a Jacobi value of

+ 1

does NOT guarantee that

a

is a quadratic residue mod

n

. For example

(\frac{2}{15}) = (\frac{2}{3}) (\frac{2}{5}) = (- 1) (- 1) = + 1

, yet

2

is a non-residue mod

15

(it's a non-residue mod both

3

and

5

). The Jacobi symbol speeds up computation but loses the QR interpretation for composite moduli. Reciprocity does NOT say the two symbols are always equal. A common error is to drop the sign factor. Take

p = 3

q = 7

, both

\equiv 3 (mod 4)

. Then

\frac{p - 1}{2} \cdot \frac{q - 1}{2} = 1 \cdot 3 = 3

is odd, so [4] gives

(\frac{3}{7}) (\frac{7}{3}) = - 1

. Check: squares mod 7 are

{1, 2, 4}

, so

(\frac{3}{7}) = - 1

; and

7 \equiv 1 (mod 3)

a square, so

(\frac{7}{3}) = (\frac{1}{3}) = + 1

. Indeed

(- 1) (+ 1) = - 1

. The symbols differ precisely because both primes are

\equiv 3 (mod 4)

— exactly the case naive "they're always equal" reasoning gets wrong.

Connections

Quadratic reciprocity sits at the crossroads of several theories. It is the simplest case of Artin Reciprocity in class field theory, where the Legendre symbol becomes an Artin symbol describing how primes split in abelian extensions. Through Gauss Sums and Cyclotomic Fields, the value $(\frac{q}{p})$ is encoded in the factorization of $p$ in $Q (ζ_{q})$ and in $Q (q^{*})$ where $q^{*} = (- 1)^{(q - 1) /2} q$ . The multiplicative structure relies on Cyclic Groups (the group $(Z / p Z)^{\times}$ being cyclic) and on Fermat's Little Theorem. Generalizations to higher powers — Cubic Reciprocity and Biquadratic Reciprocity — require working in $Z [ω]$ and $Z [i]$ , foreshadowing Algebraic Number Theory.

Real-World Applications

Primality testing — Solovay–Strassen test. A probabilistic primality test computes a Jacobi symbol $(\frac{a}{n})$ and compares it to $a^{(n - 1) /2} mod n$ ; mismatches prove compositeness. This was historically important for cryptographic key generation.
Cryptography — Goldwasser–Micali encryption. This semantically secure public-key scheme encodes bits as quadratic residues vs. pseudo-residues modulo a composite $n = pq$ ; security rests on the quadratic residuosity problem (hard without the factorization).
Computing modular square roots — Tonelli–Shanks. Before extracting a square root mod $p$ , one checks $(\frac{a}{p}) = + 1$ for solvability; this underlies point decompression on elliptic curves used in ECC and Bitcoin signatures.
Integer factorization — quadratic sieve & number field sieve. These algorithms search for $x^{2} \equiv y^{2} (mod n)$ ; residue criteria determine which primes can appear in factor bases, dramatically pruning the search.
Pseudorandom generation — Blum Blum Shub. This cryptographically secure generator iterates $x \mapsto x^{2} mod n$ with $n = pq$ , $p, q \equiv 3 (mod 4)$ ; the choice $\equiv 3 (mod 4)$ (so $- 1$ is a non-residue, via [6]) guarantees unique principal square roots.
Coding theory — quadratic residue codes. Cyclic codes (e.g. the binary Golay code, related QR codes over $F_{2}$ ) are built from the set of quadratic residues mod a prime, yielding excellent error-correcting properties.

Historical Development

1640s–1650s — Fermat observes which primes are sums of two squares ( $p \equiv 1 (mod 4)$ ), implicitly studying $(\frac{- 1}{p})$ and the residue of $- 1$ .
1744–1746 — Euler states empirical conjectures equivalent to quadratic reciprocity in correspondence and in Theoremata circa divisores numerorum, and proves Euler's criterion [2].
1785 — Legendre publishes a partial proof and introduces the Legendre symbol, formulating reciprocity in its modern symbolic form but with gaps (he assumed unproven results on primes in arithmetic progressions).
April 8, 1796 — Gauss (age 19) completes the first rigorous proof, recording the date in his diary; he names it the theorema aureum.
1801 — Gauss publishes two complete proofs in Disquisitiones Arithmeticae, founding modern number theory and introducing congruence notation.
1808–1818 — Gauss discovers further proofs (sixth proof via Gauss sums), aiming at higher reciprocity laws.
1844–1850 — Eisenstein gives elegant lattice-point and Gauss-sum proofs (the one sketched above) and, with Jacobi, advances cubic/biquadratic reciprocity.
1880s — Hilbert, Kummer recast reciprocity via the Hilbert symbol and local-global product formulas, paving the way to class field theory.
1927 — Emil Artin proves Artin reciprocity, the sweeping generalization for abelian extensions that contains quadratic reciprocity as its most basic special case.

Subtleties & Limits

Quadratic reciprocity is completely solved, but its generalizations drive active research. The Langlands program seeks a vast non-abelian reciprocity law linking Galois representations to automorphic forms; quadratic reciprocity is the abelian, rank-one tip of this iceberg. For higher power residues, Artin's reciprocity governs abelian extensions, but explicit, computable reciprocity laws for general algebraic number fields (the "explicit reciprocity laws" of Wiles, Coleman, and others in $p$ -adic settings) remain technically intricate. Open computational questions persist too: the quadratic residuosity problem — distinguishing genuine residues from pseudo-residues mod $n = pq$ without the factorization — is believed hard, but no proof of its hardness exists; if quantum factoring (Shor's algorithm) renders factoring easy, the cryptographic schemes built on it collapse. Finally, fine statistical questions about the distribution of quadratic residues (least non-residue size, related to GRH) connect to deep conjectures about $L$ -functions.

Number theory — quadratic reciprocity

The Core Insight

Formal Statement

Quadratic Residue and the Legendre Symbol

Euler's Criterion

Multiplicativity of the Legendre Symbol

Law of Quadratic Reciprocity

Why It Holds / Derivation

Eisenstein's lattice-point count: points of the rectangle split by the diagonal $py=qx$, here $p=7,\ q=5$.

Carl Friedrich Gauss | 1777–1855

Building Intuition

Worked Examples

Is 30 a quadratic residue mod 53?

Solvability of $x^2 \equiv 17 \pmod{101}$

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also

Before this

Where this leads