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^{2} ≡ 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 nonresidue) modulo p then
Euler's criterion can be concisely reformulated using the Legendre symbol:
Proof of Euler's criterion
Every number either is or isn't a quadratic residue (mod p). Also, since the squareroots of 1 are 1 and −1 (mod p), and since a^{p−1} ≡ 1 (mod p) (Fermat's little theorem), a^{(p−1)/2} is either 1 or −1 (mod p). This immediately implies that the criterion are equivalent to the biimplication:
We prove each direction separately.
(1) Assume a is a quadratic residue modulo p. We pick k such that k^{2} ≡ a (mod p). Then
The first step is valid since a ≡ b (mod n) implies a^{m} ≡ b^{m}(mod n) (see modular arithmetic#Congruence relation), while the second step is Fermat's little theorem again.
(2) Assume a^{(p − 1)/2} ≡ 1 (mod p). Then let α be a primitive root modulo p, so that a can be written as α^{i} for some i. 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^{2} = α^{i} ≡ a (mod p).
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^{1} ≡ 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^{6} ≡ 1 (mod 13), therefore 17 is a quadratic residue modulo 13. As confirmation, note that 17 ≡ 4 (mod 13), and 2^{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:
Example 2: Finding residues given a prime modulus p
Which numbers are squares modulo 17 (quadratic residues modulo 17)?
We can manually calculate:
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^{2} ≡ (−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} = 2^{8} ≡ 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^{8} ≡ 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.
Full article ▸
