Euler's criterion

From Wikipedia, the free encyclopedia

In mathematics, Euler's criterion is used in determining in number theory whether a given integer is a quadratic residue modulo a prime.

[edit] Definition

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 − 1)/2} ≡ 1 (mod p)

and if a is not a quadratic residue modulo p then

a^{(p − 1)/2} ≡ −1 (mod p).

Euler's criterion can be concisely reformulated using the Legendre symbol:

[edit] Proof of Euler's criterion

In one case, we assume a is a quadratic residue modulo p. We find k such that k² ≡ a (mod p). Then a^{(p − 1)/2} = k^{p − 1} ≡ 1 (mod p) by Fermat's little theorem.

In the other case, we assume a^{(p − 1)/2} ≡ 1 (mod p). Then let α be a primitive element modulo p, that is to say a = αⁱ. So, α^{i(p − 1)/2} ≡ 1 (mod p). By Fermat's little theorem, (p − 1) divides i(p − 1)/2, so i must be even. Let k ≡ α^i/2 (mod p). We finally have k² = αⁱ ≡ a (mod p).

[edit] 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 (mod 3) ≡ -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:

1² = 1

2² = 4

3² = 9

4² = 16

5² = 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.