Euler's Criterion
How do you decide whether a number is a square modulo p without
squaring everything? Euler found a single exponentiation that settles it — a formula computing the
Legendre symbol
directly, and the theoretical backbone of the whole theory.
The criterion
For an odd prime p and p \nmid a,
\left(\frac{a}{p}\right) \equiv a^{(p-1)/2} \pmod{p}.
That is, a^{(p-1)/2} \equiv +1 if a is a
quadratic residue, and \equiv -1 if it is not.
Test it mod 7 with (p-1)/2 = 3:
2^{3} = 8 \equiv 1 (so 2 is a residue) but
3^{3} = 27 \equiv 6 \equiv -1 (so 3 is a
non-residue) — matching what we found by hand.
Why it works
By Fermat,
a^{p-1} \equiv 1, so
\big(a^{(p-1)/2}\big)^2 \equiv 1 — meaning
a^{(p-1)/2} is a square root of 1, hence
\pm 1. If a = x^2 is a residue, then
a^{(p-1)/2} = x^{p-1} \equiv 1. The non-residues are exactly the ones
left giving -1 — there are (p-1)/2 of each, as
a primitive root
argument confirms.
What it unlocks
Euler's criterion makes the Legendre symbol an honest computation and immediately proves the
\left(\tfrac{-1}{p}\right) rule (put a = -1).
Pushed harder, it yields the supplementary law for
\left(\tfrac{2}{p}\right) and underpins the crown jewel,
quadratic reciprocity.
It is also how cryptographic libraries test for square roots when picking curve parameters.