The Legendre Symbol

The Legendre symbol is the backbone of the Law of Quadratic Reciprocity, which in turn is used to efficiently decide the solvability of $x^2 \equiv a \pmod p$ for large primes without brute-force search, a task central to computational number theory. In cryptography, fast evaluation of Legendre and Jacobi symbols underlies primality tests (such as the Solovay–Strassen test) and is used in constructing quadratic residue codes and certain pseudorandom bit generators, where the sequence of $\pm1$ values behaves like a pseudorandom binary sequence with strong statistical independence properties. In the theory of quadratic forms, the Legendre symbol determines exactly which primes are represented by forms like $x^2 + ny^2$, connecting directly to Quadratic Residues and Nonresidues and class field theory. In algebraic number theory more broadly, the symbol is the prototype for Artin symbols and Frobenius elements, generalizing the same "is this a square (or higher power) modulo this prime" idea to arbitrary number fields and Galois extensions.

Ask the tutor: How does Euler's Criterion give a fast formula for computing the Legendre symbol without factoring or listing residues?

Think of the nonzero residues $1, 2, \dots, p-1$ mod $p$ as the elements of a finite cyclic group $G = (\mathbb{Z}/p\mathbb{Z})^\times$ of order $p-1$ under multiplication. Squaring is a group homomorphism $G \to G$, $x \mapsto x^2$, and its image is precisely the set of quadratic residues. Because $p$ is odd, $p - 1$ is even, and it turns out (this is the content of the theorem below) that squaring is exactly 2-to-1: each square has precisely two square roots, $x$ and $-x$, and these are distinct because $x \equiv -x \pmod p$ would force $2x \equiv 0$, impossible for $x \not\equiv 0$ when $p$ is odd. So the squares form a subgroup of index exactly $2$. The Legendre symbol is nothing more than the indicator of membership in that subgroup, encoded as $\pm 1$ instead of "yes/no". This is exactly the right encoding because the quotient group $G / (G^2)$ has order $2$, and the unique nontrivial homomorphism from a group of order $2$ into $\{\pm 1\} \subset \mathbb{C}^\times$ is an isomorphism — so $(a/p)$ literally is (the pullback along $G \to G/G^2$ of) this isomorphism. Multiplicativity of the symbol is then just the statement that a composite of group homomorphisms is a homomorphism: nothing deeper is happening algebraically, though the number-theoretic consequences are enormous. Picture $G$ as $p-1$ points arranged around a circle (a cyclic group), colored red if the point is a square and blue if not; the picture below does this for $p = 13$, where $G$ has order $12$ and there are $6$ residues of each color, alternating in a pattern governed by the discrete-log exponent parity, not by naive adjacency.

A second way to see the same idea: draw the graph of $a \mapsto (a/p)$ for $p = 11$ as a bar chart over $a = 1, \dots, 10$. The pattern of $\pm 1$'s looks irregular, yet multiplying any two heights $(a/11)\cdot(b/11)$ always equals the height at $ab \bmod 11$ — the multiplicativity theorem below is exactly this hidden consistency, verified structurally rather than by checking all $100$ products by hand.

Example 1: computing $(45/17)$ by direct factorization and multiplicativity. Take $p = 17$ (an odd prime) and $a = 45$. First reduce: $45 = 2\cdot 17 + 11$, so $45 \equiv 11 \pmod{17}$, and since the symbol depends only on $a \bmod p$,

Rather than testing all square roots directly, use multiplicativity with the factorization $45 = 9 \cdot 5$:

Since $9 = 3^2$, the corollary above gives $(9/17) = 1$. For $(5/17)$, we search for $x$ with $x^2 \equiv 5 \pmod{17}$ by squaring residues: $1^2=1,\ 2^2=4,\ 3^2=9,\ 4^2=16,\ 5^2=25\equiv8,\ 6^2=36\equiv2,\ 7^2=49\equiv15,\ 8^2=64\equiv13$. The full set of quadratic residues mod $17$ (using that $x^2 \equiv (17-x)^2$, so it suffices to square $1,\dots,8$) is $\{1,4,9,16,8,2,15,13\}$. Since $5$ is not in this set, $5$ is a nonresidue, so $(5/17) = -1$. Hence

so $45$ is a quadratic nonresidue mod $17$. As a check: we can verify directly that $11$ (to which $45$ is congruent) is also absent from $\{1,2,4,8,9,13,15,16\}$, consistent with $(11/17) = (45/17) = -1$.

Example 2: a product of three factors, including a factor divisible by $p$, showing the $0$ case interacting with multiplicativity. Take $p = 13$ and consider $a = 6$, $b = 26$, $c = 7$, so $abc = 6 \cdot 26 \cdot 7 = 1092$. Note $26 = 2\cdot 13$, so $13 \mid 26$, hence $(26/13) = 0$ by definition. By the product formula,

This matches direct computation: $1092 = 84\cdot 13 + 0$, so indeed $13 \mid 1092$ and $(1092/13) = 0$ by definition, confirming the formula without needing to know $(6/13)$ or $(7/13)$ individually. For completeness, since $6\equiv 6$ and $6$ is not among the quadratic residues mod $13$ found in the earlier figure ($\{1,3,4,9,10,12\}$), we get $(6/13) = -1$; and $7 \notin \{1,3,4,9,10,12\}$ either, so $(7/13) = -1$ too — giving $(6/13)(7/13) = (-1)(-1) = 1 = (42/13)$, a separate check that $42 \equiv 3 \pmod{13}$ is indeed a residue (it is, since $3 = 4^2 \bmod 13$: $16 \equiv 3$). This illustrates how a single zero factor collapses the whole product to $0$ regardless of the other factors' signs.