# Euler's criterion

## Statement

### In terms of quadratic residues and nonresidues

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

•  is congruent to either 1 or -1 mod .
•  is congruent to 1 mod  if and only if  is a quadratic residue mod .
•  is congruent to -1 mod  if and only if  is a quadratic nonresidue mod .

### In terms of Legendre symbol

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



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