Engineering / Mathematics — Quadratic Residues
Quadratic Residues
Quadratic residues modulo a prime, the exact split into residues and non-residues, and the group-theoretic reason for it.
Executive summary
An element is a quadratic residue modulo n if it is a square. Modulo an odd prime, exactly half the units are residues, and this split is a consequence of the squaring map being two-to-one on a cyclic group.
The structure governs everything downstream: the Legendre symbol, reciprocity, square root algorithms and the quadratic residuosity assumption.
Learning objectives
- Define quadratic residues and count them modulo a prime.
- Derive Euler's criterion from cyclicity.
- Extend the picture to composite moduli.
01Definition and the count
Quadratic residue
An element a ∈ Z_n* is a quadratic residue modulo n if x² ≡ a (mod n) has a solution. Otherwise it is a non-residue.
Half the units are residues
For an odd prime p, exactly (p−1)/2 of the units modulo p are quadratic residues.
Reason. The squaring map x ↦ x² on Z_p* has kernel {1, −1} of size 2, so its image has index 2.
Equivalently, since Z_p* is cyclic with generator γ, an element γ^k is a square exactly when k is even. The residues are the even powers of a generator, forming the unique subgroup of index 2.
02Euler's criterion
Euler's criterion
For an odd prime p and a not divisible by p,
a^{(p−1)/2} ≡ 1 (mod p) if a is a residue, and ≡ −1 if not.
The proof is immediate from cyclicity. Writing a = γ^k, the quantity a^{(p−1)/2} = γ^{k(p−1)/2} equals 1 exactly when p−1 divides k(p−1)/2, that is, exactly when k is even.
This gives a polynomial-time test for quadratic residuosity modulo a prime: one modular exponentiation. The Jacobi symbol computation is faster still, and is what implementations actually use.
a is a QR mod p ⇔ a^{(p−1)/2} ≡ 1 (mod p)03Composite moduli
Modulo a composite the picture changes, and the change is what the quadratic residuosity assumption exploits.
| Modulus | Residues among units | Square roots per residue |
|---|---|---|
| p odd prime | Half | 2 |
| p², p odd | Half | 2 |
| pq, distinct odd primes | One quarter | 4 |
| 2^e, e ≥ 3 | One eighth | 4 |
For n = pq, the Chinese remainder theorem makes a a residue modulo n exactly when it is a residue modulo both factors. That happens for one quarter of units, and each such residue has four square roots — one for each combination of sign choices modulo p and q.
04Frequently asked questions
Why exclude the even prime 2?
Because modulo 2 the squaring map is the identity and every unit is trivially a residue, so the index-2 subgroup argument degenerates. Powers of two are treated separately throughout this subject.
Is 0 a quadratic residue?
By the definition above it is excluded, since residues are defined among the units. Some texts include it as a degenerate case; the convention matters only for edge-case handling in code.
Does a non-residue times a non-residue give a residue?
Modulo a prime, yes — the residues form a subgroup of index 2, so the quotient is the two-element group and the product of two non-residues lands back in the subgroup. Modulo a composite this fails.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 283-285.
This page carries the durable method layer only: definitions, constructions, algorithms, complexity results and selection criteria, authored originally for KEVOS. No text is transcribed or paraphrased from the source, and no numeric tables or benchmark data are reproduced — these are routed to live authoritative sources instead.
Author: Kevin Jogin. Last reviewed 2026-08-07.