Euler's criterion

Statement

In terms of quadratic residues and nonresidues

Suppose $p$ is an odd prime number. Consider an integer $a$ that is not zero mod $p$. Then:

• $a^{(p-1)/2}$ is congruent to either 1 or -1 mod $p$.
• $a^{(p-1)/2}$ is congruent to 1 mod $p$ if and only if $a$ is a quadratic residue mod $p$.
• $a^{(p-1)/2}$ is congruent to -1 mod $p$ if and only if $a$ is a quadratic nonresidue mod $p$.

In terms of Legendre symbol

Suppose $p$ is an odd prime number. Consider an integer $a$ that is not zero mod $p$. Then:

$a^{(p-1)/2}\equiv (\frac{a}{p})(\mathrm{mod}p)$

where the expression on the right side is the Legendre symbol, defined to be $+1$ for a quadratic residue and $-1$ for a quadratic nonresidue. Note that the Legendre symbol is the restriction to primes of the Jacobi symbol.

Related facts

Applications

• Congruence condition for minus one to be a quadratic residue
• Congruence condition for two to be a quadratic residue
• Quadratic reciprocity

Primality tests

• Euler primality test, which is not conclusive and can be fooled by Euler pseudoprimes to the given base
• Euler-Jacobi primality test, which is not conclusive and can be fooled by Euler-Jacobi pseudoprimes to the given base