Euler's criterion

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

Definition

Euler's criterion states:

Let "p" be an odd prime and "a" an integer coprime to "p". Then "a" is a quadratic residue modulo "p" (i.e. there exists a number "k" such that "k"² ≡ "a" (mod "p")) if and only if:$a^\{(p\; -\; 1)\; /\; 2\}\; equiv\; 1\; pmod\; p$.

As a corollary of the theorem one gets:

If "a" is not a square (also called a quadratic non-residue) modulo "p" then:$a^\{(p\; -\; 1)/2\}\; equiv\; -1\; pmod\; p$

Euler's criterion can be concisely reformulated using the Legendre symbol::$left(frac\{a\}\{p\}\; ight)\; equiv\; a^\{(p-1)/2\}\; pmod\; p$

Proof of Euler's criterion

The theorem consists of two statements connected with a biimplication:

A: "a" is a quadratic residue modulo "p"

B: "a"^{("p" − 1)/2} ≡ 1 (mod p)

To establish the biimplication one needs to show (1) that A implies B , and (2) that B implies A:

(1) assume "a" is a quadratic residue modulo "p". We find "k" such that "k"² ≡ "a" (mod "p").

Then the following rule is used: if "a" ≡ "b" (mod "n") then "a"^"m" ≡ "b"^"m"(mod "n"). One can then write: ("k"²)^(p-1)/2 ≡ a ^(p-1)/2(mod "p"). Reducing the left side gives: "k"^{"p" − 1} ≡ a ^(p-1)/2(mod "p") (*).

Because p is prime one can by Fermat's little theorem write: "k"^{"p" − 1} ≡ 1 (mod "p") (**).

(*) and (**) taken together then gives:"a"^{("p" − 1)/2} ≡ 1 (mod p)

(2) assume "a"^{("p" − 1)/2} ≡ 1 (mod "p"). Then let α be a primitive element modulo "p", that is to say "a" can be written as α^"i" for some "i". So in particular, α^{"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"² = α^"i" ≡ "a" (mod "p").

The biimplication is now established, thereby proving the theorem.

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.