In mathematics, Hensel's lemma, also known as Hensel's lifting lemma, named after Kurt Hensel, is a result in modular arithmetic, stating that if a univariate polynomial has a simple root modulo a prime number p, then this root can be lifted to a unique root modulo any higher power of p. More generally, if a polynomial factors modulo p into two coprime polynomials, this factorization can be lifted to a factorization modulo any higher power of p (the case of roots corresponds to the case of degree 1 for one of the factors).

By passing to the "limit" (in fact this is an inverse limit) when the power of p tends to infinity, it follows that a root or a factorization modulo p can be lifted to a root or a factorization over the p-adic integers.

These results have been widely generalized, under the same name, to the case of polynomials over an arbitrary commutative ring, where p is replaced by an ideal, and "coprime polynomials" means "polynomials that generate an ideal containing 1".

Hensel's lemma is fundamental in p-adic analysis, a branch of analytic number theory.

The proof of Hensel's lemma is constructive, and leads to an efficient algorithm for Hensel lifting, which is fundamental for factoring polynomials, and gives the most efficient known algorithm for exact linear algebra over the rational numbers.

Hensel's original lemma concerns the relation between polynomial factorization over the integers and over the integers modulo a prime number p and its powers. It can be straightforwardly extended to the case where the integers are replaced by any commutative ring, and p is replaced by any maximal ideal (indeed, the maximal ideals of ${\displaystyle \mathbb {Z} }$ have the form ${\displaystyle p\mathbb {Z} ,}$ where p is a prime number).

Making this precise requires a generalization of the usual modular arithmetic, and so it is useful to define accurately the terminology that is commonly used in this context.

Let R be a commutative ring, and I an ideal of R. Reduction modulo I refers to the replacement of every element of R by its image under the canonical map ${\displaystyle R\to R/I.}$ For example, if ${\displaystyle f\in R[X]}$ is a polynomial with coefficients in R, its reduction modulo I, denoted ${\displaystyle f{\bmod {I}},}$ is the polynomial in ${\displaystyle (R/I)[X]=R[X]/IR[X]}$ obtained by replacing the coefficients of f by their image in ${\displaystyle R/I.}$ Two polynomials f and g in ${\displaystyle R[X]}$ are congruent modulo I, denoted ${\textstyle f\equiv g{\pmod {I}}}$ if they have the same coefficients modulo I, that is if ${\displaystyle f-g\in IR[X].}$ If ${\displaystyle h\in R[X],}$ a factorization of h modulo I consists in two (or more) polynomials f, g in ${\displaystyle R[X]}$ such that ${\textstyle h\equiv fg{\pmod {I}}.}$

The lifting process is the inverse of reduction. That is, given objects depending on elements of ${\displaystyle R/I,}$ the lifting process replaces these elements by elements of ${\displaystyle R}$ (or of ${\displaystyle R/I^{k}}$ for some k > 1) that maps to them in a way that keeps the properties of the objects.

For example, given a polynomial ${\displaystyle h\in R[X]}$ and a factorization modulo I expressed as ${\textstyle h\equiv fg{\pmod {I}},}$ lifting this factorization modulo ${\displaystyle I^{k}}$ consists of finding polynomials ${\displaystyle f',g'\in R[X]}$ such that ${\textstyle f'\equiv f{\pmod {I}},}$ ${\textstyle g'\equiv g{\pmod {I}},}$ and ${\textstyle h\equiv f'g'{\pmod {I^{k}}}.}$ Hensel's lemma asserts that such a lifting is always possible under mild conditions; see next section.

Originally, Hensel's lemma was stated (and proved) for lifting a factorization modulo a prime number p of a polynomial over the integers to a factorization modulo any power of p and to a factorization over the p-adic integers. This can be generalized easily, with the same proof to the case where the integers are replaced by any commutative ring, the prime number is replaced by a maximal ideal, and the p-adic integers are replaced by the completion with respect to the maximal ideal. It is this generalization, which is also widely used, that is presented here.

