Euler's criterion

related topics
{math, number, function}

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 k2a (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:

Proof of Euler's criterion

Every number either is or isn't a quadratic residue (mod p). Also, since the square-roots of 1 are 1 and −1 (mod p), and since ap−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 k2a (mod p). Then

The first step is valid since ab (mod n) implies ambm(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 k2 = αia (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 = 171 ≡ 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 = 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:

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 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.

Full article ▸

related documents
BPP
NP-hard
Partial fractions in integration
Alternative algebra
Intersection (set theory)
Regular space
Real line
Decision problem
Bézout's identity
Polynomial time
C*-algebra
Heaviside step function
CLU (programming language)
Whittaker–Shannon interpolation formula
Algebraic number
T1 space
Magma (algebra)
Logarithmic integral function
Separated sets
Stirling number
Dyadic rational
Twin prime conjecture
Cayley's theorem
Syntactic sugar
Topological ring
Goldbach's weak conjecture
Magma computer algebra system
Kernel (category theory)
Amicable number
Category (mathematics)