Quadratic Residues and the Legendre Symbol

One-line: A quadratic residue mod

p

is a nonzero square in

Z / p Z

, and the Legendre symbol

(\frac{a}{p}) \in {+ 1, - 1, 0}

encodes whether

a

is such a square. Key result: Euler's criterion gives

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

, and quadratic reciprocity relates

(\frac{p}{q})

(\frac{q}{p})

. Applies in: elementary and algebraic number theory, primality testing, cryptography, the theory of

L

-functions. Who/when: Euler (1750s), Legendre (1798), Gauss (first proof of reciprocity, 1796/1801).

For an odd prime $p$ , an integer $a$ coprime to $p$ is a quadratic residue (QR) if the congruence $x^{2} \equiv a (mod p)$ has a solution, and a quadratic nonresidue (QNR) otherwise. The Legendre symbol $(\frac{a}{p})$ packages this dichotomy into a completely multiplicative function valued in ${\pm 1, 0}$ , transforming questions about square roots mod $p$ into algebra over the finite field $F_{p}$ . This matters because solvability of $x^{2} \equiv a$ is the simplest nontrivial local condition in number theory — the seed from which class field theory and the Langlands program grow. The surprising fact, which Gauss called the theorema aureum ("golden theorem"), is quadratic reciprocity: whether $p$ is a square mod $q$ is governed by whether $q$ is a square mod $p$ , even though these two questions concern entirely different finite fields, with a correction term depending only on $p, q mod 4$ .

The Core Insight

The nonzero residues mod $p$ form a cyclic group $(Z / p Z)^{\times}$ of even order $p - 1$ . The squaring map $x \mapsto x^{2}$ is a 2-to-1 homomorphism, so exactly half the residues are squares. The Legendre symbol is precisely the unique nontrivial homomorphism $(Z / p Z)^{\times} \to {\pm 1}$ — the quadratic character — and every deep theorem about residues (Euler's criterion, Gauss's lemma, reciprocity) is a statement about this character. Reciprocity itself is the assertion that a character mod $p$ , restricted to the prime $q$ , secretly carries the same arithmetic information as a character mod $q$ restricted to $p$ — a primordial instance of the duality at the heart of reciprocity laws.

Formal Statement

Quadratic Residue

Let $p$ be an odd prime and $a \in Z$ with $g cd (a, p) = 1$ . Then $a$ is a quadratic residue modulo $p$ if there exists $x \in Z$ with

x^{2} \equiv a (mod p),

and a quadratic nonresidue otherwise. The set of residue classes that are QRs is denoted

QR_{p} \subseteq (Z / p Z)^{\times}

⟳This is a definition; the existence of

x

is equivalent to

a

lying in the image of the squaring map on

(Z / p Z)^{\times}

Legendre Symbol

For an odd prime $p$ and integer $a$ , the Legendre symbol is

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

⟳The trichotomy partitions

Z / p Z

into the zero class and the two fibers of the squaring map on the unit group.

Here $p$ is the prime "modulus" and $a$ the "numerator"; the symbol depends only on $a mod p$ . Symbols: $g cd$ = greatest common divisor; $(Z / p Z)^{\times}$ = multiplicative group of units; $F_{p}$ = field with $p$ elements.

Counting and Multiplicativity

Among the $p - 1$ nonzero residues mod $p$ , exactly $\frac{p - 1}{2}$ are QRs and $\frac{p - 1}{2}$ are QNRs. The Legendre symbol is completely multiplicative:

(\frac{ab}{p}) = (\frac{a}{p}) (\frac{b}{p}) for all a, b \in Z .

⟳The squaring map

σ : x \mapsto x^{2}

on the cyclic group

(Z / p Z)^{\times}

has kernel

{\pm 1}

of order

2

, so

∣ im σ ∣ = (p - 1) /2

; multiplicativity follows because

(\frac{\cdot}{p})

is a group homomorphism into

{\pm 1}

Euler's Criterion

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

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

⟳

a^{p - 1} \equiv 1

by Fermat, so

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

; the value is

+ 1

iff

a

lies in the unique index-2 subgroup of QRs, which is exactly the set of solutions to

y^{(p - 1) /2} = 1

Quadratic Reciprocity

For distinct odd primes $p, q$ ,

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

with the two supplementary laws

(\frac{- 1}{p}) = (- 1)^{\frac{p - 1}{2}}, (\frac{2}{p}) = (- 1)^{\frac{p ^{2} - 1}{8}} .

⟳

(\frac{- 1}{p})

