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