Quadratic Residues & Legendre Symbol: Theory Guide

A quadratic residue modulo p is a number that can appear as the remainder of a perfect square. For an odd prime p, we ask: for which values of a does the congruence x^2 ≡ a (mod p) have a solution? Those values of a are the quadratic residues of p; the rest are quadratic non-residues. For example, modulo 7 the squares are 1^2 = 1, 2^2 = 4, 3^2 = 2, 4^2 = 2, 5^2 = 4, 6^2 = 1, so the residues are 1, 2 and 4, while 3, 5 and 6 are non-residues.

Quadratic residues matter because they control which square roots exist in modular arithmetic, and square roots mod p are exactly what many cryptographic protocols need. They decide whether a number is a square in finite fields, they classify which primes divide numbers of special forms, and they sit at the heart of primality tests. The Legendre symbol, which encodes residue status as +1, −1 or 0, turns these questions into calculations you can do by hand.

Key Concepts

• Quadratic residue: a (not divisible by p) is a residue mod p if x^2 ≡ a (mod p) has an integer solution x.
• Legendre symbol (a/p): equals 1 if a is a quadratic residue mod p, −1 if a is a non-residue, and 0 if p divides a.
• Counting residues: exactly (p − 1)/2 of the numbers 1 … p − 1 are residues, and (p − 1)/2 are non-residues.
• Euler's criterion: a^(p−1)/2 ≡ (a/p) (mod p) — raising to the power (p − 1)/2 reveals the residue status.
• Multiplicativity: the Legendre symbol is multiplicative: (ab/p) = (a/p)·(b/p), so a product is a residue exactly when both factors are residues or both are non-residues.
• Quadratic reciprocity: for distinct odd primes p and q, (p/q)·(q/p) = (−1)^((p−1)/2)·((q−1)/2), linking residues across primes.

Formulas

• Legendre definition: (a/p) = 1 if x^2 ≡ a (mod p) is solvable with p ∤ a; −1 if unsolvable; 0 if p | a.
• Euler's criterion: a^(p−1)/2 ≡ (a/p) (mod p) for any integer a and odd prime p.
• Special values: (−1/p) = (−1)^(p−1)/2, i.e. 1 when p ≡ 1 (mod 4) and −1 when p ≡ 3 (mod 4); (2/p) = (−1)^(p^2−1)/8, i.e. 1 when p ≡ ±1 (mod 8) and −1 when p ≡ ±3 (mod 8).
• Quadratic reciprocity: (p/q) = (q/p) unless both p ≡ q ≡ 3 (mod 4), in which case (p/q) = −(q/p).
• Two roots: if x^2 ≡ a (mod p) is solvable with p ∤ a, its solutions are x ≡ r and x ≡ −r for a single r.

Worked Example

Decide whether x^2 ≡ 5 (mod 11) is solvable and find all solutions. Step 1: list the residues mod 11 by squaring 1 … 5: 1^2 = 1, 2^2 = 4, 3^2 = 9, 4^2 = 16 ≡ 5, 5^2 = 25 ≡ 3. The residues are {1, 3, 4, 5, 9}, and 5 is among them, so (5/11) = 1 and solutions exist. Step 2: from the list, 4^2 ≡ 5 (mod 11), so x ≡ 4 works; the second solution is x ≡ −4 ≡ 7. Verification: 7^2 = 49, and 49 − 44 = 5 ✓. Step 3: cross-check with Euler's criterion: 5^5 mod 11. Compute 5^2 = 25 ≡ 3, 5^4 ≡ 3^2 = 9, so 5^5 ≡ 9·5 = 45 ≡ 45 − 44 = 1 ✓, confirming (5/11) = 1. Contrast with x^2 ≡ 6 (mod 11): 6 is not in the residue list, and indeed 6^5 ≡ (−5)^5 ≡ −1 (mod 11), so (6/11) = −1 and no solution exists.

Common Misconceptions

• "Half the numbers are residues, so a random a has a 50-50 chance — checking is pointless." The 50-50 split is exactly why we need tests like Euler's criterion or reciprocity: you cannot guess, you must compute.
• "The Legendre symbol works for any modulus." It is defined only for odd primes. For composite moduli the Jacobi symbol generalises it, but a Jacobi value of 1 does not guarantee a solution.
• "(a/p) = 1 means the square root is unique." It means two solutions exist (r and −r) when p does not divide a. Forgetting the second root loses half the answers.

Real-World Applications

• Cryptography: the Goldwasser–Micali encryption scheme encrypts a bit as a quadratic residue or non-residue; the quadratic residuosity problem is its security foundation.
• Primality testing: the Solovay–Strassen test uses Euler's criterion to check whether a number behaves like a prime.
• Square roots in finite fields: algorithms like Tonelli–Shanks first test the Legendre symbol, then extract the root — used in elliptic-curve cryptography.
• Sums of squares: residue theory proves which primes can be written as a sum of two squares (exactly those with p = 2 or p ≡ 1 (mod 4)).

Quadratic residues are the squares that survive modulo a prime, and the Legendre symbol packs their whole theory into the values +1, −1 and 0. Euler's criterion turns residue questions into a single exponentiation, and quadratic reciprocity links residues across different primes. The example shows the full workflow: list residues or apply Euler, read off the solutions as ±r, and remember that a value of −1 means no square root exists at all.