Inmathematics,Hensel's lemma, also known asHensel's lifting lemma, named afterKurt Hensel, is a result inmodular arithmetic, stating that if aunivariate polynomial has asimple root modulo aprime numberp, then this root can belifted to a unique root modulo any higher power ofp. More generally, if a polynomial factors modulop into twocoprime polynomials, this factorization can be lifted to a factorization modulo any higher power ofp (the case of roots corresponds to the case of degree1 for one of the factors).

By passing to the "limit" (in fact this is aninverse limit) when the power ofp tends to infinity, it follows that a root or a factorization modulop can be lifted to a root or a factorization over thep-adic integers.

These results have been widely generalized, under the same name, to the case of polynomials over an arbitrarycommutative ring, wherep is replaced by anideal, and "coprime polynomials" means "polynomials that generate an ideal containing1".

Hensel's lemma is fundamental inp-adic analysis, a branch ofanalytic number theory.

The proof of Hensel's lemma isconstructive, and leads to an efficient algorithm forHensel lifting, which is fundamental forfactoring polynomials, and gives the most efficient known algorithm for exactlinear algebra over therational numbers.

Hensel's original lemma concerns the relation betweenpolynomial factorization over the integers and over the integersmodulo aprime numberp and its powers. It can be straightforwardly extended to the case where the integers are replaced by anycommutative ring, andp is replaced by anymaximal ideal (indeed, the maximal ideals of${\displaystyle \mathbb{Z}}$ have the form${\displaystyle p\mathbb{Z},}$ wherep is a prime number).

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

LetR be a commutative ring, andI anideal ofR.Reduction moduloI refers to the replacement of every element ofR by its image under thecanonical map${\displaystyle R\to R/I.}$ For example, if${\displaystyle f\in R[X]}$ is apolynomial with coefficients inR, its reduction moduloI, denoted${\displaystyle fmodI,}$ is the polynomial in${\displaystyle (R/I)[X]=R[X]/IR[X]}$ obtained by replacing the coefficients off by their image in${\displaystyle R/I.}$ Two polynomialsf andg in${\displaystyle R[X]}$ arecongruent moduloI, denoted$f\equiv g(\mathrm{mod}I)$ if they have the same coefficients moduloI, that is if${\displaystyle f-g\in IR[X].}$ If${\displaystyle h\in R[X],}$ a factorization ofh moduloI consists in two (or more) polynomialsf, g in${\displaystyle R[X]}$ such that$h\equiv fg(\mathrm{mod}I).$

Thelifting process is the inverse of reduction. That is, givenobjects 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 somek > 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 moduloI expressed as$h\equiv fg(\mathrm{mod}I),$ lifting this factorization modulo${\displaystyle I^k}$ consists of finding polynomials${\displaystyle f^{\prime },g^{\prime }\in R[X]}$ such that$f^{\prime }\equiv f(\mathrm{mod}I),$$g^{\prime }\equiv g(\mathrm{mod}I),$ and$h\equiv f^{\prime }{g}^{\prime }(\mathrm{mod}{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 afactorization modulo aprime numberp of a polynomial over the integers to a factorization modulo any power ofp and to a factorization over thep-adic integers. This can be generalized easily, with the same proof to the case where the integers are replaced by anycommutative ring, the prime number is replaced by amaximal ideal, and thep-adic integers are replaced by thecompletion 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 ringR, and

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

be apolynomial in${\displaystyle R[X]}$ with aleading coefficient${\displaystyle {\alpha }_0}$ not in${\displaystyle \mathfrak{m}.}$

Since${\displaystyle \mathfrak{m}}$ is a maximal ideal, thequotient ring${\displaystyle R/\mathfrak{m}}$ is afield, and${\displaystyle (R/\mathfrak{m})[X]}$ is aprincipal ideal domain, and, in particular, aunique 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})}$ andirreducible polynomials that aremonic (that is, their leading coefficients are 1).

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

