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
This is written in a shorter form as:
Example
Let a=17. For which primes p is 17 a quadratic residue? We have:
Which numbers are squares modulo 17 (the least quadratic residues modulo 17)? We have:
A more general result is the Law of quadratic reciprocity. Euler's criterion is used in a definition of Euler-Jacobi pseudoprimes.
wikipedia.org dumped 2003-03-17 with terodump