Hensel's Lemma

Hensel's lemma is a result that stipulates conditions for roots of polynomials modulo powers of primes to be "lifted" to roots modulo higher powers. The lifting method outlined in the proof is reminiscent of Newton's method for solving equations.

The lemma is useful for finding and classifying solutions of polynomial equations modulo powers of primes with a minimum of computational difficulty.

Find all the solutions to $x^2 \equiv 14$ mod $625$ .

Rather than searching mod $625$ , it is easier to build up the solution modulo smaller powers of $5$ . First, the square roots of $14$ mod $5$ are $2,3$ . Now try to find a solution $x = 2+5t$ mod $25:$

$\begin{aligned} (2+5t)^2 &\equiv 14 \pmod{25} \\ 4+20t &\equiv 14 \pmod{25} \\ 20t &\equiv 10 \pmod{25} \\ 4t &\equiv 2 \pmod{5}, \end{aligned}$

so $t \equiv 3$ mod $5$ ; so $x\equiv 17$ mod $25$ . Similarly, starting with $x=3+5t$ yields $t\equiv 1$ , so $x\equiv 8$ mod $25$ .

The key was that when we expanded the square, some of the terms vanished mod $25$ $($ in this case $25t^2)$ , so the resulting equation was linear in $t$ .

Next, try to lift these two solutions to solutions mod $625$ . Start with $x=17+25t:$

$\begin{aligned} (17+25t)^2 &\equiv 14 \pmod{625} \\ 289+850t &\equiv 14 \pmod{625} \\ 225t &\equiv 350 \pmod{625} \\ 9t &\equiv 14 \pmod{25}, \end{aligned}$

which gives $t \equiv 21$ mod $25$ , so $x\equiv 542$ . Similarly, lifting $x=8+25t$ yields $t\equiv 3$ mod $25$ , so $x \equiv 83$ . So there are two solutions, $x \equiv \pm 83$ mod $625$ . $_\square$

The process is straightforward, but it leads to several questions.

Are lifts always guaranteed to exist?
How many lifts can there be?
How many steps are required? $($ The modulus stepped from $5$ to $25$ to $625.)$
Does this work for any polynomial equation?

The answers to these questions are contained in the statement of Hensel's lemma.

Statement of the Lemma

Let $f(x)$ be a polynomial with integer coefficients. Let $k$ be a positive integer, and $r$ an integer such that $f(r) \equiv 0$ mod $p^k$ . Suppose $m \le k$ is a positive integer. Then if $f'(r) \not\equiv 0$ mod $p$ , there is an integer $s$ such that $f(s) \equiv 0$ mod $p^{k+m}$ and $s \equiv r$ mod $p^k$ . So $s$ is a "lifting" of $r$ to a root mod $p^{k+m}$ . Moreover, $s$ is unique mod $p^{k+m}$ .

The restriction that $m \le k$ is not particularly important in practice since the lemma can be applied recursively, to lift a solution to solutions modulo higher and higher powers of $p$ . That is, given $r$ as in the lemma, with the assumptions in the lemma, there is a unique solution $s_N$ to $f(x) \equiv 0$ mod $p^N$ such that $s_N \equiv r$ mod $p^k$ , for any $N \ge k$ .

Let $f(x) = x^3-3$ and $p = 5$ . Note that $f(2) = 0$ mod $5$ and $f'(2) = 3(2)^2 \ne 0$ mod $5$ . Then Hensel's lemma implies that there is a unique lift $s = 2+5t$ mod $25$ such that $f(s) \equiv 0$ mod $25$ . The proof supplies a formula for computing $s$ , but for now we can find $s = 12$ by inspection.

The process can be repeated: $s=12$ has a unique lift to a root mod $5^3$ , which turns out to be $87$ . The conditions of Hensel's lemma apply indefinitely, so there are unique lifts to a root mod $5^k$ for all $k$ .

We can write the solution mod $5^k$ as a series $2 + 2 \cdot 5 + 3 \cdot 5^2 + \cdots$ . In the right context, this can be viewed as a kind of power series.

