Hensel's Lemma - Hensel Lifting

Hensel Lifting

Using the lemma, one can "lift" a root r of the polynomial f mod pk to a new root s mod pk+1 (by taking m=1; taking larger m also works). The new root s is congruent to r mod p, so the new root also satisfies . So the lifting can be repeated, and starting from a solution r_k of we can derive a sequence of solutions r_k+1, r_k+2, ... of the same congruence for successively higher powers of p, provided for the initial root r_k.

What happens to this process if r is not a simple root mod p? If we have a root mod pk at which the derivative mod p is 0, then there is not a unique lifting of a root mod pk to a root mod pk+1: either there is no lifting to a root mod pk+1 or there are multiple choices:

if and then .

That is, for all integers t. Therefore if then there is no lifting of r to a root of f(x) mod pk+1, while if then every lifting of r to modulus pk+1 is a root of f(x) mod pk+1.

To see the difficulty that can arise in a concrete example, take p = 2, f(x) = x2 + 1, and r = 1. Then f(1) ≡ 0 mod 2 and f'(1) ≡ 0 mod 2. We have f(1) = 2 ≠ 0 mod 4 and no lifting of 1 to modulus 4 is a root of f(x) mod 4. On the other hand, if we take f(x) = x2 - 17 and then 1 is a root of f(x) mod 2 and for every positive integer k there is more than one lifting of 1 mod 2 to a root of f(x) mod 2k.