Euler's criterion

Euler's criterion in number theory is used in determining whether an integer is a quadratic residue modulo 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-/sup> ≡ 1 (mod p}

and if a is not a quadratic residue modulo p then
a^{(p-/sup> ≡ -1 (mod p}
This is written in a shorter form as:
a^{(p-/sup> ≡ (ap) (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.

Encyclopedia Home Page

Euler's criterion