follows directly from Euler's criterion;

(\frac{2}{p})

and the main law follow from Gauss's lemma by counting lattice points, or from Gauss sums in

Q (ζ_{p})

Why It Holds / Derivation

Euler's Criterion

Let $g$ be a primitive root mod $p$ , so $(Z / p Z)^{\times} = ⟨ g ⟩$ is cyclic of order $p - 1$ .

Step 1. Write

a \equiv g^{k}

. Then

a

is a QR iff

a = (g^{m})^{2} = g^{2 m}

for some

m

, i.e. iff

k

is even, since the squares are exactly the elements of even index. Step 2. Compute

a^{(p - 1) /2} = g^{k (p - 1) /2}

. By Lagrange,

g

has exact order

p - 1

, so

g^{(p - 1) /2}

has order

2

, meaning

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

. Step 3. Therefore

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

. This equals

+ 1

iff

k

is even (QR) and

- 1

iff

k

is odd (QNR), matching equation [2]. Since

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

and

\pm 1

are distinct mod

p

(as

p

is odd), the congruence determines the symbol exactly.

■

Quadratic Reciprocity via Gauss's Lemma (sketch)

Step 1 — Gauss's Lemma. Fix

a

coprime to

p

and let

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

. Reduce each

a s

(

s \in S

) into the symmetric range

(- p /2, p /2)

and let

μ

be the number of negative reductions. Then

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

⟳The absolute values of the reductions are a permutation of

S

, so multiplying gives

a^{(p - 1) /2} \prod s \equiv (- 1)^{μ} \prod s

; cancel

\prod s

and apply Euler's criterion.

Step 2 — Counting $μ$ for $a = q$ . The number

μ

counts lattice points under a line. Set

T (q, p) = s = 1 \sum (p - 1) /2 ⌊ \frac{q s}{p} ⌋,

⟳

⌊ q s / p ⌋

counts integer multiples of

p

below

q s

; summing these "wraps" controls the parity

μ \equiv T (mod 2)

when

q

is odd.

so $(\frac{q}{p}) = (- 1)^{T (q, p)}$ .

Step 3 — Lattice-point symmetry (Eisenstein). The lattice points strictly inside the rectangle

(0, \frac{p}{2}) \times (0, \frac{q}{2})

are split by the diagonal

p y = q x

(no lattice point lies on it since

p \neq = q

). Counting below the diagonal gives

T (q, p)

and above gives

T (p, q)

, hence

T (q, p) + T (p, q) = \frac{p - 1}{2} \cdot \frac{q - 1}{2} .

⟳Total interior lattice points equal

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

and the diagonal hits none, so the two triangular counts sum to the total.

Step 4 — Conclude. Therefore

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

⟳Multiply the two Gauss-lemma expressions and substitute equation [9].

which is equation [5]. $■$

Carl Friedrich Gauss | 1777–1855

Gauss discovered quadratic reciprocity at age 18 (1795) and gave the first complete proof in 1796, publishing it in the Disquisitiones Arithmeticae (1801). He prized the result so highly that he returned to it throughout his life, ultimately producing eight distinct proofs using induction, Gauss's lemma, Gauss sums, cyclotomy, and the theory of forms. His search for higher reciprocity laws (cubic, biquadratic) forced him to invent the Gaussian integers $Z [i]$ and launched algebraic number theory. The Legendre symbol's name honors Legendre, but its deepest structural theorem is irreducibly Gaussian.

Building Intuition

Think of $(Z / p Z)^{\times}$ as a clock with $p - 1$ hours arranged in a circle, where "multiply by $g$ " rotates you one hour. Squaring doubles your hour-position, so you can only land on even hours — and those even hours are exactly the QRs. The Legendre symbol asks: "is your hour even or odd?" That parity question is preserved under multiplication (even+even=even, odd+odd=even), which is why the symbol is multiplicative.

Reciprocity is more startling. There's no obvious reason that the parity of $q$ 's position in $p$ 's clock should relate to the parity of $p$ 's position in $q$ 's clock — they are different clocks. Gauss's lattice-point proof reveals the hidden link: both parities are counting lattice points in the same rectangle, just split by its diagonal. The $(- 1)^{\frac{p - 1}{2} \frac{q - 1}{2}}$ correction is simply "are both primes $\equiv 3 mod 4$ ?" — if so the symbols flip, otherwise they agree.

The squaring map on $(\mathbb{Z}/11\mathbb{Z})^\times$ folds the unit circle onto the QRs