Let $f(x) = x^3+2$ and $p = 3$ . Then $r = 1$ is the unique root of $f$ mod $3$ , but in fact there are no roots of $f$ mod $9$ . The conditions of Hensel's lemma are not satisfied because $f'(r) = 3r^2 \equiv 0$ mod $p$ .

Note that if $g(x) = x^3-1$ and $p = 3$ , the root $r= 1$ lifts to three different roots $1,4,7$ mod $9$ .

In general, if $f'(r) \equiv 0$ mod $p$ , the lifting behavior of roots congruent to $r$ is somewhat unpredictable. Sometimes there are no lifts and sometimes there are multiple lifts.

Let $f(x) = x^3-x-2$ . How many roots does $f(x)$ have mod $2^{10}?$

Both $0$ and $1$ are roots mod $2$ . Since $f'(0) \not\equiv 0$ mod $2$ , Hensel's lemma immediately implies a unique lift of this root modulo any higher power of $2$ .

On the other hand, $f'(1) \equiv 0$ mod $2$ . The next section will discuss what can be done in this situation in general, but for this particular polynomial it is enough to note that $f(1)$ and $f(3)$ are both $2$ mod $4$ , so there is no root mod $4$ that lifts $1$ mod $2$ , hence no such roots modulo any higher power.

So the answer is that there is exactly one root mod $2^{10}$ . $_\square$

Here is a problem where Hensel's lemma rules out all but a few possibilities, which should be checked in detail:

Let $N$ be the sum of all positive integers $q$ of the form $q=p^k$ with prime $p$ , such that for at least four different integer values of $x$ from $1$ to $q$ ,

$x^3-3x\equiv 123 \pmod{q}.$

What are the last 3 digits of $N?$

The correct answer is: 271

Denote $f(x)=x^3-3x-123.$ Because $deg(f)=3,$ if $q$ is a prime, then $f$ can have no more than three roots in the field of residues modulo $q$ . So $q=p^k$ for $k\geq 2.$

The main step in the argument, that allows to rule out most possibilities for $p$ , is the following lemma, which is a particular case of the famous Hensel's Lemma.

Lemma. Suppose $p$ is a prime, different from $3,$ $5,$ and $11$ . Suppose $x$ is an integer, such that $f(x)\equiv 0 \pmod {p^k}$ , for some $k\geq 1.$ Then there is exactly one residue $y$ modulo $p^{k+1}$ , congruent to $x$ modulo $p^k,$ such that $f(y)\equiv 0 \pmod {p^{k+1}}.$

Proof. Consider all residues $y$ modulo $p^{k+1}$ that are congruent to $x$ modulo $p^k.$ Each such $y$ can be written as $x+p^k z,$ where $z$ is an integer; the class of $y$ modulo $p^{k+1}$ is uniquely determined by the class of $z$ modulo $p$ . Plugging into $f(y)\equiv 0 \pmod {p^{k+1}}$ congruence that we need to solve, we get $(x+p^k z)^3-3(x+p^k z) -123 \equiv 0 \pmod {p^{k+1}}$ , which is equivalent to $(x^3-3x-123)+ 3x^2p^kz+3xp^{2k}z^2 + p^{3k} z^3 -3xp^k z \equiv 0 \pmod {p^{k+1}}$ Suppose $x^3-3x-123=p^k\cdot v.$ Because $k\geq 1,$ $2k$ and $3k$ are greater than or equal to $k+1,$ so the above can be rewritten as $p^k\cdot v + (3x^2-3)p^kz \equiv 0 \pmod {p^{k+1}}$ Dividing by $p^k$ , we get $3(x^2-1) z \equiv v \pmod p$ If $3(x^2-1)$ is not divisible by $p,$ this congruence has a unique solution modulo $p$ , and we are done. If $p\mid 3(x^2-1)$ , then either $p=3$ or $x\equiv \pm 1 \pmod p.$ Finally, if $f(1)\equiv 0 \pmod p$ , then $p\mid -125$ , so $p=5$ ; if $f(-1)\equiv 0 \pmod p$ , then $p\mid -121,$ so $p=11$ .

