Questions: Euler's Criterion for Quadratic Residues

Question 1

Using Euler's criterion to evaluate (3/11): which computation gives the correct result, and what does it tell you?

• A. 3^5 ≡ 1 (mod 11), so 3 is a quadratic residue mod 11
• B. 3^10 ≡ 1 (mod 11), so 3 is a quadratic residue mod 11
• C. 3^5 ≡ −1 (mod 11), so 3 is a non-residue mod 11
• D. We must enumerate all squares mod 11 to determine residuosity — Euler's criterion only confirms residues, not non-residues

Answer: (A)

The criterion says compute a^((p−1)/2) mod p. Here p=11, so the exponent is 5. Computing: 3^2=9, 3^4≡4, 3^5≡12≡1 (mod 11). Since this equals +1, (3/11)=1 and 3 is a QR. (Verify: 5²=25≡3 mod 11, confirming 3 is indeed a square.) Option B uses the full Fermat exponent (p−1), which always gives 1 and tells you nothing. Option D misses the point: Euler's criterion handles both residues and non-residues, outputting −1 in the latter case.

Question 2

Why can a^((p−1)/2) only be congruent to 1 or −1 mod p, and not some other value?

• A. Because the Legendre symbol only takes those two values, so the exponentiation must match
• B. Because a^((p−1)/2) is a square root of a^(p−1) ≡ 1 (mod p), and a prime has only ±1 as square roots of unity
• C. Because (p−1)/2 is always even when p is an odd prime
• D. Because Fermat's Little Theorem guarantees that any power less than p−1 reduces to 1 or −1

Answer: (B)

The core argument: let x = a^((p−1)/2). Then x² = a^(p−1) ≡ 1 (mod p) by Fermat. So x is a square root of 1 mod p, meaning p | (x−1)(x+1). Since p is prime, it must divide one of the factors, giving x ≡ 1 or x ≡ −1. This is why the output is binary — it follows from primality, not from the definition of the Legendre symbol. Option A reverses the logic: the Legendre symbol is defined to match the exponentiation result, not the other way around.

Question 3

If a^((p−1)/2) ≡ 1 (mod p), then a is a perfect square in the ordinary integers.

• T. True
• F. False

Answer: False

Euler's criterion only tells you about squares modulo p. Many numbers that are not perfect squares in the integers are quadratic residues mod p. For example, 3 is not a perfect square in the integers, but 3 ≡ 5² (mod 11), so it is a QR mod 11. The criterion is a statement about modular arithmetic, not about the integers themselves.

Question 4

Euler's criterion provides a computationally efficient method for evaluating the Legendre symbol, requiring only O(log p) multiplications via fast exponentiation.

• T. True
• F. False

Answer: True

Evaluating (a/p) directly requires checking whether any b satisfies b² ≡ a (mod p), which in the naive approach scans up to (p−1)/2 values. Euler's criterion replaces this with modular exponentiation of a^((p−1)/2) mod p, which fast (repeated squaring) exponentiation computes in O(log p) multiplications — far more efficient for large primes.

Question 5

Explain why the residue case of Euler's criterion holds: if a ≡ b² (mod p), why does a^((p−1)/2) ≡ 1 (mod p)?

Model answer: If a ≡ b² (mod p), then a^((p−1)/2) ≡ (b²)^((p−1)/2) = b^(p−1) ≡ 1 (mod p) by Fermat's Little Theorem (since p is prime and gcd(b,p)=1).

This is the cleanest direction of the proof. Substituting the definition of quadratic residue directly into the criterion, the exponent (p−1)/2 on b² becomes the full Fermat exponent on b — and Fermat's Little Theorem delivers 1 immediately. The non-residue direction is harder and requires arguing via primitive roots.