Euler's criterion

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 an integer coprime to p. Then

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

The criterion first appeared in a 1748 paper by 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. The fact that there are $(p - 1)/2$ quadratic residues and the same number of nonresidues (mod $p$ ) is proved in the article quadratic residue.

If $a$ is 0 mod $p$ , then

Otherwise, Fermat's little theorem says that

which can be written as

Since the integers mod $p$ form a field, one or the other of these factors must be congruent to zero.

Now if $a$ is a quadratic residue, $a \equiv x 2$ ,

So every quadratic residue (mod $p$ ) makes the first factor zero.

Lagrange's theorem says that there can be no more than $(p - 1)/2$ values of $a$ that make the first factor zero. But it is known that there are $(p - 1)/2$ distinct quadratic residues (mod $p$ ) (besides 0). Therefore they are precisely the residue classes that make the first factor zero. The other $(p - 1)/2$ residue classes, the nonresidues, must make the second factor zero, or they would not satisfy Fermat's little theorem. This is Euler's criterion.

...
Wikipedia