Motivation
A polynomial root modulo a prime is only the first digit of a possible root at higher prime powers. Sometimes each next digit is forced; sometimes every digit works, or none does. The derivative describes this distinction, but it is its residue modulo the prime, rather than real differentiability, that matters.
The earlier square-root unit handled a particular polynomial and its special singular cases. Here we prove the one-step rule for every integer polynomial, so a finite lifting tree gives all roots at any prescribed prime-power precision. Compatible infinite paths lead to p-adic integers. Defining them as compatible residues lets us prove the root theorem without assuming a theory of real convergence or an undeveloped p-adic field.
Let be any prime, including two, and . Its formal derivative is when . Neither a nonzero root nor an odd prime is required for the general simple-root theorem. The essential hypothesis is that the derivative is nonzero modulo p.
Definitions
Definition 10.1.1
(Lifts, simple roots, and singular roots)
A root modulo has the candidate lifts modulo , , after a representative has been chosen. Its prime-level root is simple if , and singular otherwise. The derivative residue depends only on modulo , so this status is unchanged along a branch.
A lifting tree has the roots modulo at level , and joins a root to the roots one level higher which reduce to it. Every higher root reduces to a root below. Distinct parent classes have disjoint lists of children.
Definition 10.1.2
(-adic integers as compatible residues)
The ring consists of sequences with and . Addition and multiplication are coordinatewise. Compatibility follows because reduction is a ring homomorphism.
Equivalently an element has unique base-p digits , , whose first digits give modulo . An infinite digit expression here means compatible finite truncations, not an infinite sum evaluated in the real absolute value. Integer residues give an embedding : a nonzero integer cannot be divisible by every .
For , define coordinatewise. It is zero exactly when every is zero modulo . Thus a root in this ring is precisely an infinite compatible path of polynomial roots. This definition does not identify a p-adic integer with an ordinary real number.
Theorems
Theorem 10.1.3
(The exhaustive one-digit lifting rule)
If , put . The candidate is a root modulo exactly when
If is nonzero modulo , there is exactly one child. If the derivative is zero and is zero modulo , there are all children. If the derivative is zero and is nonzero, there are none. This is valid for every , including .
Theorem 10.1.4
(Compatible roots and simple Hensel lifting)
Each simple root modulo extends uniquely to a root in with that first residue, and uniquely to a root at every finite higher precision. More generally, has a root in exactly when it has a root modulo for every , even if those finite roots were not initially chosen compatibly.
The ring is a domain of characteristic zero. An element is a unit exactly when its first residue is nonzero modulo p. Singular roots need not have unique children or unique infinite continuations.
Proof sketch or proof idea
The derivative appears through an exact polynomial identity
Proof
(Exact expansion and one linear congruence)
The binomial theorem gives an integer polynomial such that
Indeed, in each power , the terms of h-degree zero and one are and ; all remaining terms have a factor . This argument divides by neither two nor any factorial, so it is valid at the prime two.
Take . Since for , the last term vanishes modulo . The first two terms give , proving the congruence. A nonzero derivative has one inverse in the prime field, hence exactly one solves it. A zero derivative leaves either the identity zero equals zero, allowing every , or a nonzero constant equals zero, allowing none. This proves all cases rather than declaring singular roots outside the algorithm.
Starting with every root modulo and applying the rule therefore enumerates all roots modulo any chosen . Every possible next class has one of the displayed forms, and parents are disjoint, so induction proves completeness and no repetitions. If the reduction of is a nonzero polynomial, the initial root count is bounded by its reduced degree; if every coefficient is divisible by , that reduction is the zero polynomial and every residue is initially a root. A degree bound must not be applied to that zero reduction. Finite enumeration here is not a claim of an efficient algorithm for very large precision or input size.
Proof X-ray
Why one exact identity settles every case
The key move is the identity with integer , used at . The hypothesis enters only through , which removes the quadratic term modulo and leaves a congruence linear in the single unknown digit . Linearity over the field produces the trichotomy: a unit coefficient gives one solution, and a zero coefficient gives all or none according to . Since nothing is divided by a factorial, the argument is uniform in , including .
Simple branches have one infinite continuation
Proof
(Forced choices and finite branching)
A simple root keeps its derivative residue nonzero along every lift, because integer polynomial evaluation respects congruence. The one-step rule therefore selects exactly one child at every level. These choices form a compatible sequence and hence a p-adic root by definition. Conversely any p-adic root with the given first residue must use those same uniquely forced choices at all levels, so equals this one. No limiting argument involving real magnitudes is needed.
For arbitrary singular branches, existence at all finite levels still gives a compatible path. The first level is finite. If roots exist arbitrarily high, at least one first-level root has descendants at arbitrarily high levels; otherwise finitely many finite height bounds would bound the whole tree. Its finitely many children include one with the same unbounded-descendant property. Repeat this selection. The chosen compatible roots define a p-adic integer and make vanish in every coordinate. The reverse implication follows by reduction. This finite-branching argument is the extra step that turns separate finite-level existence into a single compatible solution.
Proof X-ray
Existence at each level needs a compatibility argument
A collection of unrelated finite roots is not itself a p-adic integer. Simple roots supply compatibility through unique lifting. In the singular case, finite branching lets us choose a child that still reaches arbitrarily high levels. Repeating that choice constructs one path. Neither a few successful lifts nor a finite-looking digit pattern proves existence at all levels.
Units, first nonzero digits, and absence of zero divisors
Proof
(Inverses level by level and the first nonzero digit)
If the first residue is nonzero, every is a unit modulo . Its inverse is unique, so inverses at adjacent levels reduce to one another. They form a compatible multiplicative inverse in . If the first residue is zero, no inverse can exist, since reducing a product equal to one would contradict multiplication modulo p.
A nonzero -adic integer has a first nonzero digit, at some position . Shifting its digits gives with a unit. Such an expression is nonzero because its residue modulo is a nonzero multiple of . If also is nonzero, their product is with a unit, whose first nonzero digit is at position . Thus the product is not zero, proving the domain property. Characteristic zero follows from the integer embedding already proved. In particular residue characteristic does not make the entire ring have characteristic p.
These facts also explain how finite root counts can differ from the number of compatible infinite roots. A nonzero polynomial over a domain has no arbitrary cancellation of its linear factors; finite quotient rings can have zero divisors. The next example makes this distinction explicit at two.
Worked examples
Worked example 10.1.5
(A uniquely lifted cube root at five)
For modulo five, testing the five residues gives the single root three. Its derivative is two modulo five, so it is simple. At , , giving zero and root three modulo twenty-five. At , is one and the correction is , so is two and the root is modulo 125. The check is . Further digits are uniquely determined. The residue fifty-three is a congruence class at that precision, not a claim of closeness to the real cube root in ordinary absolute value.
Worked example 10.1.6
(Four finite two-power roots, but two infinite roots)
For at two, the initial root one is singular. It has children one and three modulo four, then all four odd classes modulo eight. At the next step, classes three and five have odd and no children, while one and seven each have two. The roots modulo sixteen are .
In , factorization and the domain property force or , both genuine roots. They are distinct because the ring has characteristic zero, although both reduce to one modulo two. Having four roots at each sufficiently high finite level does not produce four infinite roots: some finite branches terminate. Derivative singularity does not by itself tell us whether the eventual root set is empty, one element or several.
Worked example 10.1.7
(A prime-level root with no next digit)
For , zero is the only root modulo p. Its derivative is zero there, but is nonzero modulo p. The one-step rule gives no child modulo , so there is no p-adic root. This agrees with the earlier square-congruence valuation obstruction, now obtained as a special case of the general polynomial rule. Prime-level solvability alone proves no higher-level existence.
Common mistakes
Common mistake
(Simple means a nonzero derivative, not a nonzero root)
Simple means nonzero derivative modulo , not nonzero root. At two a polynomial with odd derivative still has unique lifting. Dividing a Taylor expression by factorials is unnecessary and would obscure the two-adic case.
Common mistake
(Finite-level roots are not yet a p-adic root)
A singular root has all or none of its immediate children, but different children may behave differently at later levels. A p-adic root is a compatible infinite sequence, not an arbitrary choice of one root at each level. Finite computations cannot certify the universal statement that every level has a root unless another argument supplies it. We have proved the simple-root theorem and exhaustive one-step singular rule, not a general strong valuation-form Hensel theorem or a closed-form classification of every singular branch tree.
Counterexample mode
Without a simple root, lifting can fail or branch
Claim: every root modulo extends uniquely to a root in . Take and . The residue is a root modulo , but and is odd, so the one-step rule gives no child. Directly, and are both modulo . Existence fails. For the root modulo is also singular, and it has the two continuations and in found in the worked example, so uniqueness fails as well. The repaired statement assumes .
Summary
An exact binomial expansion reduces each next digit to one linear congruence, with unique, full or empty child lists. Simple roots give unique compatible p-adic roots; finite branching proves the general all-level existence criterion. Compatible residues also give the unit and domain properties that distinguish finite congruence behavior from infinite p-adic solutions.
Exercises
Quick check
(Lift the root three of modulo seven through modulus 343. Find the other root at that precision and justify completeness.)
Solution · Answer
At the first step, is one and the derivative six modulo seven, so gives one. The root is ten modulo forty-nine. Next is , derivative twenty is six modulo seven, so two and the root is modulo 343. The opposite root is 235. The only prime-level roots are three and four, both simple, so their two unique branches give all roots. The exact check is .
Quick check
(Determine every root of modulo 27 and in , using both simple lifting and the polynomial factorization.)
Solution · Answer
Modulo three the roots are zero, one and two. The derivative is minus one modulo three at every residue, so each lifts uniquely. The integer roots already give the three branches, hence modulo 27 the roots are . In they are exactly ; the factorization and the domain property give the same complete answer.
Quick check
(For odd , track the roots of from modulus to and . Count the roots at the third level and explain which second-level branches die.)
Solution · Answer
At the first root zero, is , so all children modulo occur. At the next step, and the derivative is zero modulo p. Thus only have children; each has of them. These parents are distinct for odd , yielding exactly roots modulo . All other second-level branches terminate. The calculation is consistent with the nonunit square-root classification but follows from the general rule.
Quick check
(Show that the compatible truncations define the inverse of in . Explain the case and why this is not ordinary real-series convergence.)
Solution · Answer
Multiplying the kth partial sum by gives , equal to one modulo . The partial sums are compatible, so they define a p-adic inverse. At the digits are all one and the kth residue is , precisely the compatible residues of the integer minus one, which is indeed its own inverse. These partial sums grow without bound in the real absolute value; the expression denotes compatible congruences, not convergence as a real geometric series.