More precisely, with the above hypotheses, if$h\equiv {\alpha }_{0}fg(\mathrm{mod}\mathfrak{m}),$ wheref andg are monic andcoprime modulo${\displaystyle \mathfrak{m},}$ then, for every positive integerk there are monic polynomials${\displaystyle f_k}$ and${\displaystyle g_k}$ such that

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 thatr is asimple root of${\displaystyle hmod\mathfrak{m}.}$ This gives the following special case of Hensel's lemma, which is often also called Hensel's lemma.

With above hypotheses and notations, ifr is a simple root of${\displaystyle hmod\mathfrak{m},}$ thenr can be lifted in a unique way to a simple root of${\displaystyle hmod{\mathfrak{m}}^n}$ for every positive integern. Explicitly, for every positive integern, there is a unique${\displaystyle r_n\in R/{\mathfrak{m}}^n}$ such that$r_n\equiv r(\mathrm{mod}\mathfrak{m})$ and${\displaystyle r_n}$ is a simple root of${\displaystyle h{mod\mathfrak{m}}^n.}$

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

Given a maximal ideal${\displaystyle \mathfrak{m}}$ of a commutative ringR, the powers of${\displaystyle \mathfrak{m}}$ form a basis ofopen neighborhoods for atopology onR, which is called the${\displaystyle \mathfrak{m}}$-adic topology. Thecompletion of this topology can be identified with thecompletion of the local ring${\displaystyle R_{\mathfrak{m}},}$ and with theinverse limit${\displaystyle \underleftarrow{lim}R/{\mathfrak{m}}^n.}$ This completion is acomplete local ring, generally denoted${\displaystyle {\hat{R}}_{\mathfrak{m}}.}$ WhenR is the ring of the integers, and${\displaystyle \mathfrak{m}=p\mathbb{Z},}$ wherep is a prime number, this completion is the ring ofp-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 ofh in${\displaystyle {\hat{R}}_{\mathfrak{m}}[X].}$ Similarly, every simple root ofh modulo${\displaystyle \mathfrak{m}}$ can be lifted to a simple root of the image ofh in${\displaystyle {\hat{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 thatcoprime polynomials over a field satisfyBézout's identity. That is, iff andg are coprimeunivariate polynomials over afield (here${\displaystyle R/\mathfrak{m}}$), there are polynomialsa andb such that 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 ringR, anidealI, a polynomial${\displaystyle h\in R[X]}$ that has a leading coefficient that is invertible moduloI (that is its image in${\displaystyle R/I}$ is aunit in${\displaystyle R/I}$), andfactorization ofh moduloI or modulo a power ofI, such that the factors satisfy a Bézout's identity moduloI. In these proofs,$A\equiv B(\mathrm{mod}I)$ means${\displaystyle A-B\in IR[X].}$

LetI be anideal of acommutative ringR, and${\displaystyle h\in R[X]}$ be aunivariate polynomial with coefficients inR that has aleading coefficient${\displaystyle \alpha }$ that is invertible moduloI (that is, the image of${\displaystyle \alpha }$ in${\displaystyle R/I}$ is aunit in${\displaystyle R/I}$).

Suppose that for some positive integerk there is a factorization

${\displaystyle h\equiv \alpha fg(\mathrm{mod}{I}^k),}$

such thatf andg aremonic polynomials that are coprime moduloI, in the sense that there exist${\displaystyle a,b\in R[X],}$ such that$af+bg\equiv 1(\mathrm{mod}I).$ Then, there are polynomials${\displaystyle {\delta }_f,{\delta }_g\in I^{k}R[X],}$ such that and

${\displaystyle h\equiv \alpha (f+{\delta }_f)(g+{\delta }_g)(\mathrm{mod}{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 asf andg, that is,$${\displaystyle a(f+{\delta }_f)+b(g+{\delta }_g)\equiv 1(\mathrm{mod}I).}$$ This follows immediately from the preceding assertions, but is needed to apply iteratively the result with increasing values ofk.

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 modulop.

Proof:By hypothesis,${\displaystyle \alpha }$ is invertible moduloI. 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 \mathrm{deg}h,}$ such that

${\displaystyle {\delta }_h\equiv h-\alpha fg(\mathrm{mod}{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^{\prime }}$ where the coefficients of${\displaystyle {\delta }_h^{\prime }}$ are integers in the interval${\displaystyle [0,p-1].}$)

Asg is monic, theEuclidean division of${\displaystyle a{\delta }_h}$ byg is defined, and providesq andc such that${\displaystyle a{\delta }_h=qg+c,}$ and Moreover, bothq andc are in${\displaystyle I^{k}R[X].}$ Similarly, let${\displaystyle b{\delta }_h=q^{\prime }f+d,}$ with and${\displaystyle q^{\prime },d\in I^{k}R[X].}$

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

${\displaystyle fc+gd=af{\delta }_h+bg{\delta }_h-fg(q+q^{\prime })\equiv {\delta }_h-fg(q+q^{\prime })(\mathrm{mod}{I}^{k+1}).}$

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

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

So, the existence assertion is verified with

${\displaystyle {\delta }_f=\beta d,{\delta }_g=\beta c.}$

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

${\displaystyle h\equiv \alpha fg(\mathrm{mod}I)}$

be a factorization into coprime polynomials (in the above sense), such${\displaystyle \mathrm{deg}{f}_0+\mathrm{deg}{g}_0=\mathrm{deg}h.}$ The application of linear lifting for${\displaystyle k=1,2,\dots ,n-1\dots ,}$ shows the existence of${\displaystyle {\delta }_f}$ and${\displaystyle {\delta }_g}$ such that and

${\displaystyle h\equiv \alpha (f+{\delta }_f)(g+{\delta }_g)(\mathrm{mod}{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^{\prime },{\delta }_g^{\prime })}$ satisfies the same conditions, then one has

${\displaystyle {\delta }_f^{\prime }\equiv {\delta }_f(\mathrm{mod}{I}^n)\text{and}{\delta }_g^{\prime }\equiv {\delta }_g(\mathrm{mod}{I}^n).}$

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

${\displaystyle {\delta }_f-{\delta }_f^{\prime }\in I^{n-1}R[X]\text{and}{\delta }_g-{\delta }_g^{\prime }\in I^{n-1}R[X].}$

By hypothesis, has

${\displaystyle h\equiv \alpha (f+{\delta }_f)(g+{\delta }_g)\equiv \alpha (f+{\delta }_f^{\prime })(g+{\delta }_g^{\prime })(\mathrm{mod}{I}^n),}$

and thus

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 moduloI, there exist${\displaystyle \beta \in R}$ and${\displaystyle \gamma \in I}$ such that${\displaystyle \alpha \beta =1+\gamma .}$ Thus

using the induction hypothesis again.

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

Thus one has a polynomial of degree less than${\displaystyle \mathrm{deg}g}$ that is congruent modulo${\displaystyle I^n}$ to the product of themonic polynomialg and another polynomialw. This is possible only if${\displaystyle w\in I^{n}R[X],}$ and implies${\displaystyle {\delta }_g-{\delta }_g^{\prime }\in I^{n}R[X].}$ Similarly,${\displaystyle {\delta }_f-{\delta }_f^{\prime }}$ 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 theBézout's identity and of computing modulo${\displaystyle I^n}$ instead of moduloI (if one uses the above description of linear lifting).

For lifting up to modulo${\displaystyle I^N}$ for largeN one can use either method. If, say,${\displaystyle N=2^k,}$ a factorization modulo${\displaystyle I^N}$ requiresN − 1 steps of linear lifting or onlyk − 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 ofN, nature ofR, multiplication algorithm that is used,hardware specificities, etc.).^{[citation needed]}

Quadratic lifting is based on the following property.

Suppose that for some positive integerk there is a factorization

${\displaystyle h\equiv \alpha fg(\mathrm{mod}{I}^k),}$

such thatf andg aremonic polynomials that are coprime moduloI, in the sense that there exist${\displaystyle a,b\in R[X],}$ such that$af+bg\equiv 1(\mathrm{mod}{I}^k).$ Then, there are polynomials${\displaystyle {\delta }_f,{\delta }_g\in I^{k}R[X],}$ such that and

${\displaystyle h\equiv \alpha (f+{\delta }_f)(g+{\delta }_g)(\mathrm{mod}{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(\mathrm{mod}{I}^{2k}).}$

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

Proof: The first assertion is exactly that of linear lifting applied withk = 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+\mathrm{\Delta },}$

where

${\displaystyle \mathrm{\Delta }=\alpha +a{\delta }_f+b{\delta }_g\in I^{k}R[X].}$

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

${\displaystyle (a+{\delta }_a)(f+{\delta }_f)+(b+{\delta }_b)(g+{\delta }_g)=1-{\mathrm{\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 \overline{f}(X)=X^6-\overline{2}=X^6}$

with 6 factors${\displaystyle X}$ not being relatively prime to each other. ByEisenstein'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 \overline{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 =\dots 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 \overline{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

Let${\displaystyle f(x)}$ be apolynomial withinteger (orp-adic integer) coefficients, and letm,k be positive integers such thatm ≤k. Ifr is an integer such that

${\displaystyle f(r)\equiv 0{modp}^k\text{and}{f}^{\prime }(r)\not\equiv 0modp}$

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

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

Furthermore, thiss is unique modulop^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^{\prime }(r){]}^{-1}{modp}^m.}$

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

We use the Taylor expansion off aroundr to write:

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

From${\displaystyle r\equiv s{modp}^k,}$ we see thats −r =tp^k for some integert. Let

For${\displaystyle m⩽k,}$ we have:

The assumption that${\displaystyle f^{\prime }(r)}$ is not divisible byp ensures that${\displaystyle f^{\prime }(r)}$ has an inverse mod${\displaystyle p^m}$ which is necessarily unique. Hence a solution fort exists uniquely modulo${\displaystyle p^m,}$ ands exists uniquely modulo${\displaystyle p^{k+m}.}$

Using the above hypotheses, if we consider an irreducible polynomial

${\displaystyle f(x)=a_0+a_{1}x+\cdots +a_n{x}^n\in K[X]}$

such that${\displaystyle a_0,a_n\ne 0}$, then

${\displaystyle |f|=max\{|a_0|,|a_n|\}}$

In particular, for${\displaystyle f(X)=X^6+10X-1}$, we find in${\displaystyle {\mathbb{Q}}_2[X]}$

but${\displaystyle max\{|a_0|,|a_n|\}=0}$, hence the polynomial cannot be irreducible. Whereas in${\displaystyle {\mathbb{Q}}_7[X]}$ we have both values agreeing, meaning the polynomialcould be irreducible. In order to determine irreducibility, the Newton polygon must be employed.^[2]: 144

Note that given an${\displaystyle a\in {\mathbb{F}}_p}$ theFrobenius endomorphism${\displaystyle y\mapsto y^p}$ gives a nonzero polynomial${\displaystyle x^p-a}$ that has zero derivative

hence thepth roots of${\displaystyle a}$ do not exist in${\displaystyle {\mathbb{Z}}_p}$. For${\displaystyle a=1}$, this implies that${\displaystyle {\mathbb{Z}}_p}$ cannot contain theroot of unity${\displaystyle {\mu }_p}$.

Although thepth roots of unity are not contained in${\displaystyle {\mathbb{F}}_p}$, there are solutions of${\displaystyle x^p-x=x(x^{p-1}-1)}$. Note that

is never zero, so if there exists a solution, it necessarily lifts to${\displaystyle {\mathbb{Z}}_p}$. Because the Frobenius gives${\displaystyle a^p=a,}$ all of the non-zero elements${\displaystyle {\mathbb{F}}_p^{\times }}$ are solutions. In fact, these are the only roots of unity contained in${\displaystyle {\mathbb{Q}}_p}$.^[3]

Using the lemma, one can "lift" a rootr of the polynomialf modulop^k to a new roots modulop^k+1 such thatr ≡s modp^k (by takingm = 1; taking largerm follows by induction). In fact, a root modulop^k+1 is also a root modulop^k, so the roots modulop^k+1 are precisely the liftings of roots modulop^k. The new roots is congruent tor modulop, so the new root also satisfies${\displaystyle f^{\prime }(s)\equiv f^{\prime }(r)\not\equiv 0modp.}$ So the lifting can be repeated, and starting from a solutionr_k of${\displaystyle f(x)\equiv 0{modp}^k}$ we can derive a sequence of solutionsr_k+1,r_k+2, ... of the same congruence for successively higher powers ofp, provided that${\displaystyle f^{\prime }(r_k)\not\equiv 0modp}$ for the initial rootr_k. This also shows thatf has the same number of roots modp^k as modp^k+1, modp^k+2, or any other higher power ofp, provided that the roots off modp^k are all simple.

What happens to this process ifr is not a simple root modp? Suppose that

${\displaystyle f(r)\equiv 0{modp}^k\text{and}{f}^{\prime }(r)\equiv 0modp.}$

Then${\displaystyle s\equiv r{modp}^k}$ implies${\displaystyle f(s)\equiv f(r){modp}^{k+1}.}$ That is,${\displaystyle f(r+t{p}^k)\equiv f(r){modp}^{k+1}}$ for all integerst. Therefore, we have two cases:

• If${\displaystyle f(r)\not\equiv 0{modp}^{k+1}}$ then there is no lifting ofr to a root off(x) modulop^k+1.
• If${\displaystyle f(r)\equiv 0{modp}^{k+1}}$ then every lifting ofr to modulusp^k+1 is a root off(x) modulop^k+1.

Example. To see both cases we examine two different polynomials withp = 2:

${\displaystyle f(x)=x^2+1}$ andr = 1. Then${\displaystyle f(1)\equiv 0mod2}$ and${\displaystyle f^{\prime }(1)\equiv 0mod2.}$ We have${\displaystyle f(1)\not\equiv 0mod4}$ which means that no lifting of 1 to modulus 4 is a root off(x) modulo 4.

${\displaystyle g(x)=x^2-17}$ andr = 1. Then${\displaystyle g(1)\equiv 0mod2}$ and${\displaystyle g^{\prime }(1)\equiv 0mod2.}$ However, since${\displaystyle g(1)\equiv 0mod4,}$ we can lift our solution to modulus 4 and both lifts (i.e. 1, 3) are solutions. The derivative is still 0 modulo 2, soa priori we don't know whether we can lift them to modulo 8, but in fact we can, sinceg(1) is 0 mod 8 andg(3) is 0 mod 8, giving solutions at 1, 3, 5, and 7 mod 8. Since of these onlyg(1) andg(7) are 0 mod 16 we can lift only 1 and 7 to modulo 16, giving 1, 7, 9, and 15 mod 16. Of these, only 7 and 9 giveg(x) = 0 mod 32, so these can be raised giving 7, 9, 23, and 25 mod 32. It turns out that for every integerk ≥ 3, there are four liftings of 1 mod 2 to a root ofg(x) mod 2^k.

In thep-adic numbers, where we can make sense of rational numbers modulo powers ofp as long as the denominator is not a multiple ofp, the recursion fromr_k (roots modp^k) tor_k+1 (roots modp^k+1) can be expressed in a much more intuitive way. Instead of choosingt to be an(y) integer which solves the congruence

${\displaystyle t{f}^{\prime }(r_k)\equiv -(f(r_k)/p^k){modp}^m,}$

lett be the rational number (thep^k here is not really a denominator sincef(r_k) is divisible byp^k):

${\displaystyle -(f(r_k)/p^k)/f^{\prime }(r_k).}$

Then set

${\displaystyle r_{k+1}=r_k+t{p}^k=r_k-\frac{f(r_k)}{f^{\prime }(r_k)}.}$

This fraction may not be an integer, but it is ap-adic integer, and the sequence of numbersr_k converges in thep-adic integers to a root off(x) = 0. Moreover, the displayed recursive formula for the (new) numberr_k+1 in terms ofr_k is preciselyNewton's method for finding roots to equations in the real numbers.

By working directly in thep-adics and using thep-adic absolute value, there is a version of Hensel's lemma which can be applied even if we start with a solution off(a) ≡ 0 modp such that${\displaystyle f^{\prime }(a)\equiv 0modp.}$ We just need to make sure the number${\displaystyle f^{\prime }(a)}$ is not exactly 0. This more general version is as follows: if there is an integera which satisfies:

then there is a uniquep-adic integerb suchf(b) = 0 and The construction ofb amounts to showing that the recursion from Newton's method with initial valuea converges in thep-adics and we letb be the limit. The uniqueness ofb as a root fitting the condition needs additional work.

The statement of Hensel's lemma given above (taking${\displaystyle m=1}$) is a special case of this more general version, since the conditions thatf(a) ≡ 0 modp and${\displaystyle f^{\prime }(a)\not\equiv 0modp}$ say that and${\displaystyle |f^{\prime }(a){|}_p=1.}$

Suppose thatp is an odd prime anda is a non-zeroquadratic residue modulop. Then Hensel's lemma implies thata has a square root in the ring ofp-adic integers${\displaystyle {\mathbb{Z}}_p.}$ Indeed, let${\displaystyle f(x)=x^2-a.}$ Ifr is a square root ofa modulop then:

${\displaystyle f(r)=r^2-a\equiv 0modp\text{and}{f}^{\prime }(r)=2r\not\equiv 0modp,}$

where the second condition is dependent on the fact thatp is odd. The basic version of Hensel's lemma tells us that starting fromr₁ =r we can recursively construct a sequence of integers${\displaystyle \{r_k\}}$ such that:

${\displaystyle r_{k+1}\equiv r_k{modp}^k,r_k^2\equiv a{modp}^k.}$

This sequence converges to somep-adic integerb which satisfiesb² =a. In fact,b is the unique square root ofa in${\displaystyle {\mathbb{Z}}_p}$ congruent tor₁ modulop. Conversely, ifa is a perfect square in${\displaystyle {\mathbb{Z}}_p}$ and it is not divisible byp then it is a nonzero quadratic residue modp. Note that thequadratic reciprocity law allows one to easily test whethera is a nonzero quadratic residue modp, thus we get a practical way to determine whichp-adic numbers (forp odd) have ap-adic square root, and it can be extended to cover the casep = 2 using the more general version of Hensel's lemma (an example with 2-adic square roots of 17 is given later).

To make the discussion above more explicit, let us find a "square root of 2" (the solution to${\displaystyle x^2-2=0}$) in the 7-adic integers. Modulo 7 one solution is 3 (we could also take 4), so we set${\displaystyle r_1=3}$. Hensel's lemma then allows us to find${\displaystyle r_2}$ as follows:

Based on which the expression

${\displaystyle t{f}^{\prime }(r_1)\equiv -(f(r_1)/p^k)modp,}$

turns into:

${\displaystyle t\cdot 6\equiv -1mod7}$

which implies${\displaystyle t=1.}$ Now:

${\displaystyle r_2=r_1+t{p}^1=3+1\cdot 7=10={13}_7.}$

And sure enough,${\displaystyle {10}^2\equiv 2{mod7}^2.}$ (If we had used the Newton method recursion directly in the 7-adics, then${\displaystyle r_2=r_1-f(r_1)/f^{\prime }(r_1)=3-7/6=11/6,}$ and${\displaystyle 11/6\equiv 10{mod7}^2.}$)

We can continue and find${\displaystyle r_3=108=3+7+2\cdot 7^2={213}_7}$. Each time we carry out the calculation (that is, for each successive value ofk), one more base 7 digit is added for the next higher power of 7. In the 7-adic integers this sequence converges, and the limit is a square root of 2 in${\displaystyle {\mathbb{Z}}_7}$ which has initial 7-adic expansion