Euler's criterion

In mathematics, Euler's criterion is used in determining in number theory whether a given integer is a quadratic residue modulo or a prime.

If p is an odd prime and a is an integer coprime to p then Euler's criterion states: if a is quadratic residue modulo p (i.e. there exists a number k such that k² ≡ a (mod p)), then

a^(p-1)/2 ≡ 1 (mod p)

and if a is not a quadratic residue modulo p then

a^(p-1)/2 ≡ -1 (mod p).

This is written in a shorter form as:

a^(p-1)/2 ≡ (a/p) (mod p),

where (a/p) is the Legendre symbol.

Example

Let a=17. For which primes p is 17 a quadratic residue? We have:

(17/p) = +1 for p = {2, 13, 19, 47, 53, 67, 83, 89, ...}

(17/p) = -1 for p = {3, 31, 37, 71, ...}

Which numbers are squares modulo 17 (the least quadratic residues modulo 17)? We have:

1²=1, 2²=4, 3²=9, 4²=16, 5²=25=25-17=8 (mod 17),

6²=36=36-2*17=2 (mod 17), 7²=49=49-2*17=15 (mod 17),

8²=64=64-3*17=13 (mod 17).

So the set of the least quadratic residues modulo 17 is {1,2,4,8,9,13,15,16}.

A more general result is the Law of quadratic reciprocity. Euler's criterion is used in a definition of Euler-Jacobi pseudoprimes.