Why the unit case is not enough
For an odd prime , the existing quadratic-residue note treats targets coprime to . When the target is divisible by , a root can also be divisible by , so the derivative is no longer invertible modulo . Applying the unit-root lifting step directly would miss a genuine change in behavior.
We treat one odd prime power at a time. Throughout, is an odd prime and , and congruences are modulo unless another modulus is displayed.
Definition 6.2.1
(The -adic valuation)
For a nonzero integer , is the largest integer with . Thus with , and . If , then . No finite valuation is assigned to .
A nonzero target modulo the prime power
Theorem 6.2.2
(Roots of for a nonzero target)
Let with and . The congruence is solvable if and only if is even and is a square modulo . In that case it has exactly roots modulo , and each root has .
Proof
(Valuation, reduced modulus and lifting)
The valuation of a root. If , then and : otherwise divides and hence , contradicting . The two valuations below must be equal: if different, would have the smaller valuation, contradicting divisibility by . Thus , so must be even, say . If is odd, there are no solutions.
The reduced condition. For , write with . Division by gives the equivalent reduced condition
This division changes the modulus: it is not cancellation while keeping modulus .
The unit equation. If is a nonsquare modulo , there are no roots, since . If is a nonzero square modulo , the unit equation has exactly two roots modulo every , . Indeed there are two distinct roots modulo , distinct because is odd. Given a root modulo , its lifts satisfy
Since is invertible modulo the odd prime , exactly one makes the lift a root. Induction proves the claim.
Counting. Put . A residue modulo with corresponds to exactly one unit residue modulo , via . Since , each of the two roots modulo has lifts modulo , all of them roots of the reduced condition. Therefore the original congruence has exactly roots.
Proof X-ray
Where the hypotheses enter the count
The proof has one non-obvious move: after dividing by , the condition on lives modulo , but the root is only determined by modulo . The gap of powers of is free, and it is exactly where the factor in the count comes from.
The hypothesis is used once, to rule out a root whose square is divisible by ; it is what lets the target dictate the valuation of every root. Oddness of is used twice: to make the two roots modulo distinct, and to make invertible so that each root lifts uniquely. Without it the count fails already for a unit target: modulo the congruence has the four roots , not two.
The zero target
Theorem 6.2.3
(Roots of )
The roots of are exactly the residues divisible by , including . There are of them.
Proof
(Divisibility of the square)
For , means , that is, ; the residue is also a root. The residues modulo divisible by number . This case cannot be obtained by assigning a finite valuation to zero.
Worked example
Worked example 6.2.4
(Six roots of )
Here , , , , . Put ; the reduced condition is . Its roots are . Each has three lifts modulo : and . Multiplying by three gives six distinct roots modulo :
For instance . The count checks that the list is complete. By contrast has no solution because the target's valuation is one.
Worked example 6.2.5
(An even valuation with a nonresidue unit part)
Consider . Here , so , , , and the valuation test is passed. Writing and dividing by gives . The squares modulo are and , so there is no root. Both conditions of the theorem are needed: an even valuation and a square unit part.
Worked example 6.2.6
(The zero target modulo )
For we have and , so the roots are the multiples of :
There are of them. For instance , whereas . The count is odd, so it cannot come from the paired count for nonzero targets.
Common mistakes
Counterexample mode
Reducing the target does not preserve the old modulus
Claim: the roots of are with . The congruence has only the roots and , giving and . But , while . The claim loses four of the six roots. Dividing by must also divide the modulus: the correct condition is .
Common mistake
(Two roots is the unit count only)
For a unit target modulo an odd prime power there are zero or two roots. For a nonzero target of valuation the count is : six roots for , not two. Stopping after the two roots misses the lifts.
Common mistake
(Treating the zero target as valuation )
Putting into the nonzero formula is not valid. For it would suggest roots, whereas the correct count is .
Exercises
Quick check
(How many roots does have modulo ?)
Solution · Answer
The roots are the multiples of , giving classes.
Quick check
(Does have a solution?)
Solution · Answer
No. The target is nonzero modulo with odd valuation , but a root would need .
Quick check
(Find all roots of modulo .)
Solution · Answer
Write . Then , so . Taking modulo gives and roots , which is roots.
Quick check
(Why does the lifting argument for unit roots require odd?)
Solution · Answer
A unit root has invertible modulo only when is odd. For the factor two is not invertible, so the uniqueness-of-lift proof does not apply; modulo , has four roots. This does not by itself classify the two-power case.