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 .
Contents
Definition
Let be an odd prime and is a positive integer not divisible by . Euler's criterion tells us that
where is the Legendre symbol of with respect to .
Proof
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 except zero are quadratic residues mod . Now, by Fermat's little theorem, we have
If is a quadratic residue mod then for some . Then we must have from Fermat's little theorem.
So it suffices to prove that for quadratic nonresidues we have Consider the equation in It has at most roots. But we've already shown that all the quadratic residues there's of them mod are roots of this equation. So there's no other root, meaning for any quadratic nonresidue we can't have . But , so it must be the case that for quadratic nonresidues we have .
Hence we always have