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
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 k2 ≡ a (mod p)) if and only if
- .
As a corollary of the theorem one gets:
If a is not a square (also called a quadratic non-residue) modulo p then
Euler's criterion can be concisely reformulated using the Legendre symbol:
[edit] 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 k2 ≡ a (mod p).
Then the following rule is used: if a ≡ b (mod n) then am ≡ bm(mod n). One can then write: (k2)(p-1)/2 ≡ a (p-1)/2(mod p). Reducing the left side gives: kp − 1 ≡ a (p-1)/2(mod p) (*).
Because p is prime one can by Fermat's little theorem write: kp − 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 k2 = αi ≡ a (mod p).
The biimplication is now established, thereby proving the theorem.
[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 = 171 ≡ 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 = 176 ≡ 1 (mod 13), therefore 17 is a quadratic residue modulo 13. As confirmation, note that 17 ≡ 4 (mod 13), and 22 = 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:
- 12 = 1
- 22 = 4
- 32 = 9
- 42 = 16
- 52 = 25 ≡ 8 (mod 17)
- 62 = 36 ≡ 2 (mod 17)
- 72 = 49 ≡ 15 (mod 17)
- 82 = 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 92 = (−8)2 = 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 = 28 ≡ 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 = 38 = 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.