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).
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.
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
Hensel's lemma asserts that such a lifting is always possible under mild conditions; see next section.
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
Hensel's lemma is generally proved incrementally by lifting a factorization over
The main ingredient of the proof is that coprime polynomials over a field satisfy Bézout's identity.
and Bézout's identity allows defining coprime polynomials and proving Hensel's lemma, even if the ideal
Suppose that for some positive integer k there is a factorization such that f and g are monic polynomials that are coprime modulo I, in the sense that there exist
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
one can proceed by induction and suppose that the uniqueness has been proved for n − 1, the case n = 0 being trivial.
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.).
Suppose that for some positive integer k there is a factorization such that f and g are monic polynomials that are coprime modulo I, in the sense that there exist
satisfy a Bézout's identity of the form (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
we can derive a sequence of solutions rk+1, rk+2, ... of the same congruence for successively higher powers of p, provided that
In the p-adic numbers, where we can make sense of rational numbers modulo powers of p as long as the denominator is not a multiple of p, the recursion from rk (roots mod pk) to rk+1 (roots mod pk+1) can be expressed in a much more intuitive way.
The construction of b amounts to showing that the recursion from Newton's method with initial value a converges in the p-adics and we let b be the limit.
Suppose that p is an odd prime and a is a non-zero quadratic residue modulo p. Then Hensel's lemma implies that a has a square root in the ring of p-adic integers
If r is a square root of a modulo p then: where the second condition is dependent on the fact that p is odd.
The basic version of Hensel's lemma tells us that starting from r1 = r we can recursively construct a sequence of integers
and it is not divisible by p then it is a nonzero quadratic residue mod p. Note that the quadratic reciprocity law allows one to easily test whether a is a nonzero quadratic residue mod p, thus we get a practical way to determine which p-adic numbers (for p odd) have a p-adic square root, and it can be extended to cover the case p = 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
Each time we carry out the calculation (that is, for each successive value of k), one more base 7 digit is added for the next higher power of 7.
That is, if c ≡ 1 mod 27 then the general Hensel's lemma tells us f(x) has a 3-adic root, so c is a 3-adic cube.
In a similar way, after some preliminary work, Hensel's lemma can be used to show that for any odd prime number p, any p-adic integer c congruent to 1 modulo p2 is a p-th power in
Masayoshi Nagata proved in the 1950s that for any commutative local ring A with maximal ideal m there always exists a smallest ring Ah containing A such that Ah is Henselian with respect to mAh.
This means that Ah is usually much smaller than the completion  while still retaining the Henselian property and remaining in the same category[clarification needed].