= Legendre symbol
{c}
{title2=$\left(\frac ap\right)$}
{wiki}
For an <integer> $a$ and an \b[<odd prime>] $p$, the Legendre symbol is the <integer> valued <function>
$$
\left(\frac ap\right)=
\begin{cases}
0,&p\mid a,\\
1,&a\not\equiv0\pmod p\text{ is a square},\\
-1,&a\text{ is a nonsquare}.
\end{cases}
$$
Its value depends only on the <congruence class> of $a$ modulo $p$; the displayed notation is a symbol, not division. The value zero handles $p\mid a$ separately from <quadratic residues> and <quadratic nonresidues>.<Quadratic Residues by Ben Lynn>[Ben Lynn, Quadratic Residues, The Legendre Symbol: three values and dependence on an odd prime]{ref}
For example, $(2/7)=1$, $(3/7)=-1$, $(14/7)=0$, and $(2/11)=-1$. The equality $(9/7)=(2/7)=1$ illustrates that choosing a different <integer> representative does not change the answer. An arbitrary odd composite denominator uses the <Jacobi symbol>, not the <Legendre symbol>. For instance,
$$
\left(\frac2{15}\right)_{\!\mathrm{Jacobi}}
=\left(\frac23\right)\left(\frac25\right)=(-1)(-1)=1,
$$
but two is not a square modulo fifteen: any such <square root> would also give a <square root> modulo three, where the only nonzero square is one. A <Jacobi symbol> of one therefore cannot replace the <Legendre symbol>'s square test.
The <Legendre symbol> also counts <square roots> compactly. For every <congruence class> $a$ in the <prime field> $\mathbb F_p$,
$$
\#\{x\in\mathbb F_p:x^2=a\}=1+\left(\frac ap\right).
$$
The three cases give two, one and zero solutions for a <quadratic residue>, zero and a <quadratic nonresidue>, respectively. This is useful when counting solutions of <modular congruences> involving <polynomials>: a solvability question becomes a sum of <Legendre symbols>, as in the <complete Legendre-symbol sum> and <quadratic Legendre-symbol correlation>.
Back to article page