Euler's criterion

Proof

The proof uses the fact that the residue classes modulo a prime number are a field. See the article prime field for more details. The fact that there are (p − 1)/2 quadratic residues and the same number of nonresidues (mod p) is proved in the article quadratic residue.

If a is 0 mod p, then

a p − 1 ≡ 0 ( mod p ) .

Otherwise, Fermat's little theorem says that

a p − 1 ≡ 1 ( mod p )

which can be written as

( a p − 1 2 − 1 ) ( a p − 1 2 + 1 ) ≡ 0 ( mod p ) .

Since the integers mod p form a field, one or the other of these factors must be congruent to zero.

Now if a is a quadratic residue, a ≡ x²,

a p − 1 2 ≡ ( x 2 ) p − 1 2 ≡ x p − 1 ≡ 1 ( mod p ) .

So every quadratic residue (mod p) makes the first factor zero.

Lagrange's theorem says that there can be no more than (p - 1)/2 values of a that make the first factor zero. But it is known that there are (p - 1)/2 distinct quadratic residues (mod p) (besides 0). Therefore they are precisely the residue classes that make the first factor zero. The other (p - 1)/2 residue classes, the nonresidues, must make the second factor zero, or they would not satisfy Fermat's little theorem. This is Euler's criterion.

Examples

Example 1: Finding primes for which a is a residue

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

We can test prime p's manually given the formula above.

In one case, testing p = 3, we have 17^{(3 − 1)/2} = 17¹ ≡ 2 ≡ −1 (mod 3), therefore 17 is not a quadratic residue modulo 3.

In another case, testing p = 13, we have 17^{(13 − 1)/2} = 17⁶ ≡ 1 (mod 13), therefore 17 is a quadratic residue modulo 13. As confirmation, note that 17 ≡ 4 (mod 13), and 2² = 4.

We can do these calculations faster by using various modular arithmetic and Legendre symbol properties.

If we keep calculating the values, we find:

(17/p) = +1 for p = {13, 19, ...} (17 is a quadratic residue modulo these values)(17/p) = −1 for p = {3, 5, 7, 11, 23, ...} (17 is not a quadratic residue modulo these values).

Example 2: Finding residues given a prime modulus p

Which numbers are squares modulo 17 (quadratic residues modulo 17)?

We can manually calculate it as:

1² = 12² = 43² = 94² = 165² = 25 ≡ 8 (mod 17)6² = 36 ≡ 2 (mod 17)7² = 49 ≡ 15 (mod 17)8² = 64 ≡ 13 (mod 17).

So the set of the quadratic residues modulo 17 is {1,2,4,8,9,13,15,16}. Note that we did not need to calculate squares for the values 9 through 16, as they are all negatives of the previously squared values (e.g. 9 ≡ −8 (mod 17), so 9² ≡ (−8)² = 64 ≡ 13 (mod 17)).

We can find quadratic residues or verify them using the above formula. To test if 2 is a quadratic residue modulo 17, we calculate 2^{(17 − 1)/2} = 2⁸ ≡ 1 (mod 17), so it is a quadratic residue. To test if 3 is a quadratic residue modulo 17, we calculate 3^{(17 − 1)/2} = 3⁸ ≡ 16 ≡ −1 (mod 17), so it is not a quadratic residue.

Euler's criterion is related to the Law of quadratic reciprocity and is used in a definition of Euler–Jacobi pseudoprimes.