Legendre symbol

Definition

Let $p$ be an odd prime number and let $a$ be an integer. The Legendre symbol $\left(\frac{a}{p}\right)$ is the number $$\left(\frac{a}{p}\right) = \begin{cases} 0 & \text{if } p \mid a, \\ 1 & \text{if } p \nmid a \text{ and } a \text{ is a quadratic residue modulo } p, \\ -1 & \text{if } a \text{ is a quadratic nonresidue modulo } p. \end{cases}$$ Here quadratic residue has the meaning of the definition of a quadratic residue.

Remarks

The value depends only on the class of $a$ modulo $p$. For example, $\left(\frac{2}{7}\right) = 1$ because $3^2 \equiv 2 \pmod 7$, and $\left(\frac{3}{7}\right) = -1$. Euler's criterion gives the value as $a^{(p-1)/2}$ modulo $p$. The law of quadratic reciprocity helps to compute the symbol quickly.

Explanations

L1 human

The Legendre symbol is a short way to say whether $a$ is a square modulo $p$. The value $1$ means yes, the value $-1$ means no, and the value $0$ means that $a$ is $0$ modulo $p$.