A solution modulo five is not automatically a solution modulo twenty-five—but it may contain the first digit of one. Hensel lifting turns that observation into an algorithm. Starting from a root modulo a prime, it determines the correction needed to obtain a root modulo the next prime power. Under the simple-root condition, the correction exists and is unique.
The calculation looks like Newton’s method, but closeness has a different meaning. Two numbers are close when their difference is divisible by a high power of the chosen prime. A correction can increase the ordinary integer representative while making the p-adic error smaller.
This is Guide 11 in the Bukit Timah Tutor Computational Number Theory series. It connects the modular square-root guide to arithmetic modulo prime powers. The prerequisite is ordinary congruences and modular inverses, not prior knowledge of p-adic analysis. Use the BTT Mathematics Hub to return to the wider subject.
1. A valuation measures divisibility
Fix a prime p. For a nonzero integer n, the p-adic valuation v_p(n) is the exponent of p in its prime factorisation. Thus v5(250)=3 because 250=2·5³, while v5(18)=0. The sign does not affect the valuation.
For nonzero rational a/b, define v_p(a/b)=v_p(a)−v_p(b). For example, v3(45/14)=2 and v3(14/45)=−2. By convention, v_p(0)=infinity, since zero is divisible by every positive power of p.
Valuation is not a new factorisation problem when p is fixed. Repeated exact division by p determines v_p(n). One does not need to find every other prime factor of n. This distinction makes valuation a cheap and focused source of structural information.
The p-adic absolute value is |x|_p=p^(−v_p(x)) for nonzero x and zero at x=0. Higher divisibility therefore corresponds to smaller absolute value. SageMath’s introductory p-adic documentation develops these conventions and their connection to finite-precision representation. [1]
2. Multiplication adds valuations
Write a=p^r u and b=p^s v, where neither u nor v is divisible by p. Then ab=p^(r+s)uv, and uv is also not divisible by p. Therefore v_p(ab)=v_p(a)+v_p(b).
For addition, v_p(a+b) is at least the smaller of v_p(a) and v_p(b). Factor out the smaller common power of p. The remaining sum is an integer, so divisibility cannot become worse. It can become better if the remaining leading residues cancel.
If the two valuations are unequal, equality holds: the lower-valuation term cannot be cancelled by a term containing an additional factor of p. For example, v5(25)=2 and v5(125)=3, while v5(150)=2.
When valuations are equal, cancellation can raise the answer. The numbers 25 and 100 both have valuation two, but their sum 125 has valuation three. A program that always replaces the valuation of a sum by the minimum would lose this possible gain.
3. Congruence is a precision statement
The relation a=b modulo p^k means v_p(a−b)≥k. Equivalently, the p-adic distance between a and b is at most p^(−k). Increasing k means that the two values agree to more base-p digits. [1]
This is not ordinary decimal approximation. The integers 1 and 626 differ by 625, so they agree modulo 5⁴ despite being far apart on a real number line. The relevant question is how many powers of five divide their difference.
A finite-precision value can be recorded as r+O(p^k), meaning all p-adic numbers congruent to r modulo p^k. The O-term is not an ordinary real-analysis error estimate: it specifies an ideal of possible p-adic errors.
It is important to keep the representative r and precision k together. The integer 16 by itself is exact. The approximation 16+O(125) represents an entire congruence class. Treating the second object as if it were the first silently invents information about higher digits.
4. From residue classes to p-adic integers
A p-adic integer can be viewed as a compatible sequence of residues modulo p, p², p³ and so on. Compatibility means that each later residue reduces to the earlier one. The sequence adds higher digits without changing digits already fixed.
For instance, a sequence beginning 1 modulo 5, 16 modulo 25, 16 modulo 125 and 516 modulo 625 is compatible. The base-five digits exposed so far are 1,3,0,4, starting at the units position. The repeated representative 16 at two stages means that the next digit is zero.
Computers usually store only a finite amount of this information. An exact theorem may guarantee an infinite compatible continuation, while a finite calculation returns a root only modulo the requested power. The theorem and the computed approximation should not be conflated.
We write Z_p for the p-adic integers in this guide and Z/p^kZ for a finite residue ring. Some texts use related notation differently; declaring the convention prevents confusion between an infinite ring and one of its finite quotients.
5. State Hensel’s simple-root condition
Let f be a polynomial with integer coefficients and p a prime. Suppose f(a)=0 modulo p and f'(a) is nonzero modulo p. Then the root a has a unique compatible lift to a root modulo p^k for every positive k, and a unique root in Z_p reducing to a modulo p. This is the simple-root form of Hensel’s lemma. [2]
The derivative condition says that f'(a) has a multiplicative inverse modulo p. It is not a decorative technicality: that inverse will determine the next correction digit. A vanishing derivative can produce several lifts or no lift.
The lemma is local to the chosen residue class. It does not say that f has only one root in all of Z_p. A polynomial can have two different simple roots modulo p, and each can lift uniquely along its own branch.
For f=X²−6 and p=5, the roots modulo five are 1 and 4. Their derivatives are 2 and 8, both nonzero modulo five. Therefore there are two distinct simple lifting branches, one from each root.
6. Derive one lifting step
Assume a is already a root modulo p^k. Every residue modulo p^(k+1) that reduces to a has the form a+t·p^k, with t in {0,…,p−1}. We need to choose the one digit t that makes f vanish to the next precision.
For an integer polynomial, expansion gives f(a+t·p^k)=f(a)+t·p^k f'(a) plus terms divisible by p^(2k). Since 2k≥k+1 for k≥1, those higher-order terms vanish modulo p^(k+1).
Write f(a)=c·p^k. After dividing the divisibility condition by p^k, the next digit must satisfy c+t f'(a)=0 modulo p. If f'(a) is invertible, the unique solution is:
t = −c · (f'(a))^−1 mod p, where c = f(a)/p^k is an exact integer. new root = a+t·p^k.
The division by p^k is exact division of integers before reducing modulo p. It is not multiplication by the inverse of p modulo p, which would be impossible. Distinguishing these two meanings of division is essential to implementing the step correctly.
7. Lift a square root of six from 5 to 25
Let f(X)=X²−6 and start with a=1 modulo five. The function value is f(1)=−5, so c=−1. The derivative is f'(1)=2, whose inverse modulo five is three.
t = −(−1)·3 = 3 mod 5. a_new = 1+3·5 = 16. 16²−6 = 250 = 10·25.
Thus 16 is a root modulo 25 and reduces to one modulo five. Trying all five candidates would also find it, but the derivative calculation selects the correct candidate directly.
Notice that 16 is not an ordinary integer square root of six. The statement is 16²=6 modulo 25. The modulus is part of the answer. Dropping it converts a correct modular statement into a false integer equality.
8. Continue to 125 and 625
At a=16 modulo 25, f(a)=250. Dividing by 25 gives c=10, which is zero modulo five. Hence the next correction digit is zero. The same integer representative 16 already solves the congruence modulo 125.
At the next step, divide 250 by 125 to get c=2. The derivative 32 is two modulo five, with inverse three. Therefore t=−2·3=4 modulo five, and the new representative is 16+4·125=516.
precision 5: root 1 precision 25: root 16 precision 125: root 16 precision 625: root 516 516²−6 = 266250 = 426·625.
The compatible base-five expansion begins 1+3·5+0·5²+4·5³. Each step both preserves the earlier residue and raises the modulus at which the equation holds.
The other root modulo 625 is −516=109. It reduces to four modulo five and belongs to the other simple branch. The two roots are distinct because the prime is odd and neither root is zero modulo five.
9. A second example: square roots of two modulo powers of seven
Start with a=3 modulo seven, since 3²−2=7. Here c=1 and f'(3)=6, whose inverse modulo seven is also six. The correction digit is −6=1, giving a=10 modulo 49.
Next, f(10)=98=2·49. The derivative 20 is six modulo seven. Thus t=−2·6=2 modulo seven, giving a=10+2·49=108 modulo 343.
Continue once more. We have 108²−2=11662=34·343. The derivative 216 is six modulo seven. The correction digit is −34·6=6 modulo seven, so the lifted representative is 108+6·343=2166 modulo 2401.
Nothing in the algorithm depends on the square-root expression being simple over the real numbers. The information being improved is divisibility by powers of seven. A learner who substitutes a decimal approximation to √2 into this calculation has switched to the wrong notion of approximation.
10. Why uniqueness survives every step
Suppose t and u both give lifts of the same root a modulo p^k. Subtract their correction equations to obtain (t−u)f'(a)=0 modulo p. Since f'(a) is invertible, t=u modulo p. Among the digits zero through p−1, they are identical.
The derivative remains nonzero along the branch because every later representative is congruent to the original seed modulo p. Evaluating an integer polynomial at congruent arguments gives congruent results, so the derivative’s residue modulo p is unchanged.
These two observations give the inductive mechanism. Existence follows by solving one linear equation for each digit. Uniqueness follows from the inverse derivative. Compatibility is built into the expression a+t·p^k.
A finite test can check many examples of this mechanism, but the proof establishes it for every input satisfying the hypotheses. The computer and the proof have complementary jobs: the proof controls the general case, while execution checks whether a particular implementation follows the proof.
11. When the derivative vanishes: no lift
Take f=X²−3 and p=3. The residue a=0 is a root modulo three, but f'(0)=0 modulo three. Every possible lift to modulo nine is 0,3 or 6. Each has square zero modulo nine, so none has square three.
The branch stops. This does not contradict Hensel’s lemma because the simple-root hypothesis failed. The example also shows why testing for a root modulo p alone is not sufficient to promise a root at every higher power.
In the correction equation, c=f(0)/3=−1 and f'(0)=0. We would need −1+0·t=0 modulo three, which is impossible. The failure is visible before enumerating all candidates.
12. When the derivative vanishes: several lifts
Now take f=X² with p=3 and seed a=0. The correction equation for lifting to modulo nine is 0+0·t=0, so all three digits are allowed. The roots modulo nine are 0,3 and 6.
At the following level, only the zero branch modulo nine continues to roots modulo 27: the roots are 0,9 and 18. The branches represented by 3 and 6 modulo nine do not survive. A list of roots at one precision is therefore not a promise that every branch continues forever.
In general, x²=0 modulo p^k exactly when v_p(x)≥ceil(k/2). The solutions are multiples of p^ceil(k/2), and there are p^floor(k/2) of them modulo p^k. This follows immediately from v_p(x²)=2v_p(x).
Valuation has turned a potentially large root search into an exact count and parametrisation. It also reveals why the singular case is structurally different from the unique-digit simple case.
13. The prime two needs deliberate handling
For f=X²−1 at an odd input, f'(X)=2X is always even. The simple-root condition fails modulo two, even though roots exist modulo every power of two. This is a useful reminder that a sufficient condition need not be necessary.
Modulo eight, all four odd residues 1,3,5,7 square to one. Modulo sixteen, the four roots are 1,7,9,15. For powers 2^k with k≥3, there are four roots of x²=1, rather than the two nonzero square roots familiar from odd prime fields.
The explanation uses (x−1)(x+1). For odd x, those two even numbers differ by two. One has exactly one factor of two, while the other must supply enough remaining powers for their product to be divisible by 2^k.
A square-root routine designed for odd primes cannot be extended to two merely by allowing p=2 in its argument list. Its branch logic and proof must cover that case.
14. Newton lifting can double the precision
Suppose a is a root modulo p^k and f'(a) is a unit. Instead of adding just one base-p digit, compute an inverse of f'(a) modulo p^(2k) and set b=a−f(a)(f'(a))^−1 modulo p^(2k). Then b is a root modulo p^(2k).
To see why, let the correction be h=b−a. It is divisible by p^k. The linear terms f(a)+h f'(a) vanish modulo p^(2k) by construction, while every remaining expansion term contains h² and is also divisible by p^(2k).
For f=X²−6 and a=16 modulo 25, f(a)=250 and f'(a)=32. The inverse of 32 modulo 625 is 293 because 32·293=9376=15·625+1. Therefore b=16−250·293=516 modulo 625.
The doubled-precision step agrees with the two single-digit steps. The number of Newton stages grows logarithmically in the requested exponent k, but the integers manipulated become larger as precision increases. Counting only the stages would not give the full bit complexity.
15. Stronger Hensel conditions exist
The simple-root condition is the cleanest entry point, not the only form of the theorem. A common stronger version uses the valuation inequality v_p(f(a))>2v_p(f'(a)). Under appropriate p-adic hypotheses, it guarantees a nearby root even when the derivative is not a unit. The neighbourhood and uniqueness statement must be specified carefully. [2,3]
This guide’s program deliberately implements only simple-root digit lifting. It rejects a zero derivative modulo p rather than guessing whether a stronger theorem might apply. A narrow function with an honest contract is more useful than a broad-looking function whose edge cases have no proof.
For a more general solver, separate singular branching, stronger Newton conditions and resource limits. Returning unsupported for a singular seed is not a claim that no mathematical root exists; it is a statement about the implemented method.
16. An exact classroom implementation
The code below accepts coefficients in increasing degree order: [-6,0,1] means X²−6. It verifies the small prime by trial division, checks the initial root and derivative condition, then adds one digit at a time. The primality check is suitable for classroom-sized p, not a proposed method for enormous primes.
from math import isqrt
def lift_simple_root(coefficients, p, seed, precision):
if type(p) is not int or p < 2:
raise ValueError("p must be prime.")
if any(p % d == 0 for d in range(2, isqrt(p) + 1)):
raise ValueError("p must be prime.")
if type(seed) is not int:
raise TypeError("seed must be an integer.")
if type(precision) is not int or precision < 1:
raise ValueError("precision must be positive.")
if not coefficients or any(type(c) is not int for c in coefficients):
raise ValueError("Supply integer coefficients in increasing degree.")
def evaluate(cs, x):
value = 0
for c in reversed(cs):
value = value * x + c
return value
derivative = [i * coefficients[i]
for i in range(1, len(coefficients))]
x = seed % p
if evaluate(coefficients, x) % p:
raise ValueError("The seed is not a root modulo p.")
slope = evaluate(derivative, x) % p
if slope == 0:
raise ValueError("The seed is not a simple root.")
inverse = pow(slope, -1, p)
modulus = p
for _ in range(1, precision):
value = evaluate(coefficients, x)
if value % modulus:
raise ArithmeticError("The root invariant was lost.")
digit = (-(value // modulus) * inverse) % p
x += digit * modulus
modulus *= p
if evaluate(coefficients, x) % modulus:
raise ArithmeticError("Final verification failed.")
return x, modulus
assert lift_simple_root([-6, 0, 1], 5, 1, 4) == (516, 625)
assert lift_simple_root([-2, 0, 1], 7, 3, 3) == (108, 343)All divisions of f(x) by the current modulus are exact integer divisions. The inverse derivative modulo p can be computed once because its residue does not change along the branch. The final verification evaluates the original polynomial, not a simplified surrogate.
Each returned x is normalised into the range zero through modulus−1. Starting with x in that range and adding a digit between zero and p−1 preserves the same range property at the next precision.
17. Testing the implementation without confusing tests with proof
For small p and precision k, enumerate every residue modulo p^k and compare the roots in the selected seed class with the program’s single result. Under the simple-root condition, the enumerated list should contain exactly that one representative.
The worked square-root examples and small simple-root cases were checked by exact arithmetic. That confirms the displayed outputs and provides bounded evidence for the teaching implementation. The general uniqueness guarantee comes from the lifting proof, not from the number of test cases run.
Important negative tests include a composite p, a seed that is not a root, a singular seed, an empty coefficient list, a noninteger coefficient and a nonpositive precision. A routine that handles only the successful path has not yet demonstrated reliable input handling.
For the singular seed zero of X² modulo three, the intended program response is a rejection of the simple-root contract. It would be an error to compare that response with a general root enumerator and conclude that the program should have returned one of three roots without changing its contract.
18. Combine local roots with the Chinese Remainder Theorem
When a modulus factors into coprime prime powers, solve the root problem locally and combine the results by CRT. Hensel lifting improves precision within one prime-power component; CRT combines different prime components. These are complementary operations, not competing alternatives.
Consider x²=11 modulo 175=25·7. Modulo 25, the roots are 6 and 19. Modulo seven, the roots are 2 and 5. Each pair of local choices determines one residue modulo 175.
For example, start with x=6+25t and impose x=2 modulo seven. Since 25=4 and the inverse of four is two modulo seven, t=(2−6)·2=6 modulo seven. Thus x=156. Using x=5 modulo seven instead gives t=5 and x=131.
Starting with 19 modulo 25 produces the other two roots, 44 and 19. The complete set is {19,44,131,156}. Direct substitution confirms that each square is 11 modulo 175. The four distinct sign combinations are preserved through CRT.
19. Local obstruction is decisive, but local success has limits
For x²=6 modulo 175, the modulus-five component has roots, but modulo seven the nonzero squares are 1,2 and 4. Six is not a square modulo seven. Therefore there can be no root modulo 175, regardless of how successfully the modulo-five roots lift.
This is an exact local obstruction: a global solution would reduce to a local solution, and one required local solution does not exist. Checking small prime components can therefore prevent a great deal of unnecessary work.
The converse should not be carelessly extended to arbitrary Diophantine equations. Solving congruences at selected moduli does not by itself prove that an integer solution exists. For the specific finite modulus composed of coprime prime powers, CRT gives the needed equivalence; beyond that setting, separate theorems are required.
Even our lifted root 516 modulo 625 does not prove that six is an integer square. Increasing modular precision is a different task from solving an equation in the ordinary integers.
20. Precision loss under division
Suppose a value is known modulo p^k and is divisible by p. Dividing its representative by p does not preserve k digits of absolute precision: the quotient is determined only modulo p^(k−1). The unknown error was a multiple of p^k, and after division it is only a multiple of p^(k−1).
For example, 25+O(5⁴) divided by five is 5+O(5³). The ordinary integer 25/5=5 is exact, but the finite-precision p-adic input represented more possibilities than the exact integer 25. The precision statement must follow the arithmetic.
Absolute precision records the power of p controlling the error; relative precision measures the number of known digits after accounting for the valuation of the value. SageMath documents these as distinct quantities. [1]
A residue that is zero at the available precision should not automatically be assigned the exact valuation infinity. It may merely have valuation at least k. Likewise, an apparent cancellation in finite-precision data may require additional input precision before its exact valuation can be determined.
21. What root lifting does not claim
A finite calculation returns a residue and modulus, not an infinite printed p-adic expansion. The simple-root theorem supplies the existence and uniqueness of the compatible continuation. The program supplies a checked finite part of it.
A proof of Hensel’s lemma has also been formalised in a theorem prover, illustrating the distinction between a formal theorem and a particular numerical implementation. A formal proof does not automatically verify every program inspired by the theorem. Robert Y. Lewis’s paper discusses that formalisation. [3]
For dependable computational work, retain both layers: a clear theorem with hypotheses, and an implementation whose inputs, invariants and outputs match those hypotheses. An elegant theorem cannot rescue code that silently divides by a nonunit or discards precision.
22. Practice set
1. Compute v5(250), v3(45/14) and v3(14/45). 2. Explain why 1 and 626 are close 5-adically. 3. Derive the correction equation for a+t·p^k. 4. Lift the root one of X²−6 from modulo five to modulo 25.
5. Why is the next correction digit zero at precision 125? 6. Find the root in the same branch modulo 625. 7. Find the other root modulo 625. 8. Lift the root three of X²−2 from modulo seven to modulo 49.
9. Continue that branch to modulo 343. 10. Explain why the root zero of X²−3 modulo three does not lift to nine. 11. List the roots of X²=0 modulo nine. 12. Count the roots of X²=0 modulo 5⁵.
13. List the roots of X²=1 modulo sixteen. 14. Solve X²=11 modulo 175. 15. Explain why X²=6 modulo 175 has no solution. 16. State the precision of (25+O(5⁴))/5. 17. Why is a singular-seed rejection not the same as no mathematical root? 18. What independent check should accompany every returned root?
23. Answers and decisive reasoning
1. The valuations are 3,2 and −2. 2. Their difference is 625=5⁴, so they agree modulo 5⁴ and their 5-adic distance is 5^−4. 3. Write f(a)=c·p^k; the first-order expansion reduces the next-root condition to c+t f'(a)=0 modulo p.
4. The digit is three because c=−1 and the inverse of two modulo five is three; the root is 16. 5. f(16)/25=10 is already zero modulo five. 6. At the next stage c=2, so t=4 and the root is 516. 7. Its negative is 109 modulo 625.
8. The digit is one, giving 10 modulo 49. 9. The next digit is two, giving 108 modulo 343. 10. Every lift of zero is divisible by three, so its square is zero modulo nine, never three.
11. The roots are 0,3 and 6. 12. A root must be divisible by 5³; there are 5²=25 such residues modulo 5⁵. 13. The roots are 1,7,9 and 15.
14. The roots are 19,44,131 and 156, obtained from the two roots modulo 25 and two modulo seven. 15. Six is a nonsquare modulo seven, giving a local obstruction. 16. The quotient is 5+O(5³).
17. The simple-root method may not apply when the derivative vanishes; singular branches can have zero, several or continuing lifts. 18. Evaluate the original polynomial at the returned representative and check divisibility by the returned modulus. Also check reduction to the requested seed class.
24. Teaching the distinction between size and precision
A useful lesson compares the representatives 1,16,16 and 516 without initially revealing the moduli. Their ordinary sizes suggest no simple convergence pattern. Adding the moduli 5,25,125 and 625 reveals that each new answer agrees with all the earlier digits while satisfying the equation at higher precision.
Then contrast the simple branch of X²−6 with the singular branches of X² and X²−3 modulo three. The derivative test should predict three different behaviours: one lift, several lifts or none. That turns the theorem’s hypothesis into something the learner can observe, not merely quote.
The transferable habit is to ask what the approximation preserves. Decimal approximation, rational approximation by continued fractions, residue classes and p-adic precision all retain different information. A calculation is meaningful only when its representation and error model match the problem.
Sources and further study
[1] SageMath, Introduction to the p-adics: valuation, representation and precision. [2] Keith Conrad, Hensel’s Lemma: simple and stronger lifting statements. [3] Robert Y. Lewis, A formal proof of Hensel’s lemma over the p-adic integers: formal theorem verification. The numerical branches and classroom code above are explicit worked calculations, not claims that these sources certify the program.
Continue through Batch 03
Use Guide 9: Finite Fields and Polynomial Arithmetic for the distinction between a field and a prime-power residue ring. Use Guide 10: Polynomial Factorisation over Finite Fields for exact polynomial structure. Continue to Guide 12: Arithmetic Functions, Möbius Inversion and Sieves for divisor structure and counting.