You compute the Jacobi symbol (a/n) = 1, where n = pq is a product of two distinct odd primes. What can you conclude about a?
Aa is definitely a quadratic residue mod n
Ba is definitely not a quadratic residue mod n
Ca may or may not be a quadratic residue mod n — Jacobi = 1 gives no guarantee when n is composite
DThe computation is invalid because n is not prime
This is the central warning about the Jacobi symbol. When n is composite, (a/n) = 1 does not imply that a is a quadratic residue mod n. It's possible that (a/p) = −1 and (a/q) = −1 at each prime factor, so the product (−1)(−1) = 1, even though a is not a square mod pq. The implication runs only one way: (a/n) = −1 guarantees non-residuosity, but (a/n) = 1 is inconclusive. Option A is the classic error.
Question 2 Multiple Choice
What is the primary computational advantage of the Jacobi symbol over directly evaluating Legendre symbols at each prime factor of n?
AIt produces a more accurate residuosity test than any individual Legendre symbol
BIt can be computed via a Euclidean-algorithm-like procedure without factoring n
CIt avoids the need for quadratic reciprocity in calculations
DIt works for even moduli, unlike the Legendre symbol
The whole point of the Jacobi symbol is efficiency: you can evaluate (a/n) using repeated application of quadratic reciprocity and supplementary rules — reducing to smaller symbols until a base case — without ever finding the prime factors of n. Factoring a large n is expensive (computationally hard); computing the Jacobi symbol is fast. This is why it appears in the Solovay–Strassen primality test.
Question 3 True / False
For composite n, the Jacobi symbol (a/n) = 1 guarantees that a is a quadratic residue modulo n.
TTrue
FFalse
Answer: False
This is false and is the central misconception to avoid. When n is prime, (a/n) = 1 does imply a is a QR. But when n is composite, (a/n) is defined as the product of Legendre symbols at each prime power factor. Those Legendre symbols could each be −1, and their product would still be 1, even though a is not a quadratic residue mod n. The Jacobi symbol can only certify non-residuosity: (a/n) = −1 is a conclusive negative.
Question 4 True / False
If the Jacobi symbol (a/n) = −1, then a is not a quadratic residue modulo n.
TTrue
FFalse
Answer: True
This is the one-directional guarantee the Jacobi symbol provides. If a were a quadratic residue mod n, then a would be a QR at every prime power factor of n, so each Legendre symbol would equal 1, and their product would be 1. A product of values in {1, −1} equals −1 only if an odd number of factors equal −1 — which cannot happen if all factors are 1. Therefore (a/n) = −1 conclusively rules out quadratic residuosity.
Question 5 Short Answer
Explain why the Jacobi symbol cannot serve as a direct quadratic residuosity test for composite moduli, even though it satisfies quadratic reciprocity.
Think about your answer, then reveal below.
Model answer: The Jacobi symbol (a/n) is defined multiplicatively as the product of Legendre symbols at each prime factor of n. When (a/p) = −1 for two different prime factors p and q, the product (a/p)(a/q) = (−1)(−1) = 1, so (a/pq) = 1 — but a is not a square mod pq. The Jacobi symbol 'loses information' about individual prime factors by multiplying their values, so a result of 1 is consistent with both residuosity and non-residuosity.
This asymmetry is inherent to the multiplicative definition. The Legendre symbol at a prime directly encodes residuosity; the Jacobi symbol at a composite aggregates multiple Legendre symbols and the signs can cancel. The Solovay–Strassen test exploits this: when (a/n) disagrees with a^((n−1)/2) mod n, n must be composite — the Jacobi symbol's failure to certify residuosity becomes a compositeness certificate.