Quadratic residues and Legendre symbols

Fix an odd prime p. A nonzero residue a is a quadratic residue if x² is congruent to a for some x, and a nonresidue otherwise. If nonzero x is a root, then −x is a distinct root because p is odd. There cannot be a third: from x² = y² modulo p, primality forces p to divide x − y or x + y. Thus every nonzero square has exactly two roots.

There are p − 1 nonzero inputs to the squaring map, paired into opposite pairs, so there are (p − 1)/2 nonzero square values. Define the Legendre symbol to be one for these residues, negative one for nonresidues, and zero when p divides a. The bottom entry must be an odd prime in this lesson. Substituting a composite modulus into the same notation without a new definition would confuse it with a different object, the Jacobi symbol.

Euler’s criterion says a to the power (p − 1)/2 is congruent to its Legendre symbol. For a nonzero a, write a = gᵏ using a primitive root. The squares are exactly even exponents. Since g to the half group size is the nontrivial square root of one, it equals −1, and the half-period power of a is one or negative one according to the parity of k. This proves the test rather than merely reporting it.

The criterion also implies multiplicativity: the symbol of ab is the product of the symbols of a and b. Equivalently, even and odd generator exponents add like parity. Two nonsquares therefore multiply to a square, while multiplying a square by a nonsquare gives a nonsquare. If either factor is divisible by p, both sides of the multiplicative identity are zero. Include that case instead of silently assuming every residue is a unit.

A Legendre symbol of one guarantees that two roots exist but does not directly name them. For small primes a table or a search may be enough. For primes congruent to three modulo four, a nonzero quadratic residue a has a root given by a to the power (p + 1)/4; squaring that candidate and using Euler’s criterion verifies it. Other primes require a more general root-finding method, not a change to the definition of a residue.

Composite moduli behave differently. A nonzero square can have more than two roots because the factorization of x² − y² need not force one factor to be zero modulo the whole modulus. Chinese remainders can combine root choices from several prime factors. Keep the odd-prime assumption in sight whenever using the half-of-the-units count or the two-root conclusion; these are consequences of field arithmetic, not universal properties of modular squaring.