Quadratic Residues & Legendre Symbol

Which residues are squares mod p, via the Legendre symbol.

The idea

A quadratic residue modulo a prime is a residue that is a perfect square there.

Definition (Quadratic residue).

Let $p$ be an odd prime and let $a$ be coprime to $p$. Then $a$ is a quadratic residue modulo $p$ when $x^{2} \equiv a \pmod{p}$ has a solution, and a quadratic nonresidue when it has none.

Since $x$ and $-x$ are distinct but have the same square, squaring is two-to-one on the nonzero residues, so exactly half of them are squares: $\tfrac{p-1}{2}$ residues and $\tfrac{p-1}{2}$ nonresidues.

The Legendre symbol records the answer as a sign: $\left(\frac{a}{p}\right) = \begin{cases} +1 & a \text{ is a quadratic residue} \\ -1 & a \text{ is a nonresidue.} \end{cases}$ It can be computed without searching for a square root.

Theorem (Euler's criterion).

For an odd prime $p$ and an integer $a$ coprime to $p$, $\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p}.$

One exponentiation settles whether the congruence $x^{2} \equiv a$ is solvable.

Ways to work on it

• Walkthrough. Quadratic residues, the Legendre symbol, and Euler's criterion.
• Practice. Evaluate a Legendre symbol with Euler's criterion.
• Hardest. Evaluate the Legendre symbol of a composite number.

Not sure where to start? Take the ten-question placement test.