Let ${\displaystyle {\mathfrak {m}}}$ be a maximal ideal of a commutative ring R, and

${\displaystyle h=\alpha _{0}X^{n}+\cdots +\alpha _{n-1}X+\alpha _{n}}$

be a polynomial in ${\displaystyle R[X]}$ with a leading coefficient ${\displaystyle \alpha _{0}}$ not in ${\displaystyle {\mathfrak {m}}.}$

Since ${\displaystyle {\mathfrak {m}}}$ is a maximal ideal, the quotient ring ${\displaystyle R/{\mathfrak {m}}}$ is a field, and ${\displaystyle (R/{\mathfrak {m}})[X]}$ is a principal ideal domain, and, in particular, a unique factorization domain, which means that every nonzero polynomial in ${\displaystyle (R/{\mathfrak {m}})[X]}$ can be factorized in a unique way as the product of a nonzero element of ${\displaystyle (R/{\mathfrak {m}})}$ and irreducible polynomials that are monic (that is, their leading coefficients are 1).

Hensel's lemma asserts that every factorization of h modulo ${\displaystyle {\mathfrak {m}}}$ into coprime polynomials can be lifted in a unique way into a factorization modulo ${\displaystyle {\mathfrak {m}}^{k}}$ for every k.

More precisely, with the above hypotheses, if ${\textstyle h\equiv \alpha _{0}fg{\pmod {\mathfrak {m}}},}$ where f and g are monic and coprime modulo ${\displaystyle {\mathfrak {m}},}$ then, for every positive integer k there are monic polynomials ${\displaystyle f_{k}}$ and ${\displaystyle g_{k}}$ such that

${\displaystyle {\begin{aligned}h&\equiv \alpha _{0}f_{k}g_{k}{\pmod {{\mathfrak {m}}^{k}}},\\f_{k}&\equiv f{\pmod {\mathfrak {m}}},\\g_{k}&\equiv g{\pmod {\mathfrak {m}}},\end{aligned}}}$

and ${\displaystyle f_{k}}$ and ${\displaystyle g_{k}}$ are unique (with these properties) modulo ${\displaystyle {\mathfrak {m}}^{k}.}$

An important special case is when ${\displaystyle f=X-r.}$ In this case the coprimality hypothesis means that r is a simple root of ${\displaystyle h{\bmod {\mathfrak {m}}}.}$ This gives the following special case of Hensel's lemma, which is often called also Hensel's lemma.

With above hypotheses and notations, if r is a simple root of ${\displaystyle h{\bmod {\mathfrak {m}}},}$ then r can be lifted in a unique way to a simple root of ${\displaystyle h{\bmod {{\mathfrak {m}}^{n}}}}$ for every positive integer n. Explicitly, for every positive integer n, there is a unique ${\displaystyle r_{n}\in R/{\mathfrak {m}}^{n}}$ such that ${\textstyle r_{n}\equiv r{\pmod {\mathfrak {m}}}}$ and ${\displaystyle r_{n}}$ is a simple root of ${\displaystyle h{\bmod {\mathfrak {m}}}^{n}.}$

The fact that one can lift to ${\displaystyle R/{\mathfrak {m}}^{n}}$ for every positive integer n suggests to "pass to the limit" when n tends to the infinity. This was one of the main motivations for introducing p-adic integers.

Given a maximal ideal ${\displaystyle {\mathfrak {m}}}$ of a commutative ring R, the powers of ${\displaystyle {\mathfrak {m}}}$ form a basis of open neighborhoods for a topology on R, which is called the ${\displaystyle {\mathfrak {m}}}$-adic topology. The completion of this topology can be identified with the completion of the local ring ${\displaystyle R_{\mathfrak {m}},}$ and with the inverse limit ${\displaystyle \lim _{\leftarrow }R/{\mathfrak {m}}^{n}.}$ This completion is a complete local ring, generally denoted ${\displaystyle {\widehat {R}}_{\mathfrak {m}}.}$ When R is the ring of the integers, and ${\displaystyle {\mathfrak {m}}=p\mathbb {Z} ,}$ where p is a prime number, this completion is the ring of p-adic integers ${\displaystyle \mathbb {Z} _{p}.}$

