Engineering / Mathematics — Quadratic Residues
The Legendre Symbol
The Legendre symbol as a multiplicative character, its evaluation by Euler's criterion, and the supplementary laws.
Executive summary
The Legendre symbol encodes quadratic residuosity modulo a prime as a value in plus one, minus one or zero. Its multiplicativity turns residuosity questions into arithmetic.
Together with the supplementary laws for minus one and two, it reduces most evaluations to a short computation.
Learning objectives
- Define the Legendre symbol and state its multiplicativity.
- Apply the supplementary laws.
- Evaluate symbols using Euler's criterion.
01Definition and multiplicativity
Legendre symbol
For an odd prime p and integer a:
(a|p) = 0 if p | a; = 1 if a is a non-zero quadratic residue mod p; = −1 otherwise.
Multiplicativity
(ab|p) = (a|p)(b|p) for all integers a, b.
Multiplicativity follows directly from Euler's criterion, since the criterion expresses the symbol as a power and powers multiply. Structurally, the symbol is the homomorphism from Z_p* onto the two-element group whose kernel is the subgroup of residues.
The practical consequence is that a symbol can be evaluated by factoring the numerator and combining the symbols of the parts — though for large arguments the Jacobi symbol algorithm avoids the need to factor at all.
02The supplementary laws
Supplementary laws
(−1|p) = 1 if p ≡ 1 (mod 4), and −1 if p ≡ 3 (mod 4).
(2|p) = 1 if p ≡ ±1 (mod 8), and −1 if p ≡ ±3 (mod 8).
| p mod 8 | (−1|p) | (2|p) | (−2|p) |
|---|---|---|---|
| 1 | +1 | +1 | +1 |
| 3 | −1 | −1 | +1 |
| 5 | +1 | −1 | −1 |
| 7 | −1 | +1 | −1 |
03Evaluation
- Euler's criterion
O(len(p)³)One modular exponentiation; simple but not fastest - Factor and combine
Requires factoring aImpractical for large arguments - Jacobi symbol algorithm
O(len(p)²)Euclid-like; the method actually used
Euler's criterion is the definition made computational, and it is correct but slower than necessary. The Jacobi algorithm proceeds like the Euclidean algorithm, using reciprocity to swap arguments and the supplementary laws to handle factors of two, and never factors anything.
04Frequently asked questions
Why is (0|p) defined as 0?
So that multiplicativity holds without exception. If it were left undefined, every identity would need a side condition excluding multiples of p.
Is the Legendre symbol a character?
Yes — it is the unique non-trivial real character on Z_p*, the quadratic character. This is the entry point to the theory of Dirichlet characters and L-functions.
Can the symbol be computed without knowing p is prime?
The Jacobi symbol generalises it to odd composite moduli and is computable without factoring. It agrees with the Legendre symbol when the modulus is prime but no longer determines residuosity.
Sources and method
Structural reference: Victor Shoup, A Computational Introduction to Number Theory and Algebra, Version 1, Cambridge University Press, 2005 — book pages 285-287.
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.