Questions: Quadratic Residues and the Legendre Symbol

Question 1

If the Legendre symbol satisfies (ab/p) = (a/p)(b/p), and you know that (a/p) = −1 and (b/p) = −1, what is (ab/p)?

• A. −1, because the product of two non-residues should remain a non-residue
• B. +1, because the Legendre symbol is multiplicative and (−1)(−1) = +1
• C. 0, because the product of two non-residues might be divisible by p
• D. It depends on the specific values of a and b, not just their symbols

Answer: (B)

The Legendre symbol is a group homomorphism from (ℤ/pℤ)× to {±1}, so it multiplies exactly like signs: (−1)(−1) = +1. The product of two quadratic non-residues is always a quadratic residue. This can be understood structurally: the QRs form an index-2 subgroup of (ℤ/pℤ)×, and the product of two elements from the non-residue coset lands back in the subgroup. Option A represents the common intuition that 'two bad things make a bad thing' — it is exactly wrong here.

Question 2

How many quadratic residues are there among {1, 2, 3, ..., 10} modulo 11?

• A. 4
• B. 5
• C. 6
• D. 10

Answer: (B)

For any odd prime p, exactly (p−1)/2 of the nonzero residues mod p are quadratic residues. With p = 11, that's (11−1)/2 = 5. The reason: the squaring map x ↦ x² on (ℤ/11ℤ)× is 2-to-1, since x and −x (= 11−x) both square to x². With 10 nonzero elements and each QR hit twice, there are exactly 5 distinct squares. You can verify: 1²=1, 2²=4, 3²=9, 4²=5, 5²=3 (mod 11) — these 5 values are the QRs.

Question 3

If a is a quadratic non-residue mod p, then a² is also a quadratic non-residue mod p.

• T. True
• F. False

Answer: False

False. For any integer a with p ∤ a, a² is by definition a perfect square — it is always a quadratic residue mod p. Non-residuosity of a means no integer x satisfies x² ≡ a; but a itself squares to a², so a² is always a QR. The Legendre symbol confirms this: (a²/p) = (a/p)² = (−1)² = +1.

Question 4

The Legendre symbol (ab/p) = (a/p)(b/p) holds even when a or b is a quadratic non-residue mod p.

• T. True
• F. False

Answer: True

True. Multiplicativity is unconditional (as long as p does not divide a or b). The formula works whether each factor is +1 or −1. This is what makes the Legendre symbol a group homomorphism: it respects multiplication in (ℤ/pℤ)× and sends it to multiplication in {±1}. The fact that QNR × QNR = QR (i.e., (−1)(−1) = 1) is a consequence of this homomorphism property, not an exception to it.

Question 5

Explain why exactly half of the integers in {1, 2, ..., p−1} are quadratic residues mod p, for an odd prime p.

Model answer: The squaring map x ↦ x² on (ℤ/pℤ)× is exactly 2-to-1: both x and −x square to x², and since p is odd, x and −x are always distinct (x ≡ −x would force 2x ≡ 0, i.e., p | x, contradicting our assumption). So the p−1 nonzero elements pair up into (p−1)/2 pairs {x, −x}, with each pair producing one distinct square. The image of the squaring map therefore has exactly (p−1)/2 elements — precisely half the nonzero residues.

The key is that x ≠ −x mod p when p is odd, so the 2-to-1 pairing is exact with no collisions. The same argument fails for p = 2 (where x ≡ −x for all x), which is why the theory of quadratic residues restricts to odd primes. The (p−1)/2 QRs form the kernel of the Legendre symbol homomorphism, making them a subgroup of index 2 in (ℤ/pℤ)×.