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 k2 ≡ 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:
- 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.