Quadratic Residues and the Legendre Symbol

⚡ Key Takeaways

One-line: A quadratic residue mod $p$ is a nonzero square in $\mathbb{Z}/p\mathbb{Z}$ , and the Legendre symbol $\left(\frac{a}{p}\right) \in \{+1,-1,0\}$ encodes whether $a$ is such a square. Key result: Euler's criterion gives $\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p}$ , and quadratic reciprocity relates $\left(\frac{p}{q}\right)$ to $\left(\frac{q}{p}\right)$ . 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).

💡 The Core Insight

The nonzero residues mod $p$ form a cyclic group $(\mathbb{Z}/p\mathbb{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 $(\mathbb{Z}/p\mathbb{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.

DefinitionQuadratic Residue

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

1

\quad x^2 \equiv a \pmod{p},

and a quadratic nonresidue otherwise. The set of residue classes that are QRs is denoted $\mathrm{QR}_p \subseteq (\mathbb{Z}/p\mathbb{Z})^\times$ . Derivation hint: This is a definition; the existence of $x$ is equivalent to $a$ lying in the image of the squaring map on $(\mathbb{Z}/p\mathbb{Z})^\times$ .

DefinitionLegendre Symbol

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

2

\quad \left(\frac{a}{p}\right) = \begin{cases} \phantom{-}0 & \text{if } p \mid a,\\ \phantom{-}1 & \text{if } a \text{ is a QR mod } p,\\ -1 & \text{if } a \text{ is a QNR mod } p. \end{cases}

Derivation hint: The trichotomy partitions $\mathbb{Z}/p\mathbb{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 \bmod p$ . Symbols: $\gcd$ = greatest common divisor; $(\mathbb{Z}/p\mathbb{Z})^\times$ = multiplicative group of units; $\mathbb{F}_p$ = field with $p$ elements.

TheoremCounting and Multiplicativity

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

3

\quad \left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right) \quad \text{for all } a,b \in \mathbb{Z}.

Derivation hint: The squaring map $\sigma: x \mapsto x^2$ on the cyclic group $(\mathbb{Z}/p\mathbb{Z})^\times$ has kernel $\{\pm 1\}$ of order $2$ , so $|\mathrm{im}\,\sigma| = (p-1)/2$ ; multiplicativity follows because $\left(\frac{\cdot}{p}\right)$ is a group homomorphism into $\{\pm1\}$ .

TheoremEuler's Criterion

For odd prime $p$ and $\gcd(a,p)=1$ ,

4

\quad \left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p}.

Derivation hint: $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$ .

TheoremQuadratic Reciprocity

For distinct odd primes $p,q$ ,

5

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

with the two supplementary laws

6

\quad \left(\frac{-1}{p}\right) = (-1)^{\frac{p-1}{2}}, \qquad \left(\frac{2}{p}\right) = (-1)^{\frac{p^2-1}{8}}.

Derivation hint: $\left(\frac{-1}{p}\right)$ follows directly from Euler's criterion; $\left(\frac{2}{p}\right)$ and the main law follow from Gauss's lemma by counting lattice points, or from Gauss sums in $\mathbb{Q}(\zeta_p)$ .

ProofEuler's Criterion

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

Step 1. Write $a \equiv g^k$ . Then $a$ is a QR iff $a = (g^m)^2 = g^{2m}$ 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. $\blacksquare$

∎

ProofQuadratic 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 $as$ ( $s\in S$ ) into the symmetric range $(-p/2, p/2)$ and let $\mu$ be the number of negative reductions. Then

7

\quad \left(\frac{a}{p}\right) = (-1)^{\mu}.

Derivation hint: The absolute values of the reductions are a permutation of $S$ , so multiplying gives $a^{(p-1)/2}\prod s \equiv (-1)^\mu \prod s$ ; cancel $\prod s$ and apply Euler's criterion.

Step 2 — Counting $\mu$ for $a=q$ . The number $\mu$ counts lattice points under a line. Set

8

\quad T(q,p) = \sum_{s=1}^{(p-1)/2}\left\lfloor \frac{qs}{p}\right\rfloor,

Derivation hint: $\lfloor qs/p\rfloor$ counts integer multiples of $p$ below $qs$ ; summing these "wraps" controls the parity $\mu \equiv T \pmod 2$ when $q$ is odd. so $\left(\frac{q}{p}\right) = (-1)^{T(q,p)}$ .

Step 3 — Lattice-point symmetry (Eisenstein). The lattice points strictly inside the rectangle $\big(0,\tfrac{p}{2}\big)\times\big(0,\tfrac{q}{2}\big)$ are split by the diagonal $py = qx$ (no lattice point lies on it since $p\ne q$ ). Counting below the diagonal gives $T(q,p)$ and above gives $T(p,q)$ , hence

9

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

Derivation hint: 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

10

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

Derivation hint: Multiply the two Gauss-lemma expressions and substitute equation [9]. which is equation [5]. $\blacksquare$

∎

mathematician · 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 $\mathbb{Z}[i]$ and launched algebraic number theory. The Legendre symbol's name honors Legendre, but its deepest structural theorem is irreducibly Gaussian.

🧠 Intuition

Think of $(\mathbb{Z}/p\mathbb{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 \bmod 4$ ?" — if so the symbols flip, otherwise they agree.

Figure

The squaring map on

(\mathbb{Z}/11\mathbb{Z})^\times

folds the unit circle onto the QRs

ExampleIs 30 a quadratic residue mod 53?

Given: $p = 53$ (prime, $\equiv 1 \bmod 4$ ), $a = 30$ .

Step 1 — Factor and use multiplicativity [3]: $30 = 2\cdot 3 \cdot 5$ , so

\left(\tfrac{30}{53}\right) = \left(\tfrac{2}{53}\right)\left(\tfrac{3}{53}\right)\left(\tfrac{5}{53}\right).

Step 2 — $\left(\frac{2}{53}\right)$ : Since $53 \equiv 5 \pmod 8$ , the supplementary law [6] gives $\left(\frac{2}{53}\right) = -1$ .

Step 3 — $\left(\frac{3}{53}\right)$ : Both $3\equiv 3$ , $53\equiv 1 \pmod 4$ , so the correction $(-1)^{1\cdot 26}=+1$ ; reciprocity [5] gives $\left(\frac{3}{53}\right)=\left(\frac{53}{3}\right)=\left(\frac{2}{3}\right)=-1$ (since $2$ is a QNR mod 3).

Step 4 — $\left(\frac{5}{53}\right)$ : $5\equiv 1 \bmod 4$ so no sign flip: $\left(\frac{5}{53}\right)=\left(\frac{53}{5}\right)=\left(\frac{3}{5}\right)$ . Squares mod 5 are $\{1,4\}$ , so $3$ is a QNR: $\left(\frac{3}{5}\right)=-1$ .

Step 5 — Combine: $(-1)(-1)(-1) = -1$ .

\boxed{\left(\tfrac{30}{53}\right) = -1 \;\Rightarrow\; 30 \text{ is a quadratic nonresidue mod } 53.}

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

Given: $p = 23 \equiv 3 \pmod 4$ , $a = 7$ .

Step 1 — Confirm $7$ is a QR via [4]: Compute $7^{(23-1)/2} = 7^{11} \pmod{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\cdot3 = 36\equiv 13$ ; $13\cdot 7 = 91 \equiv 91-69 = 22 \equiv -1$ . Indeed $\left(\frac{7}{23}\right) = -1$ , so no square root exists. Replace target by $a=2$ .

Step 2 — Test $a=2$ : $23 \equiv 7\pmod 8$ , so $\left(\frac{2}{23}\right) = +1$ by [6]: a root exists.

Step 3 — Extract root (Tonelli for $p\equiv 3 \bmod 4$ ): when $p\equiv 3\pmod 4$ , a root of a QR $a$ is $x \equiv a^{(p+1)/4}$ . Here $(p+1)/4 = 6$ , so $x \equiv 2^6 = 64 \equiv 64 - 46 = 18 \pmod{23}$ .

Step 4 — Verify: $18^2 = 324 = 14\cdot 23 + 2 = 322 + 2$ , so $18^2 \equiv 2 \pmod{23}$ . ✓

\boxed{\sqrt{2} \equiv \pm 18 \equiv \{18,\,5\} \pmod{23}.}

⚠️ Common mistake

The Legendre symbol is not a fraction. $\left(\frac{a}{p}\right)$ is a multiplicative symbol, not division; $\left(\frac{6}{p}\right)=\left(\frac{2}{p}\right)\left(\frac{3}{p}\right)$ but it is NOT "two thirds" of anything.

" $\left(\frac{a}{p}\right)=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. $\left(\frac{a}{p}\right)\left(\frac{a}{q}\right) \ne \left(\frac{a}{pq}\right)$ 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.

Counterexample

Jacobi symbol $+1$ does not mean quadratic residue. Take $n = 15 = 3\cdot 5$ and $a = 2$ . The Jacobi symbol factors as

\left(\tfrac{2}{15}\right) = \left(\tfrac{2}{3}\right)\left(\tfrac{2}{5}\right) = (-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.

connection

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 $\mathbb{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,\chi)$ for the Kronecker symbol $\chi$ . 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 $\mathbb{Q}(\zeta_p)$ and Gauss Sums. The count of QRs and the distribution of $\left(\frac{a}{p}\right)$ feed directly into Character Sums and the Pólya–Vinogradov Inequality.

🔬 Where this appears

⏳ History

- 1640s — Fermat states results on which primes are sums of two squares, implicitly governed by

\left(\frac{-1}{p}\right)

.

- 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

\mathbb{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.

open-problem

Least quadratic nonresidue. Let $n_p$ be the smallest positive QNR mod $p$ . Vinogradov conjectured $n_p = O(p^\varepsilon)$ for every $\varepsilon>0$ . Under the Generalized Riemann Hypothesis, Ankeny proved $n_p = O((\log p)^2)$ ; unconditionally the best bound (Burgess) is roughly $n_p = O(p^{1/(4\sqrt e)+\varepsilon})$ — far from the conjecture. The truth is believed to be $n_p \le (\log p)^{1+o(1)}$ , but this remains open.

Distribution and pseudorandomness. Whether the sequence $\left(\frac{1}{p}\right),\left(\frac{2}{p}\right),\dots$ behaves like a random $\pm1$ sequence is captured by character-sum bounds; the Pólya–Vinogradov inequality gives $\big|\sum_{a=M+1}^{M+N}\left(\frac{a}{p}\right)\big| = O(\sqrt p\log p)$ , and improving the $\sqrt 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

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also