To compute (3/7) using the Law of Quadratic Reciprocity, you note that 3 ≡ 3 (mod 4) and 7 ≡ 3 (mod 4). What is the correct conclusion?
A(3/7) = (7/3), because both primes are odd and the law allows free flipping
B(3/7) = −(7/3), because both primes are ≡ 3 (mod 4), making the product (3/7)(7/3) = −1
C(3/7) = (7/3) · (−1)^3 = −(7/3), but only if 3 < 7
D(3/7)(7/3) = 1, because the exponent (p−1)/2 · (q−1)/2 = 1 · 3 = 3 is always positive
The reciprocity formula says (p/q)(q/p) = (−1)^{(p−1)/2 · (q−1)/2}. With p=3, q=7: (3−1)/2 = 1, (7−1)/2 = 3, product = 3, which is odd. So (3/7)(7/3) = (−1)³ = −1, meaning the symbols have opposite signs. The sign flip happens exactly when both primes are ≡ 3 (mod 4) — since that makes (p−1)/2 and (q−1)/2 both odd, and their product odd. To finish: (7/3) = (1/3) = 1 since 7 ≡ 1 (mod 3), so (3/7) = −1. Indeed, 3 is not a quadratic residue mod 7 (the QRs mod 7 are 1, 2, 4).
Question 2 Multiple Choice
When does the Law of Quadratic Reciprocity alone suffice to compute any Legendre symbol (a/p)?
AAlways — the law handles all cases by repeated flipping until a small base case is reached
BWhenever a and p are both odd primes — the law handles all such pairs directly
CNever alone — you also need the supplementary laws for (−1/p) and (2/p) to handle reductions that produce −1 or 2
DOnly when a < p, since flipping reduces the larger argument
The main reciprocity law handles pairs of distinct odd primes p and q. But the reduction process — analogous to the Euclidean algorithm — will eventually produce residues of −1 or 2 (just as Euclidean algorithm eventually reaches small remainders). These cannot be handled by the main law, which requires two odd primes. The first supplementary law (−1/p) = (−1)^{(p−1)/2} and the second supplementary law (2/p) = (−1)^{(p²−1)/8} are essential components of the complete algorithm. Forgetting them is the most common error in practice.
Question 3 True / False
The sign flip in the Law of Quadratic Reciprocity — (p/q)(q/p) = −1 — occurs if and only if both p and q are congruent to 3 mod 4.
TTrue
FFalse
Answer: True
The exponent (p−1)/2 · (q−1)/2 is odd (giving a product of −1) if and only if both factors are odd — i.e., both (p−1)/2 and (q−1)/2 are odd — i.e., both p ≡ 3 (mod 4) and q ≡ 3 (mod 4). If at least one prime is ≡ 1 (mod 4), then at least one factor is even, making the product even, so (p/q)(q/p) = 1 and you can flip freely without a sign change. The sign flip is the case to remember because it is the exception; free flipping is the rule.
Question 4 True / False
The Law of Quadratic Reciprocity, together with its two supplementary laws, provides a complete algorithm for computing (a/p) for any integer a and odd prime p, without computing any large powers.
TTrue
FFalse
Answer: True
This is the practical payoff of the law. Without reciprocity, computing (a/p) requires evaluating a^{(p−1)/2} mod p — a large modular exponentiation. With the full toolkit (main law + both supplementary laws), you can reduce (a/p) recursively — flipping the symbol, reducing mod the new modulus, handling factors of −1 and 2 — until you reach trivial base cases. The process terminates because the numbers decrease, just like the Euclidean algorithm. No large powers are needed at any step.
Question 5 Short Answer
Explain why computing Legendre symbols via the Law of Quadratic Reciprocity is analogous to computing GCDs via the Euclidean algorithm. What plays the role of 'division with remainder'?
Think about your answer, then reveal below.
Model answer: In the Euclidean algorithm, you reduce gcd(a, b) to gcd(b, a mod b) — replacing the larger number by the smaller remainder. In Legendre symbol computation, you reduce (p/q) to ±(q/p) by flipping (the sign depends on whether both are ≡ 3 mod 4), then reduce further by replacing p with p mod q. The 'division with remainder' step is: (p/q) = (p mod q / q), because the Legendre symbol (p/q) depends only on p mod q by periodicity. The numbers decrease with each step, guaranteeing termination, and supplementary laws handle the base cases (analogous to gcd terminating when the remainder reaches 1).
Both algorithms achieve efficiency by recursive reduction. The Euclidean algorithm can compute gcd(10^100, 10^100 − 1) in about 300 steps by reduction. Similarly, reciprocity lets you compute (10^100 + 3 / some large prime) by reducing the problem size at each step. The parallel is not just metaphorical — both algorithms have similar worst-case step counts proportional to the number of digits, and both exploit the same periodicity structure (remainder for gcd; congruence for Legendre symbol).