The definition of the completion as an inverse limit, and the above statement of Hensel's lemma imply that every factorization into pairwise coprime polynomials modulo ${\displaystyle {\mathfrak {m}}}$ of a polynomial ${\displaystyle h\in R[X]}$ can be uniquely lifted to a factorization of the image of h in ${\displaystyle {\widehat {R}}_{\mathfrak {m}}[X].}$ Similarly, every simple root of h modulo ${\displaystyle {\mathfrak {m}}}$ can be lifted to a simple root of the image of h in ${\displaystyle {\widehat {R}}_{\mathfrak {m}}[X].}$

Hensel's lemma is generally proved incrementally by lifting a factorization over ${\displaystyle R/{\mathfrak {m}}^{n}}$ to either a factorization over ${\displaystyle R/{\mathfrak {m}}^{n+1}}$ (Linear lifting), or a factorization over ${\displaystyle R/{\mathfrak {m}}^{2n}}$ (Quadratic lifting).

The main ingredient of the proof is that coprime polynomials over a field satisfy Bézout's identity. That is, if f and g are coprime univariate polynomials over a field (here ${\displaystyle R/{\mathfrak {m}}}$), there are polynomials a and b such that ${\displaystyle \deg a<\deg g,}$ ${\displaystyle \deg b<\deg f,}$ and

${\displaystyle af+bg=1.}$

Bézout's identity allows defining coprime polynomials and proving Hensel's lemma, even if the ideal ${\displaystyle {\mathfrak {m}}}$ is not maximal. Therefore, in the following proofs, one starts from a commutative ring R, an ideal I, a polynomial ${\displaystyle h\in R[X]}$ that has a leading coefficient that is invertible modulo I (that is its image in ${\displaystyle R/I}$ is a unit in ${\displaystyle R/I}$), and factorization of h modulo I or modulo a power of I, such that the factors satisfy a Bézout's identity modulo I. In these proofs, ${\textstyle A\equiv B{\pmod {I}}}$ means ${\displaystyle A-B\in IR[X].}$

Let I be an ideal of a commutative ring R, and ${\displaystyle h\in R[X]}$ be a univariate polynomial with coefficients in R that has a leading coefficient ${\displaystyle \alpha }$ that is invertible modulo I (that is, the image of ${\displaystyle \alpha }$ in ${\displaystyle R/I}$ is a unit in ${\displaystyle R/I}$).

Suppose that for some positive integer k there is a factorization

${\displaystyle h\equiv \alpha fg{\pmod {I^{k}}},}$

such that f and g are monic polynomials that are coprime modulo I, in the sense that there exist ${\displaystyle a,b\in R[X],}$ such that ${\textstyle af+bg\equiv 1{\pmod {I}}.}$ Then, there are polynomials ${\displaystyle \delta _{f},\delta _{g}\in I^{k}R[X],}$ such that ${\displaystyle \deg \delta _{f}<\deg f,}$ ${\displaystyle \deg \delta _{g}<\deg g,}$ and

${\displaystyle h\equiv \alpha (f+\delta _{f})(g+\delta _{g}){\pmod {I^{k+1}}}.}$

Under these conditions, ${\displaystyle \delta _{f}}$ and ${\displaystyle \delta _{g}}$ are unique modulo ${\displaystyle I^{k+1}R[X].}$

Moreover, ${\displaystyle f+\delta _{f}}$ and ${\displaystyle g+\delta _{g}}$ satisfy the same Bézout's identity as f and g, that is, $${\displaystyle a(f+\delta _{f})+b(g+\delta _{g})\equiv 1{\pmod {I}}.}$$ This follows immediately from the preceding assertions, but is needed to apply iteratively the result with increasing values of k.