Remark. The above argument also works if $p$ is $5$ or $11$ and $x$ is not $1$ or $-1$ modulo $p.$ Indeed, in this case $3(x^2-1)\neq 0 \pmod p.$

Suppose for some $q=p^k,$ $p\neq 3, 5, 11,$ we have $f(x)\equiv 0 \pmod q$ for at least four residues modulo $q.$ Then by the above lemma the same must be true for $p^{k-1},$ $p^{k-2}, ... , p^1=p,$ which is impossible. Therefore, $p$ must be $3,$ $5,$ or $11.$

Case 1. $p=3.$ If $f(x)\equiv 0 \pmod 3,$ then $x^3 \equiv 0 \pmod 3,$ so $x=3y$ for some $y$ . But then $f(x)=27y^3-9y-123$ is never divisible by $9.$ So, no $q=3^k$ can satisfy the condition of the problem.

Case 2. $p=11.$ If $f(x)\equiv 0 \pmod {11},$ then, by direct check, either $x\equiv -1$ or $x\equiv 2$ modulo $11.$ For $x\equiv 2 \pmod {11},$ the Remark above implies that there is exactly one residue modulo $11^k,$ congruent to $2$ modulo $11,$ such that $f(x)\equiv 0 \pmod {11^k}.$

If $x\equiv -1 \pmod {11},$ then $x=-1+11y,$ so

$\begin{aligned} f(x) &=(-1+11y)^3-3(-1+11y)-123 \\ &= -121-3\cdot 11^2y^2+11^3y^3 \\ &=11^2(-1-3y^2+11y^3) \\ \end{aligned}$

So for every $y=1,2,...,11,$ we get $x$ such that $f(x)$ is divisible by $121,$ thus $q=121$ works. On the other hand, $11^2(-1-3y^2+11y^3)\equiv 0 \pmod {11^3}$ if and only if $-1-3y^2\equiv 0 \pmod{11},$ which never happens. So for any $k\geq 3$ there are no residues modulo $11^k$ , congruent to $-1$ modulo $11,$ such that $f(x)\equiv 0 \pmod {11^k}.$ Together with the sub-case $x\equiv 2 \pmod {11},$ considered above, we conclude that for $p=11$ there is one solution: $q=121.$

Case 3. $p=5.$ If $f(x)\equiv 0 \pmod {5},$ then, by direct check, either $x\equiv 1$ or $x\equiv 3$ modulo $5.$ For $x\equiv 3 \pmod 5,$ the Remark above implies that there is exactly one residue modulo $5^k,$ congruent to $3$ modulo $5,$ such that $f(x)\equiv 0 \pmod {5^k}.$

If $x\equiv 1 \pmod 5,$ then $x=1+5y,$ so $\begin{aligned} f(x) &=(1+5y)^3-3(1+5y)-123 \\ &=-125+3\cdot 25y^2+125y^3 \\ &=25(-5+3y^2+5y^3)\\ \end{aligned}$

So for every $y=0,1,2,3,4$ we get $x$ such that $f(x)$ is divisible by $25,$ thus $q=25$ works.

Note that $25(-5+3y^2+5y^3)\equiv 0 \pmod {5^3}$ if and only if $y\equiv 0 \pmod 5,$ that is $y=5z.$ In this case $x=1+25z$ and $f(x)=125(-1+15z^2+125z^3).$ This gives $5$ different residues $x$ modulo $5^3,$ so $q=125$ also works. On the other hand, $f(x)$ is never divisible by $5^4$ for $x\equiv 1 \pmod 5.$ So for any $k\geq 4$ there is only one residue $x$ modulo $5^k,$ such that $f(x)\equiv 0 \pmod {5^k},$ with $x\equiv 3 \pmod 5.$

Putting this all together, $q$ is $121,$ $25,$ or $125,$ so the answer is $121+25+125=271.$

Proof

The polynomial $f\big(r+p^kt\big)$ has a Taylor series expansion

$f\big(r+p^kt\big) = f(r) + f'(r) p^k t + \frac{f''(r)}{2!} p^{2k} t^2 + \cdots.$

