The Legendre Symbol
The "sign-like" behaviour of
quadratic residues
cries out for compact notation. The Legendre symbol packages "is this a square
modulo p?" into a single value of +1,
-1 or 0 — and turns residue questions into
clean algebra.
Definition
For an odd prime p and integer a:
\left(\frac{a}{p}\right) = \begin{cases} +1 & \text{if } a \text{ is a quadratic residue mod } p,\\ -1 & \text{if } a \text{ is a non-residue},\\ \ \ 0 & \text{if } p \mid a. \end{cases}
So \left(\tfrac{2}{7}\right) = +1 (we saw
3^2 \equiv 2) while
\left(\tfrac{3}{7}\right) = -1.
It's completely multiplicative
The Legendre symbol turns the residue multiplication rule into ordinary multiplication:
\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right).
The "\text{R}\cdot\text{N} = \text{N}" rules become
(+1)(-1) = -1 and so on. This means you can evaluate any symbol by
factoring the top and handling each prime separately — which, combined with the deep reciprocity
law to come, makes the symbol genuinely computable without ever testing squares.
A first special value
One famous case follows quickly: when is -1 a square modulo
p? The answer depends only on p \bmod 4:
\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2} = \begin{cases} +1 & p \equiv 1 \pmod 4,\\ -1 & p \equiv 3 \pmod 4. \end{cases}
So -1 is a square mod 5 (indeed
2^2 = 4 \equiv -1) but not mod 7. The tool that
proves such formulas is
Euler's criterion.