The proof that follows is written for computing ${\displaystyle \delta _{f}}$ and ${\displaystyle \delta _{g}}$ by using only polynomials with coefficients in ${\displaystyle R/I}$ or ${\displaystyle I^{k}/I^{k+1}.}$ When ${\displaystyle R=\mathbb {Z} }$ and ${\displaystyle I=p\mathbb {Z} ,}$ this allows manipulating only integers modulo p.

Proof: By hypothesis, ${\displaystyle \alpha }$ is invertible modulo I. This means that there exists ${\displaystyle \beta \in R}$ and ${\displaystyle \gamma \in IR[X]}$ such that ${\displaystyle \alpha \beta =1-\gamma .}$

Let ${\displaystyle \delta _{h}\in I^{k}R[X],}$ of degree less than ${\displaystyle \deg h,}$ such that

${\displaystyle \delta _{h}\equiv h-\alpha fg{\pmod {I^{k+1}}}.}$

(One may choose ${\displaystyle \delta _{h}=h-\alpha fg,}$ but other choices may lead to simpler computations. For example, if ${\displaystyle R=\mathbb {Z} }$ and ${\displaystyle I=p\mathbb {Z} ,}$ it is possible and better to choose ${\displaystyle \delta _{h}=p^{k}\delta '_{h}}$ where the coefficients of ${\displaystyle \delta '_{h}}$ are integers in the interval ${\displaystyle [0,p-1].}$)

As g is monic, the Euclidean division of ${\displaystyle a\delta _{h}}$ by g is defined, and provides q and c such that ${\displaystyle a\delta _{h}=qg+c,}$ and ${\displaystyle \deg c<\deg g.}$ Moreover, both q and c are in ${\displaystyle I^{k}R[X].}$ Similarly, let ${\displaystyle b\delta _{h}=q'f+d,}$ with ${\displaystyle \deg d<\deg f,}$ and ${\displaystyle q',d\in I^{k}R[X].}$

