The Legendre Symbol — Mathematics Knowledge System

Overview

The Legendre symbol (a/p), introduced by Adrien-Marie Legendre in 1798, is compact notation for whether an integer a is a quadratic residue modulo an odd prime p: it equals +1 if a is a nonzero square mod p, −1 if it is a non-residue, and 0 if p divides a. Beyond bookkeeping, the symbol is multiplicative in its top argument — (ab/p) = (a/p)(b/p) — which turns residue questions about products into simple sign arithmetic, and Euler's criterion gives a direct computational formula via modular exponentiation. Combined with Gauss's law of quadratic reciprocity, the Legendre symbol lets you decide, for arbitrarily large primes, whether a number is a square mod p without ever testing individual residues — a cornerstone technique feeding into primality tests (Solovay–Strassen) and the later, more general Jacobi and Kronecker symbols.

Intuition

Euler's criterion works because the nonzero residues mod p form a cyclic group of order p−1. Squaring is a group homomorphism whose image (the quadratic residues) has index 2, so every element raised to the half-order (p−1)/2 lands on one of the two square roots of 1 — namely +1 if it was already a square, and −1 otherwise (since a non-square, squared, is a square, and (a^{(p-1)/2})^2 = a^{p-1} ≡ 1 by Fermat forces a^{(p-1)/2} ≡ ±1). Multiplicativity then follows immediately from the exponentiation formula: (ab)^{(p-1)/2} = a^{(p-1)/2} b^{(p-1)/2}, so signs multiply exactly like the symbols do.

Formal Definition

Definition

For an odd prime p and integer a, the Legendre symbol is:

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

Definition

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

Euler's criterion

\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)

Multiplicativity (completely multiplicative in a)

Worked Examples

Euler's criterion: (2/7) ≡ 2^{(7-1)/2} = 2^3 (mod 7).
$2^{3} = 8$
8 = 1·7 + 1, so 2^3 ≡ 1 (mod 7).
$8 \equiv 1 \pmod{7}$

Answer: (2/7) = 1, so 2 is a quadratic residue mod 7 (indeed 3² = 9 ≡ 2 mod 7).

Practice Problems

Difficulty 5/10

Compute 27 mod 7 to determine the Legendre symbol (3/7) via Euler's criterion (3^3 mod 7).

Difficulty 6/10

Given (2/7) = 1 and (3/7) = −1, use multiplicativity to find (6/7) without further exponentiation.

Difficulty 6/10

Compute the Legendre symbol (5/11) using Euler's criterion (compute 5^5 mod 11).

Quiz

Summary

The Legendre symbol (a/p) ∈ {+1, −1, 0} encodes whether a is a quadratic residue mod an odd prime p.
Euler's criterion computes it directly: (a/p) ≡ a^{(p-1)/2} (mod p).
It is completely multiplicative — (ab/p) = (a/p)(b/p) — turning residue questions about products into sign arithmetic, and it feeds directly into quadratic reciprocity.

References

WebsiteWikipedia — Legendre symbol