Euler's Criterion

In number theory, Euler's criterion tells you if a number is a quadratic residue modulo an odd prime or not.

It was discovered by Leonhard Euler in \(1748\).

Let \(p\) be an odd prime and \(a\) is a positive integer not divisible by \(p\). Euler's criterion tells us that

\[\left(\frac{a}{p}\right) \equiv a^{\frac{p-1}{2}} \pmod p,\]

where \(\left(\frac{a}{p}\right)\) is the Legendre symbol of \(a\) with respect to \(p\).

The proof we're about to go through is a combination of Fermat's little theorem and the fundamental theorem of algebra.

First, we recall a well-known fact: exactly half of the linear residues mod \(p\) except zero are quadratic residues mod \(p\). Now, by Fermat's little theorem, we have

\[a^{p-1}\equiv 1~\implies ~ a^{\frac{p-1}{2}}\equiv \pm 1\pmod p.\]

If \(a\) is a quadratic residue mod \(p,\) then \(a\equiv x^2\pmod p\) for some \(x\). Then we must have \(a^{\frac{p-1}{2}}\equiv x^{p-1}\equiv 1=\left(\frac a p\right)\pmod p\) from Fermat's little theorem.

So it suffices to prove that for quadratic nonresidues \(a\) we have \(a^{\frac{p-1}{2}}\equiv -1\pmod p.\) Consider the equation \(x^{\frac{p-1}{2}}=1\) in \(\mathbb Z_p.\) It has at most \(\frac{p-1}{2}\) roots. But we've already shown that all the quadratic residues \(\big(\)there's \(\frac{p-1}{2}\) of them\(\big)\) mod \(p\) are roots of this equation. So there's no other root, meaning for any quadratic nonresidue \(a\) we can't have \(a^{\frac{p-1}{2}}\equiv 1\pmod p\). But \(a^{\frac{p-1}{2}}\equiv \pm 1\pmod p\), so it must be the case that for quadratic nonresidues \(a\) we have \(a^{\frac{p-1}{2}}\equiv -1=\left(\frac a p\right)\pmod p\).

Hence we always have \(a^{\frac{p-1}{2}}\equiv\left(\frac a p\right)\pmod p.\)

1. Legendre Symbol
2. Quadratic Residues
3. Fermat's Little Theorem