In number theory, Euler's criterion is a formula for determining whether an integer is a quadratic residue modulo a prime. Precisely,

Let p be an odd prime and a be an integer coprime to p. Then

Euler's criterion can be concisely reformulated using the Legendre symbol:

The criterion dates from a 1748 paper by Leonhard Euler.

The proof uses the fact that the residue classes modulo a prime number are a field. See the article prime field for more details.

Because the modulus is prime, Lagrange's theorem applies: a polynomial of degree k can only have at most k roots. In particular, x² ≡ a (mod p) has at most 2 solutions for each a. This immediately implies that besides 0 there are at least ⁠p − 1/2⁠ distinct quadratic residues modulo p: each of the p − 1 possible values of x can only be accompanied by one other to give the same residue.

In fact, ${\displaystyle (p-x)^{2}\equiv x^{2}{\pmod {p}}.}$This is because ${\displaystyle (p-x)^{2}\equiv p^{2}-{2}{x}{p}+x^{2}\equiv x^{2}{\pmod {p}}.}$ So, the ${\displaystyle {\tfrac {p-1}{2}}}$ distinct quadratic residues are: ${\displaystyle 1^{2},2^{2},...,({\tfrac {p-1}{2}})^{2}{\pmod {p}}.}$

As a is coprime to p, Fermat's little theorem says that