Quadratic Residues — Mathematics Knowledge System

Overview

An integer a is a quadratic residue modulo n if it is congruent to a perfect square modulo n — that is, x² ≡ a (mod n) has a solution. For an odd prime p, exactly half of the nonzero residues 1, …, p−1 are quadratic residues and half are non-residues, a symmetry first studied systematically by Euler and Legendre and brought to full power by Gauss's law of quadratic reciprocity (which he called his 'theorema aureum,' golden theorem, and proved multiple times over his career). The Legendre symbol (a/p) packages this as +1 (residue), −1 (non-residue), or 0 (a ≡ 0), and Euler's criterion gives a direct formula for it via modular exponentiation. Quadratic residues matter well beyond pure theory: they determine which numbers have modular square roots (needed to solve quadratic congruences), they underlie primality tests (Solovay–Strassen) and cryptographic constructions (Rabin cryptosystem, Goldwasser–Micali encryption), and reciprocity lets you decide residue-ness for huge primes without factoring anything.

Intuition

Squaring on the nonzero residues mod p is exactly 2-to-1: a and p−a always square to the same value, since (p−a)² = p² − 2pa + a² ≡ a² (mod p). So the p−1 nonzero residues pair up into (p−1)/2 pairs, each producing one square — meaning exactly half the residues are 'hit' by squaring (the quadratic residues) and half are never hit (the non-residues). Quadratic reciprocity is the surprising extra fact that whether p is a square mod q is tightly linked to whether q is a square mod p, letting you flip the problem to whichever direction is easier to compute.

Formal Definition

Definition

For an odd prime p and integer a with p ∤ a, the Legendre symbol is defined and computed by Euler's criterion as:

\left(\frac{a}{p}\right) = \begin{cases} 1 & \text{if } a \text{ is a quadratic residue mod } p \\ -1 & \text{if } a \text{ is a non-residue} \\ 0 & \text{if } p \mid a \end{cases}

Legendre symbol

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

Euler's criterion

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

Law of quadratic reciprocity (odd primes p, q)

Worked Examples

Square each nonzero residue mod 7 and reduce.
$1^2, 2^2, 3^2, 4^2, 5^2, 6^2 \equiv 1, 4, 2, 2, 4, 1 \pmod 7$
The distinct values obtained are the quadratic residues.
$\{1, 2, 4\}$

Answer: The quadratic residues mod 7 are {1, 2, 4}; the non-residues are {3, 5, 6}.

Practice Problems

Difficulty 4/10

List the quadratic residues modulo 11.

Difficulty 6/10

Use Euler's criterion to determine whether 3 is a quadratic residue modulo 11 (compute 3^5 mod 11).

Difficulty 4/10

Is 2 a quadratic residue modulo 7? Justify by checking against the residue list {1, 2, 4}.

Quiz

Summary

a is a quadratic residue mod p if x² ≡ a (mod p) has a solution; exactly (p−1)/2 of the nonzero residues mod an odd prime p are residues.
The Legendre symbol (a/p) ∈ {+1, −1, 0} encodes this, and Euler's criterion computes it as a^((p−1)/2) mod p.
Gauss's law of quadratic reciprocity links (p/q) and (q/p) for odd primes, enabling fast residue determination without factoring.

References

WebsiteWikipedia — Quadratic residue