One has ${\displaystyle q+q'\in I^{k+1}R[X].}$ Indeed, one has

${\displaystyle fc+gd=af\delta _{h}+bg\delta _{h}-fg(q+q')\equiv \delta _{h}-fg(q+q'){\pmod {I^{k+1}}}.}$

As ${\displaystyle fg}$ is monic, the degree modulo ${\displaystyle I^{k+1}}$ of ${\displaystyle fg(q+q')}$ can be less than ${\displaystyle \deg fg}$ only if ${\displaystyle q+q'\in I^{k+1}R[X].}$

Thus, considering congruences modulo ${\displaystyle I^{k+1},}$ one has

${\displaystyle {\begin{aligned}\alpha (f+\beta d)&(g+\beta c)-h\\&\equiv \alpha fg-h+\alpha \beta (f(a\delta _{h}-qg)+g(b\delta _{h}-q'f))\\&\equiv \delta _{h}(-1+\alpha \beta (af+bg))-\alpha \beta fg(q+q')\\&\equiv 0{\pmod {I^{k+1}}}.\end{aligned}}}$

So, the existence assertion is verified with

${\displaystyle \delta _{f}=\beta d,\qquad \delta _{g}=\beta c.}$

Let R, I, h and ${\displaystyle \alpha }$ as a in the preceding section. Let

${\displaystyle h\equiv \alpha fg{\pmod {I}}}$

be a factorization into coprime polynomials (in the above sense), such ${\displaystyle \deg f_{0}+\deg g_{0}=\deg h.}$ The application of linear lifting for ${\displaystyle k=1,2,\ldots ,n-1\ldots ,}$ shows the existence of ${\displaystyle \delta _{f}}$ and ${\displaystyle \delta _{g}}$ such that ${\displaystyle \deg \delta _{f}<\deg f,}$ ${\displaystyle \deg \delta _{g}<\deg g,}$ and

${\displaystyle h\equiv \alpha (f+\delta _{f})(g+\delta _{g}){\pmod {I^{n}}}.}$

The polynomials ${\displaystyle \delta _{f}}$ and ${\displaystyle \delta _{g}}$ are uniquely defined modulo ${\displaystyle I^{n}.}$ This means that, if another pair ${\displaystyle (\delta '_{f},\delta '_{g})}$ satisfies the same conditions, then one has

${\displaystyle \delta '_{f}\equiv \delta _{f}{\pmod {I^{n}}}\qquad {\text{and}}\qquad \delta '_{g}\equiv \delta _{g}{\pmod {I^{n}}}.}$

Proof: Since a congruence modulo ${\displaystyle I^{n}}$ implies the same concruence modulo ${\displaystyle I^{n-1},}$ one can proceed by induction and suppose that the uniqueness has been proved for n − 1, the case n = 0 being trivial. That is, one can suppose that

${\displaystyle \delta _{f}-\delta '_{f}\in I^{n-1}R[X]\qquad {\text{and}}\qquad \delta _{g}-\delta '_{g}\in I^{n-1}R[X].}$

By hypothesis, has

${\displaystyle h\equiv \alpha (f+\delta _{f})(g+\delta _{g})\equiv \alpha (f+\delta '_{f})(g+\delta '_{g}){\pmod {I^{n}}},}$

and thus

${\displaystyle {\begin{aligned}\alpha (f+\delta _{f})(g+\delta _{g})&-\alpha (f+\delta '_{f})(g+\delta '_{g})\\&=\alpha (f(\delta _{g}-\delta '_{g})+g(\delta _{f}-\delta '_{f}))+\alpha (\delta _{f}(\delta _{g}-\delta '_{g})-\delta _{g}(\delta _{f}-\delta '_{f}))\in I^{n}R[X].\end{aligned}}}$

By induction hypothesis, the second term of the latter sum belongs to ${\displaystyle I^{n},}$ and the same is thus true for the first term. As ${\displaystyle \alpha }$ is invertible modulo I, there exist ${\displaystyle \beta \in R}$ and ${\displaystyle \gamma \in I}$ such that ${\displaystyle \alpha \beta =1+\gamma .}$ Thus

${\displaystyle {\begin{aligned}f(\delta _{g}-\delta '_{g})&+g(\delta _{f}-\delta '_{f})\\&=\alpha \beta (f(\delta _{g}-\delta '_{g})+g(\delta _{f}-\delta '_{f}))-\gamma (f(\delta _{g}-\delta '_{g})+g(\delta _{f}-\delta '_{f}))\in I^{n}R[X],\end{aligned}}}$

using the induction hypothesis again.

The coprimality modulo I implies the existence of ${\displaystyle a,b\in R[X]}$ such that ${\textstyle 1\equiv af+bg{\pmod {I}}.}$ Using the induction hypothesis once more, one gets

${\displaystyle {\begin{aligned}\delta _{g}-\delta '_{g}&\equiv (af+bg)(\delta _{g}-\delta '_{g})\\&\equiv g(b(\delta _{g}-\delta '_{g})-a(\delta _{f}-\delta '_{f})){\pmod {I^{n}}}.\end{aligned}}}$

Thus one has a polynomial of degree less than ${\displaystyle \deg g}$ that is congruent modulo ${\displaystyle I^{n}}$ to the product of the monic polynomial g and another polynomial w. This is possible only if ${\displaystyle w\in I^{n}R[X],}$ and implies ${\displaystyle \delta _{g}-\delta '_{g}\in I^{n}R[X].}$ Similarly, ${\displaystyle \delta _{f}-\delta '_{f}}$ is also in ${\displaystyle I^{n}R[X],}$ and this proves the uniqueness.

Linear lifting allows lifting a factorization modulo ${\displaystyle I^{n}}$ to a factorization modulo ${\displaystyle I^{n+1}.}$ Quadratic lifting allows lifting directly to a factorization modulo ${\displaystyle I^{2n},}$ at the cost of lifting also the Bézout's identity and of computing modulo ${\displaystyle I^{n}}$ instead of modulo I (if one uses the above description of linear lifting).

For lifting up to modulo ${\displaystyle I^{N}}$ for large N one can use either method. If, say, ${\displaystyle N=2^{k},}$ a factorization modulo ${\displaystyle I^{N}}$ requires N − 1 steps of linear lifting or only k − 1 steps of quadratic lifting. However, in the latter case the size of the coefficients that have to be manipulated increase during the computation. This implies that the best lifting method depends on the context (value of N, nature of R, multiplication algorithm that is used, hardware specificities, etc.).^{[citation needed]}

Quadratic lifting is based on the following property.

Suppose that for some positive integer k there is a factorization

${\displaystyle h\equiv \alpha fg{\pmod {I^{k}}},}$

such that f and g are monic polynomials that are coprime modulo I, in the sense that there exist ${\displaystyle a,b\in R[X],}$ such that ${\textstyle af+bg\equiv 1{\pmod {I^{k}}}.}$ Then, there are polynomials ${\displaystyle \delta _{f},\delta _{g}\in I^{k}R[X],}$ such that ${\displaystyle \deg \delta _{f}<\deg f,}$ ${\displaystyle \deg \delta _{g}<\deg g,}$ and

${\displaystyle h\equiv \alpha (f+\delta _{f})(g+\delta _{g}){\pmod {I^{2k}}}.}$

Moreover, ${\displaystyle f+\delta _{f}}$ and ${\displaystyle g+\delta _{g}}$ satisfy a Bézout's identity of the form

${\displaystyle (a+\delta _{a})(f+\delta _{f})+(b+\delta _{b})(g+\delta _{g})\equiv 1{\pmod {I^{2k}}}.}$

(This is required for allowing iterations of quadratic lifting.)

Proof: The first assertion is exactly that of linear lifting applied with k = 1 to the ideal ${\displaystyle I^{k}}$ instead of ${\displaystyle I.}$

Let ${\displaystyle \alpha =af+bg-1\in I^{k}R[X].}$ One has

${\displaystyle a(f+\delta _{f})+b(g+\delta _{g})=1+\Delta ,}$

where

${\displaystyle \Delta =\alpha +a\delta _{f}+b\delta _{g}\in I^{k}R[X].}$

Setting ${\displaystyle \delta _{a}=-a\Delta }$ and ${\displaystyle \delta _{b}=-b\Delta ,}$ one gets

${\displaystyle (a+\delta _{a})(f+\delta _{f})+(b+\delta _{b})(g+\delta _{g})=1-\Delta ^{2}\in I^{2k}R[X],}$

which proves the second assertion.

Let ${\displaystyle f(X)=X^{6}-2\in \mathbb {Q} [X].}$

Modulo 2, Hensel's lemma cannot be applied since the reduction of ${\displaystyle f(X)}$ modulo 2 is simply^{[1]pg 15-16}

${\displaystyle {\bar {f}}(X)=X^{6}-{\overline {2}}=X^{6}}$

with 6 factors ${\displaystyle X}$ not being relatively prime to each other. By Eisenstein's criterion, however, one can conclude that the polynomial ${\displaystyle f(X)}$ is irreducible in ${\displaystyle \mathbb {Q} _{2}[X].}$
Over ${\displaystyle k=\mathbb {F} _{7}}$, on the other hand, one has

${\displaystyle {\bar {f}}(X)=X^{6}-{\overline {2}}=X^{6}-{\overline {16}}=(X^{3}-{\overline {4}})\;(X^{3}+{\overline {4}})}$

where ${\displaystyle 4}$ is the square root of 2 in ${\displaystyle \mathbb {F} _{7}}$. As 4 is not a cube in ${\displaystyle \mathbb {F} _{7},}$ these two factors are irreducible over ${\displaystyle \mathbb {F} _{7}}$. Hence the complete factorization of ${\displaystyle X^{6}-2}$ in ${\displaystyle \mathbb {Z} _{7}[X]}$ and ${\displaystyle \mathbb {Q} _{7}[X]}$ is

${\displaystyle f(X)=X^{6}-2=(X^{3}-\alpha )\;(X^{3}+\alpha ),}$

where ${\displaystyle \alpha =\ldots 450\,454_{7}}$ is a square root of 2 in ${\displaystyle \mathbb {Z} _{7}}$ that can be obtained by lifting the above factorization.
Finally, in ${\displaystyle \mathbb {F} _{727}[X]}$ the polynomial splits into

${\displaystyle {\bar {f}}(X)=X^{6}-{\overline {2}}=(X-{\overline {3}})\;(X-{\overline {116}})\;(X-{\overline {119}})\;(X-{\overline {608}})\;(X-{\overline {611}})\;(X-{\overline {724}})}$

with all factors relatively prime to each other, so that in ${\displaystyle \mathbb {Z} _{727}[X]}$ and ${\displaystyle \mathbb {Q} _{727}[X]}$ there are 6 factors ${\displaystyle X-\beta }$ with the (non-rational) 727-adic integers

${\displaystyle \beta =\left\{{\begin{array}{rrr}3\;+&\!\!\!545\cdot 727\;+&\!\!\!537\cdot 727^{2}\,+&\!\!\!161\cdot 727^{3}+\ldots \\116\;+&\!\!\!48\cdot 727\;+&\!\!\!130\cdot 727^{2}\,+&\!\!\!498\cdot 727^{3}+\ldots \\119\;+&\!\!\!593\cdot 727\;+&\!\!\!667\cdot 727^{2}\,+&\!\!\!659\cdot 727^{3}+\ldots \\608\;+&\!\!\!133\cdot 727\;+&\!\!\!59\cdot 727^{2}\,+&\!\!\!67\cdot 727^{3}+\ldots \\611\;+&\!\!\!678\cdot 727\;+&\!\!\!596\cdot 727^{2}\,+&\!\!\!228\cdot 727^{3}+\ldots \\724\;+&\!\!\!181\cdot 727\;+&\!\!\!189\cdot 727^{2}\,+&\!\!\!565\cdot 727^{3}+\ldots \end{array}}\right.}$

Let ${\displaystyle f(x)}$ be a polynomial with integer (or p-adic integer) coefficients, and let m, k be positive integers such that m ≤ k. If r is an integer such that

${\displaystyle f(r)\equiv 0{\bmod {p}}^{k}\quad {\text{and}}\quad f'(r)\not \equiv 0{\bmod {p}}}$

then, for every ${\displaystyle m>0}$ there exists an integer s such that

${\displaystyle f(s)\equiv 0{\bmod {p}}^{k+m}\quad {\text{and}}\quad r\equiv s{\bmod {p}}^{k}.}$

Furthermore, this s is unique modulo p^k+m, and can be computed explicitly as the integer such that

${\displaystyle s=r-f(r)\cdot a,}$

where ${\displaystyle a}$ is an integer satisfying

${\displaystyle a\equiv [f'(r)]^{-1}{\bmod {p}}^{m}.}$

Note that ${\displaystyle f(r)\equiv 0{\bmod {p}}^{k}}$ so that the condition ${\displaystyle s\equiv r{\bmod {p}}^{k}}$ is met. As an aside, if ${\displaystyle f'(r)\equiv 0{\bmod {p}}}$, then 0, 1, or several s may exist (see Hensel Lifting below).

We use the Taylor expansion of f around r to write:

${\displaystyle f(s)=\sum _{n=0}^{N}c_{n}(s-r)^{n},\qquad c_{n}=f^{(n)}(r)/n!.}$

From ${\displaystyle r\equiv s{\bmod {p}}^{k},}$ we see that s − r = tp^k for some integer t. Let