Note that this is in fact a finite sum since $f$ is a polynomial, so there are no questions of convergence to worry about. Also note that $\frac{f^{(d)}(r)}{d!}$ is actually an integer for all $d$ $\big($ use the power rule and the fact that the binomial coefficient $\binom{s}{d}$ is always an integer $\big).$

Since $m\le k$ , all the terms but the first two vanish mod $p^{k+m}$ , so

$f\big(r+p^kt\big) \equiv f(r) +f'(r) p^k t \pmod{p^{k+m}}.$

Setting $f\big(r+p^kt\big) \equiv 0$ , we can solve for $t:$

$\begin{aligned} f(r) + f'(r) p^k t &\equiv 0 \pmod{p^{k+m}} \\\\ p^k t &\equiv -\frac{f(r)}{f'(r)} \pmod{p^{k+m}} \\\\ t &\equiv -\frac{ \hspace{1.5mm} \frac{f(r)}{p^k} \hspace{1.5mm} }{f'(r)} \pmod{p^m}, \end{aligned}$

which gives rise to a unique solution mod $p^{k+m}$ . Note that the numerator of this expression is an integer because $f(r)$ is divisible by $p^k$ , and the quotient makes sense because $f'(r)$ has a multiplicative inverse mod $p^m$ ; this is where the assumptions about $r$ are being used. $_\square$

A Stronger Version of the Lemma

There are stronger versions of Hensel's lemma that can be applied to cases when $f'(r) \equiv 0$ mod $p$ . Here is a more general statement:

Let $f(x)$ be a polynomial with integer coefficients. Let $k$ be a positive integer, and $r$ an integer such that $f(r) \equiv 0$ mod $p^k$ , $f(r) \not\equiv 0$ mod $p^{k+1}$ . Suppose $d < \frac k2$ is a positive integer. Then if $f'(r) \equiv 0$ mod $p^d$ but $f'(r) \not\equiv 0$ mod $p^{d+1}$ , then the following holds:

For every positive integer $N>k-d$ , there is a unique integer $s_N$ such that $f(s_N) \equiv 0$ mod $p^N$ and $s_N \equiv r$ mod $p^{k-d}$ . Also, $s_M \equiv s_N$ mod $p^{\text{min}(M,N)}$ .

Note that $s_N$ may not be congruent to $r$ mod $p^k$ ; that is, the original $r$ may not lift to a root modulo higher powers. But the theorem says that some $s_{k-d}$ congruent to $r$ mod $p^{k-d}$ will be liftable to a root modulo higher powers.

Let $f(x) = x^2-17$ and $r = 1$ . Then we can take $k = 4$ and $d = 1$ . Since $d<\frac k2$ as desired, the stronger form of Hensel's lemma applies. Even though $f(1) \equiv 0$ mod $2^4$ , there is no lift of $1$ to a root mod $2^5$ . But there is a lift of $9$ to a root mod $2^4, 2^5,$ and so on. $\big($ Similarly, note that $9$ is a root mod $2^6$ but there is no lift of $9$ to a root mod $2^7$ ; but there is a lift of 41... $\big)$

So the lifting process is more complicated and often requires some "backtracking" in practice when $d \ne 0$ .

The $p$ -adic Integers

Note that the formula for the lift $s$ of $r$ simplifies to

$s = r - \frac{f(r)}{f'(r)},$

which is exactly the formula employed in Newton's method for approximating real roots of polynomials. This is not a coincidence!

(The following paragraph can safely be skipped by anyone but the very curious.)

There is a set of $p$ -adic integers that is a sort of limit (an "inverse limit") of the sets ${\mathbb Z}_{p^k}$ . Elements of the set can be written as power series of the form $a_0 + a_1 p + a_2 p^2 + \cdots,$ where an appropriate topology is put on the set so that $p$ is "small" and higher powers of $p$ are "smaller" (in the same way that the powers of $x$ in typical power series are small). In this context, the process of Hensel lifting is in fact just Newton's method: solutions mod $p^k$ for higher powers of $p$ are better and better approximations to a $p$ -adic solution.

Contents