Questions: Quadratic Residues and the Legendre Symbol

Question 1

Suppose (a/p) = −1 and (b/p) = −1 for a prime p. What is (ab/p)?

• A. −1, because combining two non-residues produces another non-residue.
• B. 0, because neither a nor b is a perfect square mod p.
• C. 1, because the product of two quadratic non-residues is always a quadratic residue.
• D. It depends on the specific values of a and b; no general rule applies.

Answer: (C)

By multiplicativity of the Legendre symbol, (ab/p) = (a/p)(b/p) = (−1)(−1) = 1. This is the analogue of multiplying two negative numbers: the result is positive (a quadratic residue). The same rule says two residues multiply to a residue (1 × 1 = 1), and a residue times a non-residue is a non-residue (1 × −1 = −1). Option A is the natural but wrong intuition — it reverses the algebraic fact. Multiplicativity is the Legendre symbol's most useful computational property.

Question 2

Among the nonzero elements {1, 2, 3, ..., p−1} of ℤ/pℤ for an odd prime p, how many are quadratic residues?

• A. p − 1, because every nonzero element has a square root in some extension field.
• B. (p − 1)/2, because the squaring map x ↦ x² is two-to-one: x and −x always yield the same square.
• C. (p + 1)/2, because we must count zero as a quadratic residue.
• D. It varies depending on the prime; no general formula exists.

Answer: (B)

Among the p − 1 nonzero elements of ℤ/pℤ, exactly (p−1)/2 are quadratic residues and (p−1)/2 are non-residues. The reason is that the squaring map x ↦ x² hits each quadratic residue exactly twice: both x and −x (≡ p−x mod p) map to x². Since x ≠ −x for nonzero x in ℤ/pℤ (assuming p is an odd prime), the p−1 nonzero elements pair up into (p−1)/2 pairs with the same square, giving (p−1)/2 distinct quadratic residue values. Zero (p | a) is the special case where (a/p) = 0, not classified as a QR.

Question 3

The product of a quadratic residue and a quadratic non-residue mod an odd prime p is always a quadratic non-residue.

• T. True
• F. False

Answer: True

By multiplicativity of the Legendre symbol: if (a/p) = 1 and (b/p) = −1, then (ab/p) = (a/p)(b/p) = (1)(−1) = −1, so ab is a non-residue. This follows from the analogy with multiplication of signs: positive × negative = negative. The three cases are: QR × QR = QR, NR × NR = QR, QR × NR = NR. Knowing just the Legendre symbols of a and b fully determines the symbol of their product.

Question 4

If x² ≡ a (mod p) has a solution and p ∤ a, then it has exactly one solution in {1, 2, ..., p−1}.

• T. True
• F. False

Answer: False

When x² ≡ a (mod p) is solvable (a is a quadratic residue), it has exactly two solutions: if x₀ is one solution, then −x₀ ≡ p − x₀ (mod p) is the other, since (−x₀)² = x₀² ≡ a. These are distinct elements of ℤ/pℤ because x₀ ≠ −x₀ when p is an odd prime and p ∤ x₀. This two-to-one nature of the squaring map is exactly why only half of the nonzero elements are quadratic residues — each residue value is the image of exactly two inputs.

Question 5

Explain why exactly half of the nonzero elements of ℤ/pℤ are quadratic residues, for an odd prime p.

Model answer: The squaring map x ↦ x² on the nonzero elements of ℤ/pℤ is exactly two-to-one: for each nonzero a, both x and −x satisfy x² ≡ a (mod p), and x ≠ −x since p is odd (x = −x would mean 2x ≡ 0, so p | x, contradicting x ≠ 0). Therefore the p−1 nonzero inputs pair up into (p−1)/2 pairs, each pair mapping to the same output. The image of the squaring map — the set of quadratic residues — has exactly (p−1)/2 elements, which is half of the nonzero elements.

The key is the pairing argument: every input x has a distinct partner −x with the same square. Since the inputs pair perfectly (no element is its own pair in ℤ/pℤ for odd p), the outputs are exactly half as many as the inputs. This same reasoning shows that every quadratic residue has exactly two square roots, while quadratic non-residues have none. The 2-to-1 structure of the squaring map is the fundamental fact underlying the entire theory of quadratic residues.