You want to solve x² ≡ 5 (mod 21). What is the correct first step, and what does success at this step guarantee?
AApply Hensel's lemma directly to lift a solution from mod 3 to mod 21
BCheck whether 5 is a quadratic residue mod 21 using the Legendre symbol (5/21)
CFactor 21 = 3 × 7, then check solvability mod 3 and mod 7 separately using Legendre symbols; a solution mod 21 exists iff solutions exist for both
DUse the Chinese Remainder Theorem to immediately write down the solution without checking solvability
The Legendre symbol is only defined for odd primes, not for composite moduli. The correct strategy is to factor 21 = 3 × 7, then apply (5/3) and (5/7) separately. If both are 1, a solution mod 21 exists and can be assembled via CRT. If either is -1, no solution exists mod 21. Option B is the tempting wrong answer: (5/21) is not a standard Legendre symbol, and computing it without decomposing the modulus bypasses the actual check. Solvability mod a composite number requires solvability mod each prime factor.
Question 2 Multiple Choice
You have found that r₁ = 3 satisfies r₁² ≡ 4 (mod 5). You want to lift this to a solution mod 25 using Hensel's lemma. What is the key condition that must hold for the lift to succeed, and why?
Ar₁ must be odd; even solutions cannot be lifted to higher prime powers
B2r₁ must not be ≡ 0 (mod 5), i.e., the derivative of x² - 4 evaluated at r₁ must be nonzero mod p
CThe discriminant of x² - 4 must be a perfect square; otherwise lifting fails for all k > 1
DThe prime p = 5 must divide r₁; otherwise the lift formula is undefined
Hensel's lemma lifts solutions when the 'derivative condition' holds: 2r₁ ≢ 0 (mod p). Here, 2·3 = 6 ≡ 1 (mod 5) ≠ 0, so the lift succeeds. This condition fails precisely when p = 2 (since 2r₁ is always even) or when p | r₁ (making 2r₁ divisible by p). When it fails, solutions mod pᵏ must be analyzed directly, which is why p = 2 requires special treatment. Option D is backwards: the condition requires p ∤ r₁, not p | r₁.
Question 3 True / False
If x² ≡ d (mod p) has no solution for some prime p dividing n, then x² ≡ d (mod n) also has no solution.
TTrue
FFalse
Answer: True
By the Chinese Remainder Theorem, x² ≡ d (mod n) splits into independent congruences x² ≡ d (mod pᵢᵃⁱ) for each prime power factor of n. A solution mod n exists only if all component congruences have solutions. In particular, any solution mod n reduces mod p to a solution of x² ≡ d (mod p). Contrapositive: if no solution exists mod p, no solution can exist mod n. This is why the Legendre symbol check is the first gating step — it can immediately rule out solvability.
Question 4 True / False
The Legendre symbol (d/p) = 1 is sufficient to guarantee that x² ≡ d (mod pᵏ) has a solution for most k ≥ 1, with no further conditions needed.
TTrue
FFalse
Answer: False
For odd primes p and when p ∤ d, Hensel's lemma does extend solutions from mod p to mod pᵏ, so for odd primes with p ∤ r₁ the statement is true. But for p = 2, the Legendre symbol is not even defined, and solvability mod 2ᵏ for k ≥ 3 requires additional conditions on d mod 8. The statement is false as a universal claim. More precisely, the derivative condition 2r₁ ≢ 0 (mod p) must hold for Hensel lifting to succeed automatically, and p = 2 is the primary exception requiring separate analysis.
Question 5 Short Answer
Explain the three-tool strategy for solving a general quadratic congruence ax² + bx + c ≡ 0 (mod n), and explain why each of the three tools is necessary.
Think about your answer, then reveal below.
Model answer: Step 1: Complete the square to reduce to x² ≡ d (mod n). Step 2: Factor n = p₁ᵃ¹ · p₂ᵃ² · ··· and use the Chinese Remainder Theorem to decompose into congruences mod each prime power. Step 3: For each prime p, use the Legendre symbol (d/p) to check solvability mod p; then use Hensel's lemma to lift solutions from mod p to mod pᵏ. The three tools are necessary for different levels: the Legendre symbol handles the prime-level existence check, CRT handles how prime-power solutions combine into a solution mod n, and Hensel lifting handles the gap between prime and prime-power solutions.
No single tool handles the full problem: the Legendre symbol only works for primes, not prime powers or composites; CRT requires knowing solutions modulo each prime power component; Hensel lifting only applies to odd primes satisfying the derivative condition. Together they form a complete algorithm. This three-step structure — check, decompose, lift — mirrors the general strategy in number theory of reducing problems about arbitrary moduli to problems about prime powers.