Main Page | See live article | Alphabetical index

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 k2a (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:
12=1, 22=4, 32=9, 42=16, 52=25=25-17=8 (mod 17),
62=36=36-2*17=2 (mod 17), 72=49=49-2*17=15 (mod 17),
82=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.