Math 115. The Stronger General Hensel’s Lemma

This handout gives the stronger version of the general Hensel’s Lemma (Theorem 2.24), a variant of it, and also a corollary.

Theorem (Hensel’s lemma, general version). Let f ∈ ℤ[x] , let p be a prime, and let a ∈ ℤ. Assume that f(a) ≡ 0 (mod p^{j}) for some j, p^{τ} ∥ f′(a) for some τ ∈ ℕ, and that j ≥ 2τ + 1 . Then: (a). There is an integer t, unique modulo p^{j−2τ} , such that f(a + tp^{j−τ}) ≡ 0

(mod p^{2j−2τ}) . Also, t is the (unique) solution to the congruence

\frac{f′(a)}{p^{τ}}t ≡ −\frac{f(a)}{p^{j}} (mod p^{j−2τ}) .

(b). If b ≡ a (mod p^{j−τ}) , then f(b) ≡ f(a) (mod p^{j}) .

(c). If b ≡ a (mod p^{τ+1}) , then p^{τ} ∥ f′(b) . In particular, this holds if b ≡ a

(mod p^{j−τ}) .

Proof. (a). Let b = a + tp^{j−τ} (with t ∈ ℤ unknown). By Taylor’s formula,

f(b) = f(a) + f′(a)(tp^{j−τ}) + \frac{f′′(a)}{2}(tp^{j−τ})^{2} + ⋯ + \frac{f^{(n)}(a)}{n!}(tp^{j−τ})^{n} .  (*)

Each coefficient f^{(i)}(a)/i! is an integer; this is because the polynomial f^{(i)}(x)/i! has integer coefficients (this can be checked term by term, using Theorem 1.21 on page 36). Therefore the third and subsequent terms are all ≡ 0 (mod p^{2j−2τ}) (since j ≥ 2τ + 1 implies j ≥ τ ).

Setting f(b) congruent to zero modulo p^{2j−2τ} then gives the congruence

0 ≡ f(a) + f′(a)(tp^{j−τ}) (mod p^{2j−2τ}) ;

rearranging terms and dividing by p^{j} then gives

\frac{f′(a)}{p^{τ}}t ≡ −\frac{f(a)}{p^{j}} (mod p^{j−2τ}) .

Note that f(a)/p^{j} ∈ ℤ and that f′(a)/p^{τ} is an integer prime to p, hence prime to p^{j−2τ} . This gives t uniquely modulo p^{j−2τ} , as was to be shown.

(b). If b ≡ a (mod p^{j−τ}) , then we have b = a + tp^{j−τ} , so the equation (*) is true. This part then follows from the fact that all terms on the right-hand side other than the first are multiples of p^{j} . Indeed, for the terms (f^{(i)}(a)/i!)(tp^{j−τ})^{i} with i ≥ 2 , this is true because f^{(i)}(a)/i! ∈ ℤ and i(j − τ) ≥ 2j − 2τ > j, and when i = 1 it is true because f′(a)(tp^{j−τ}) is a multiple of p^{j} .

(c). By Theorem 2.2,

b ≡ a (mod p^{τ+1}) ⟹ f′(b) ≡ f′(a) (mod p^{τ+1}) ,

and it then follows that p^{τ} ∥ f′(b) since p^{τ} ∥ f′(a) . The last part is true because j − τ ≥ τ + 1 . □

Since t is only unique modulo p^{j−τ} , a + tp^{j−τ} is unique modulo p^{2j−3τ} , and so the congruence f(x) ≡ 0 (mod p^{2j−2τ}) has p^{τ} solutions modulo p^{2j−2τ} corresponding to a given value of a.

It is interesting (although perhaps beyond the scope of this course) to see how this plays out in the situation of Example 13, especially the diagram on page 90. We have f(x) = x^{2} + x + 223 , so f′(x) = 2x + 1 . First look at the node 13 in the mod 27 level. We have f′(13) = 27 , so κ = 3 there. So Hensel’s lemma can’t be applied unless we have solutions modulo 3^{7} = 2187 . (We can’t even count on κ being constant on this subtree, and in fact going up to the next level, f′(40) = 81 , so κ = 4 there. But in any case, the presence of dead ends above this node is not surprising.)

At the other two nodes on the mod 27 level, we have f′(4) = 9 and f′(22) = 45 , so κ = 2 at both of them. Also, if x ≡ y (mod 27) then f′(x) ≡ f′(y) (mod 27) , so κ = 2 everywhere in the tree above each of those two nodes.

When κ = 2 , we need j ≥ 5 , so we can only apply Hensel’s lemma at the modulus 243 level and above. But why are there dead ends when going up to 729?

Let’s look at what happens at the node a ≡ 4 (mod 243) . Here j = 5 and τ = 2 . Let a = 4 . We have f(4) = 243 and f′(4) = 9 , so we obtain t by solving the congruence t ≡ −1 (mod 3) . Taking t = −1 gives b = a + tp^{j−τ} = 4 − 3^{3} = −23 . Then f(b) = 729 = 3^{6} , and 6 = 2j − 2τ , as expected. To express the residue −23 as a positive number, we have 729 − 23 = 706 . This lies above 220 at the 243 level, which in turn lies above 58 at the 81 level. Or, we could have taken t = 2 to get 4 + 2 · 3^{3} = 58 , which of course lies over 58 at the 243 level. In fact, different choices of t in that same congruence class mod 3 can give any of the nine congruence classes modulo 729 on the left half of the diagram.

So the upshot of this example is that it’s better to look at solutions modulo p^{j−τ} instead of mod p^{j} . To do that, consider what happens when we let k = j − τ and restate Hensel’s lemma using k and τ instead of j and τ .

Theorem (Hensel’s lemma, new general version). Let f ∈ ℤ[x] , let p be a prime, and let a ∈ ℤ. Let τ be such that p^{τ} ∥ f′(a) , and assume that f(a) ≡ 0 (mod p^{k+τ}) for some k ≥ τ + 1 . Then: (a). there is an integer t, unique modulo p^{k−τ} , such that f(a + tp^{k}) ≡ 0 (mod p^{2k}) , and moreover t is the (unique) solution to the congruence

\frac{f′(a)}{p^{τ}}t ≡ −\frac{f(a)}{p^{k+τ}} (mod p^{k−τ}) ;

(b). if b ≡ a (mod p^{k}) , then f(b) ≡ f(a) (mod p^{k+τ}) ; and
(c). if b ≡ a (mod p^{k}) , then p^{τ} ∥ f′(b) .

Corollary. Let f ∈ ℤ[x] , let p be a prime, and let a ∈ ℤ. Let τ be such that p^{τ} ∥ f′(a) , and assume that f(a) ≡ 0 (mod p^{k+τ}) for some k ≥ τ + 1 . Then, for any α ≥ k there is an integer b, unique modulo p^{α}, such that b ≡ a (mod p^{k}) and f(b) ≡ 0 (mod p^{α+τ}) .