Legendre Symbol

Why the Legendre symbol matters

• Primality testing. Solovay-Strassen and earlier Pocklington-style tests use (a|n) and Euler's criterion: if a^((n-1)/2) ≢ (a|n) (mod n), n is composite. Each round costs O(log³ n) and detects compositeness with probability ≥ 1/2.
• Elliptic curve cryptography. Schoof's point-counting algorithm and naive ECC implementations call (a|p) for thousands of values during prime curve selection. The symbol controls whether y² = f(x) has a solution over F_p for given x.
• Modular square roots — Tonelli-Shanks. Before solving x² ≡ a (mod p), the algorithm tests (a|p): if -1, no solution exists. If +1, a randomised search for a quadratic non-residue and the Tonelli-Shanks loop produce x in expected O(log² p · log log p) time.
• Cipolla's algorithm. An alternative deterministic-looking modular square root method also begins with (a|p) and constructs the root inside the field F_p[t]/(t² − (b² − a)) for an explicit non-residue b² − a.
• Distribution of QRs and Polya-Vinogradov. Sums Σₐ (a|p) cancel almost completely — bounded by p^(1/2) log p — and this controls character sums, equidistribution of squares mod p, and many analytic-number-theory inequalities.
• Continued fractions and Pell. Whether x² − D y² = -1 is solvable hinges on (D|p) for primes p in particular forms — and the Legendre symbol is the deciding gadget.
• Class numbers and Dirichlet L-functions. The L-function L(s, χ) for the Kronecker character χ_D = (D|·) has its values at s = 1 directly controlling class numbers via Dirichlet's class number formula. The symbol is the lifeblood of these L-functions.

Common misconceptions

• "(a|p) only makes sense for primes." The bottom must be an odd prime to define (a|p) as a quadratic-residue indicator. The Jacobi symbol extends the bottom to any positive odd integer by multiplicativity, and the Kronecker symbol extends further to all integers — including negatives and 2 — at the cost of careful sign conventions.
• "(a|n) = +1 implies a is a quadratic residue mod n." True for prime n. False for composite n with the Jacobi symbol. Example: (2|15) = (2|3)(2|5) = (-1)(-1) = +1, but 2 is not a square mod 15 (squares mod 15 are 0,1,4,6,9,10). The Jacobi symbol is a useful proxy, not an honest residue indicator on composites.
• "Compute (a|p) by squaring lots of integers and checking." Naive: try x = 1, 2, …, (p-1)/2 and see if x² ≡ a (mod p). Cost: O(p) — exponential in input size. Reciprocity-based computation is O(log² p), polynomial in input size — and that polynomial gap is what makes cryptographic-scale primality testing tractable.
• "Euler's criterion is faster than reciprocity." Euler's criterion (a|p) ≡ a^((p-1)/2) (mod p) needs O(log p) modular multiplications, each costing O(log² p) bit operations: total O(log³ p). Reciprocity-based computation is O(log² p) bit operations. Reciprocity is asymptotically faster — the standard library implementations all use it.
• "The symbol is multiplicative in the bottom." No — the Legendre symbol is multiplicative in the top: (ab|p) = (a|p)(b|p). It is NOT multiplicative in the bottom; that role is played by the Jacobi symbol's definition (a|mn) = (a|m)(a|n).
• "(a|p) = 0 is rare." (a|p) = 0 exactly when p divides a — common in worked examples and crucial to remember. It is not "negligible"; it is a distinct case that algorithms must handle separately.

A worked computation

Compute (5|31) by reciprocity. Both 5 ≡ 1 (mod 4) and 31 ≡ 3 (mod 4), so reciprocity gives (5|31) = +(31|5) = (31 mod 5 | 5) = (1|5) = +1. So 5 is a quadratic residue mod 31 — and indeed 6² = 36 ≡ 5 (mod 31). The whole computation costs three modular reductions, no exponentiations. Compare Euler's criterion: 5^15 mod 31 by fast exponentiation, requiring four squarings and a couple of multiplications, all mod 31 — also fast for this size, but the reciprocity approach scales better as primes grow into the cryptographic range.

Legendre and Gauss

Legendre introduced the symbol (a|p) in his 1785 memoir on indeterminate analysis, and used it to state quadratic reciprocity in essentially modern form. His own proof, however, had a gap — it assumed the existence of certain primes in arithmetic progressions, a claim only proved by Dirichlet decades later. Gauss, then 19, filled the gap in 1796, and the symbol acquired its name from Legendre's clean notation. The Jacobi symbol came in 1837, the Kronecker symbol in 1885, the Hilbert symbol in 1897 — each a successive generalisation. Today the Legendre symbol survives unchanged in introductory number theory courses, computer-algebra systems, and cryptographic primality testers.