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\).
Contents
Definition
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\).
Proof
The proof we're about to go through is a combination of Fermat's Little Theorem and 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(\dfrac 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 \(\dfrac{p-1}{2}\) roots. But we've already shown that all the quadratic residues (there's \(\dfrac{p-1}{2}\) of them) 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(\dfrac a p\right)\pmod p\).
Hence we always have \(a^{\frac{p-1}{2}}\equiv\left(\dfrac a p\right)\pmod p.\)