Questions: Euler's Criterion

Question 1

To determine whether 5 is a quadratic residue mod 11 using Euler's Criterion (p = 11), what computation must you perform?

• A. Check whether 5 divides 11 − 1 = 10
• B. Compute 5^5 mod 11, since (p−1)/2 = 5
• C. Compute 5^10 mod 11 to apply Fermat's Little Theorem directly
• D. Find the square root of 5 mod 11 by testing all residue classes

Answer: (B)

Euler's Criterion says: compute a^((p−1)/2) mod p. For p = 11, (p−1)/2 = 5. So you compute 5^5 mod 11. If the result is 1, then 5 is a quadratic residue; if −1 (≡ 10 mod 11), then it is not. Actually: 5^2 = 25 ≡ 3, 5^4 ≡ 9, 5^5 ≡ 45 ≡ 1 (mod 11), so 5 is a QR mod 11 (indeed 4² = 16 ≡ 5). Option C computes a^(p−1) which always gives 1 by Fermat and tells you nothing. Option D works but is inefficient and misses the point of the criterion.

Question 2

Suppose you compute a^((p−1)/2) ≡ −1 (mod p). What does this tell you about a?

• A. a is a quadratic residue mod p because −1 is a perfect square in some fields
• B. a is a quadratic non-residue mod p — it has no square root mod p
• C. a ≡ −1 (mod p), so a = p − 1
• D. The computation was performed incorrectly, since a^((p−1)/2) must equal 1 by Fermat's Little Theorem

Answer: (B)

Euler's Criterion gives a two-way test: a^((p−1)/2) ≡ 1 means QR; a^((p−1)/2) ≡ −1 means non-residue. The result −1 (mod p) is perfectly valid — it is the unique element of order 2 in (ℤ/pℤ)*, and it indicates that a is not a perfect square in that group. Option D is wrong because Fermat says a^(p−1) ≡ 1, which factors as (a^((p−1)/2))² ≡ 1 — this allows the half-power to be either 1 or −1, it does not force 1.

Question 3

The fact that a^((p−1)/2) (mod p) must equal either 1 or −1 follows from Fermat's Little Theorem via the factorization (a^((p−1)/2) − 1)(a^((p−1)/2) + 1) ≡ 0 (mod p) and the primality of p.

• T. True
• F. False

Answer: True

Fermat's Little Theorem gives a^(p−1) ≡ 1 (mod p), so a^(p−1) − 1 ≡ 0. This factors as (a^((p−1)/2) − 1)(a^((p−1)/2) + 1) ≡ 0 (mod p). Since p is prime, ℤ/pℤ has no zero divisors, so one factor must be 0 — meaning a^((p−1)/2) ≡ 1 or a^((p−1)/2) ≡ −1. The primality of p is essential: for composite moduli, a product can be zero mod n without either factor being zero mod n.

Question 4

Euler's Criterion holds for most moduli, not just prime moduli, since it follows from Fermat's Little Theorem which holds whenever gcd(a, n) = 1.

• T. True
• F. False

Answer: False

Fermat's Little Theorem holds only for prime moduli. For composite n, the order of (ℤ/nℤ)* may not be n−1, and (ℤ/nℤ)* may not even be cyclic. The factorization argument that forces a^((p−1)/2) to be ±1 depends on p being prime (so ℤ/pℤ is a field with no zero divisors). For composite moduli, a^((n−1)/2) need not equal the Legendre symbol, and the Jacobi symbol (the generalization) does not reliably indicate quadratic residuosity.

Question 5

Using the group structure of (ℤ/pℤ)*, explain why a^((p−1)/2) ≡ 1 (mod p) if and only if a is a perfect square in that group.

Model answer: (ℤ/pℤ)* is cyclic of order p−1 with generator g. Every element a = g^k for some k. The element a is a perfect square iff k is even (since g^k = (g^(k/2))² requires k/2 to be an integer). Now compute a^((p−1)/2) = g^(k(p−1)/2). If k is even, the exponent k(p−1)/2 is a multiple of p−1, so by Fermat g^(k(p−1)/2) = (g^(p−1))^(k/2) = 1. If k is odd, the exponent k(p−1)/2 is an odd multiple of (p−1)/2, and since g^((p−1)/2) is the unique element of order 2 in the group (which equals −1 mod p), the result is −1. So the test a^((p−1)/2) ≡ 1 perfectly detects even k, i.e., perfect squares.

The group-theoretic argument shows why the criterion is not a coincidence: it is a direct consequence of the cyclic structure of (ℤ/pℤ)*. Squares are exactly the elements with even discrete logarithm, and raising to the (p−1)/2 power is exactly the parity-detection map in that cyclic group.