Euler's criterion

Statement

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$ .

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}) (\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.