Worked Examples

Is 30 a quadratic residue mod 53?

Given:

p = 53

(prime,

\equiv 1 mod 4

a = 30

. 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 — $(\frac{2}{53})$ : Since

53 \equiv 5 (mod 8)

, the supplementary law [6] gives

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

. Step 3 — $(\frac{3}{53})$ : Both

3 \equiv 3

53 \equiv 1 (mod 4)

, so the correction

(- 1)^{1 \cdot 26} = + 1

; reciprocity [5] gives

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

(since

2

is a QNR mod 3). Step 4 — $(\frac{5}{53})$ :

5 \equiv 1 mod 4

so no sign flip:

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

. Squares mod 5 are

{1, 4}

, so

3

is a QNR:

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

. Step 5 — Combine:

(- 1) (- 1) (- 1) = - 1

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

Find a square root of 7 mod 23 using Euler's criterion

Given:

p = 23 \equiv 3 (mod 4)

a = 7

. Step 1 — Confirm $7$ is a QR via [4]: Compute

7^{(23 - 1) /2} = 7^{11} (mod 23)

. Successively:

7^{2} = 49 \equiv 3

7^{4} \equiv 3^{2} = 9

7^{8} \equiv 9^{2} = 81 \equiv 12

, so

7^{11} = 7^{8} \cdot 7^{2} \cdot 7 \equiv 12 \cdot 3 \cdot 7 = 252 \equiv 252 - 230 = 22 \equiv - 1

Wait — that yields $- 1$ , so $7$ would be a nonresidue. Recheck: $12 \cdot 3 = 36 \equiv 13$ ; $13 \cdot 7 = 91 \equiv 91 - 69 = 22 \equiv - 1$ . Indeed $(\frac{7}{23}) = - 1$ , so no square root exists. Replace target by $a = 2$ .

Step 2 — Test $a = 2$ :

23 \equiv 7 (mod 8)

, so

(\frac{2}{23}) = + 1

by [6]: a root exists. Step 3 — Extract root (Tonelli for $p \equiv 3 mod 4$ ): when

p \equiv 3 (mod 4)

, a root of a QR

a

x \equiv a^{(p + 1) /4}

. Here

(p + 1) /4 = 6

, so

x \equiv 2^{6} = 64 \equiv 64 - 46 = 18 (mod 23)

. Step 4 — Verify:

1 8^{2} = 324 = 14 \cdot 23 + 2 = 322 + 2

, so

1 8^{2} \equiv 2 (mod 23)

. ✓

2 \equiv \pm 18 \equiv {18, 5} (mod 23) .

Common Misconceptions

The Legendre symbol is not a fraction.

(\frac{a}{p})

is a multiplicative symbol, not division;

(\frac{6}{p}) = (\frac{2}{p}) (\frac{3}{p})

but it is NOT "two thirds" of anything. " $(\frac{a}{p}) = 1$ tells you the square root." It only certifies existence, not a value. Extracting the root (the Tonelli–Shanks algorithm) is a separate, harder task — though still polynomial time. Multiplicativity is in the numerator only.

(\frac{a}{p}) (\frac{a}{q}) \neq = (\frac{a}{pq})

as Legendre symbols (the right side isn't even defined for composite

pq

); the analogous denominator multiplicativity belongs to the Jacobi Symbol, whose value

+ 1

does not imply

a

is a QR. Jacobi symbol $+ 1$ does not mean quadratic residue. Take

n = 15 = 3 \cdot 5

and

a = 2

. The Jacobi symbol factors as

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

Yet

2

is not a square mod

15

: the squares mod

15

are

{0, 1, 4, 6, 9, 10}

, and

2

is absent. The two

- 1

's cancel in the Jacobi symbol, masking that

2

is a nonresidue modulo both prime factors. This is exactly why Solovay–Strassen primality testing must use the Jacobi symbol but interprets failure carefully.

Connections

The Legendre symbol is the quadratic case of a vast hierarchy. Replacing the prime modulus by a composite gives the Jacobi Symbol (still multiplicative, computable without factoring); extending to all of $Q$ and beyond gives the Hilbert Symbol and the Power Residue Symbol. Euler's criterion realizes the symbol as the unique quadratic Dirichlet Character mod $p$ , linking residues to L-functions and Dirichlet Series via $L (s, χ)$ for the Kronecker symbol $χ$ . Quadratic reciprocity is the abelian, degree-2 shadow of Class Field Theory and ultimately the Artin Reciprocity Law; Gauss's sum-based proof connects it to Cyclotomic Fields $Q (ζ_{p})$ and Gauss Sums. The count of QRs and the distribution of $(\frac{a}{p})$ feed directly into Character Sums and the Pólya–Vinogradov Inequality.

Real-World Applications

Solovay–Strassen primality test: uses the Jacobi symbol and Euler's criterion to probabilistically certify primality — historically central to RSA key generation.
Tonelli–Shanks square-root extraction: computing square roots mod $p$ underpins decompression of elliptic-curve points (from $x$ to $y$ ) in protocols like ECDSA and EdDSA.
Goldwasser–Micali cryptosystem: the first probabilistic public-key scheme, whose semantic security rests on the quadratic residuosity problem — distinguishing QRs from QNRs mod a composite $N = pq$ without its factorization.
Rabin cryptosystem: encryption is squaring mod $N$ ; decryption requires square roots mod $p$ and $q$ combined by CRT, with security provably equivalent to factoring.
Paillier and Cocks identity-based encryption: Cocks's IBE scheme manipulates Jacobi symbols of ciphertext components.
Quadratic-residue (QR) error-correcting codes: a class of cyclic codes (including the binary Golay code as a special case) whose defining set is the QRs mod a prime.
Pseudorandom generators: the Blum–Blum–Shub generator iterates $x \mapsto x^{2} mod N$ , with output bits secured by quadratic residuosity.

Historical Development

1640s — Fermat states results on which primes are sums of two squares, implicitly governed by $(\frac{- 1}{p})$ .
1750s — Euler conjectures the reciprocity relation in the language of which primes divide values of quadratic forms, and proves Euler's criterion.
1785 — Legendre states the law of quadratic reciprocity and introduces the symbol notation, but his proofs assume the existence of primes in arithmetic progressions (then unproven), leaving gaps.
1796 — Gauss, aged 18, gives the first rigorous and complete proof (his "first proof," by induction).
1801 — Publication of Disquisitiones Arithmeticae, presenting the theorema aureum with multiple proofs and the full theory of forms.
1808–1832 — Gauss develops further proofs, including those via Gauss sums and biquadratic reciprocity over $Z [i]$ .
1844–1850 — Eisenstein gives elegant lattice-point and trigonometric proofs; Eisenstein and Jacobi establish cubic and quartic reciprocity.
1882 — Kronecker and Weber extend the symbol (Kronecker symbol) and frame reciprocity within cyclotomic theory.
1927 — Emil Artin proves the Artin reciprocity law, subsuming quadratic reciprocity as the simplest abelian case and crowning class field theory.

Subtleties & Limits

Least quadratic nonresidue. Let

n_{p}

be the smallest positive QNR mod

p

. Vinogradov conjectured

n_{p} = O (p^{ε})

for every

ε > 0

. Under the Generalized Riemann Hypothesis, Ankeny proved

n_{p} = O ((lo g p)^{2})

; unconditionally the best bound (Burgess) is roughly

n_{p} = O (p^{1/ (4 e) + ε})

— far from the conjecture. The truth is believed to be

n_{p} \leq (lo g p)^{1 + o (1)}

, but this remains open. Distribution and pseudorandomness. Whether the sequence

(\frac{1}{p}), (\frac{2}{p}), \dots

behaves like a random

\pm 1

sequence is captured by character-sum bounds; the Pólya–Vinogradov inequality gives

\sum_{a = M + 1}^{M + N} (\frac{a}{p}) = O (p lo g p)

, and improving the

p

factor (the Pólya–Vinogradov / Burgess problem) is a deep open question tied to GRH. Higher reciprocity and Langlands. Quadratic reciprocity generalizes to Artin reciprocity for abelian extensions; the nonabelian reciprocity laws sought by the Langlands program remain largely conjectural, making the Legendre symbol the fully understood tip of a vast iceberg.

Quadratic Residues and the Legendre Symbol

The Core Insight

Formal Statement

Quadratic Residue

Legendre Symbol

Counting and Multiplicativity

Euler's Criterion

Quadratic Reciprocity

Why It Holds / Derivation

Euler's Criterion

Quadratic Reciprocity via Gauss's Lemma (sketch)

Carl Friedrich Gauss | 1777–1855

Building Intuition

The squaring map on $(\mathbb{Z}/11\mathbb{Z})^\times$ folds the unit circle onto the QRs

Worked Examples

Is 30 a quadratic residue mod 53?

Find a square root of 7 mod 23 using Euler's criterion

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also

Before this

Where this leads