What is the difference between Hensel lifting and the Newton-Raphson method? So in the Newton-Raphson method to iteratively approximate a root of a real polynomial, we start with a crude approximation $x_0 \in \mathbb{R}$ for $f(x)=0$ where $f(x) \in \mathbb{R}[x]$. For the next iterate $x_1$, we put $x_1 = x_0 + \epsilon$, and we want to determine $\epsilon$ to get a better approximation. For this we use a Taylor series and take a linear approximation, and equate $f(x_1)$ to 0 to get a value of $\epsilon$.
$$ f(x_1) = f(x_0 + \epsilon) = f(x_0) + \epsilon f'(x_0) + O(\epsilon^2) \approx f(x_0) + \epsilon f'(x_0)$$
$$ 0 = f(x_0) + \epsilon f'(x_0)$$
$$ \epsilon = - \frac{f(x_0)}{f'(x_0)}$$
$$ x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}$$
Of course, a necessary condition here is that $f'(x_0) \neq 0$.
Now in the case of Hensel lifting of a root modulo $p$ of $f(x) \in \mathbb{Z}[x]$ to a root modulo $p^2$, we do something very similar. If $x_0 \in \mathbb{Z}$ is such that $f(x_0) \equiv 0 \pmod p$ and $f'(x_0) \neq 0 \pmod p$, then again we take $x_1 = x_0 + p\epsilon$, ignore everything but first order terms by going modulo $p^2$ and find $\epsilon$ by equating $f(x_1)$ to zero.
$$ f(x_1) = f(x_0 + p\epsilon) = f(x_0) + p\epsilon f'(x_0) + O(p^2\epsilon^2) $$
$$ 0 = f(x_0) + p\epsilon f'(x_0) \pmod {p^2} $$
$$ \epsilon = - \frac{f(x_0)}{pf'(x_0)}$$
$$ x_1 = x_0 - \frac{f(x_0)}{f'(x_0)}$$
So just as before, we end up ignoring terms beyond the linear term, and the $x_1$ that we get is pretty much the same thing, except that if we do get a fraction, we think of it (the division or inverse) as operating within the ring $\mathbb{Z}/p^2\mathbb{Z}$ and express it as an integer.
So except for the starting value (in Newton-Raphson we start at some (any) crude approximation, while in Hensel lifting we start with a root modulo prime $p$), are the two methods essentially the same? Can't we obtain the lifts modulo higher powers of $p$ simply by looking at the iterates in the Newton-Raphson method, if only we start with an agreeable candidate?
 A: They are, from a distance, the same. The main difference is that the iterates of Newton's method always remain approximations, while Hensel lifting is exact in the values it computes. As p-adic numbers, the iterates of Hensel are also approximations, but their lower order terms become stationary after finitely many iterations.
So you can for instance use Hensel lifting to compute a power series expansion of some solution of an algebraic problem, and if this power series is actually a rational function, this can be exactly recovered from the Hensel-produced power series.
A: There is a very general viewpoint that relates Newton's method
and similar successive approximation schemes such as Hensel's lemma. This is essentially folklore, but has become more accessible recently due to computational applications (e.g. polynomial factorization). To locate pertinent literature you can begin with the papers reviewed below.

von zur Gathen, Joachim (3-TRNT-C) 85j:12012 12J20 65P05
Hensel and Newton methods in valuation rings.
Math. Comp. 42 (1984), no. 166, 637--661.
Hensel's lemma is a fundamental tool in the study of algebraic equations over
$p$-adic fields. In the folklore of number theory it has been known for a long
time that Hensel's and Newton's method are formally the same (this remark
appears in printed form in an article by D. J. Lewis published in a book
edited by W. J. LeVeque [Studies in number theory, 25--75, see p. 29,
Prentice-Hall, Englewood Cliffs, N.J., 1969; MR 39 #2699]).
A generalized version of Hensel's lemma in suitable valuation rings is
contained in N. Bourbaki's book [Elements of mathematics, 23, Commutative
algebra (French), see Chapter III, Section 4, Theorem 1 and Theorem 2,
Hermann, Paris, 1958; MR 20 #4576].
This paper also deals with the study of Hensel's method in valuation rings and
shows that Newton's method is a special case of Hensel's. The presentation
emphasizes the algorithmic point of view and is very detailed and clear. The
linear and quadratic cases of Hensel's lemma are both given. Newton's method
is applied to systems of nonlinear partial differential equations. Then the
author presents an algorithm for the computation of a shortest nonzero vector
in a non-Archimedean valuation module. These results are applied in the last
section, which contains an algorithm for factoring polynomials over a ring
with valuations.
          Reviewed by Maurice Mignotte


Ribenboim, Paulo (3-QEN) 87a:12014 12J10 13A18
Equivalent forms of Hensel's lemma.
Exposition. Math. 3 (1985), no. 1, 3--24.
From the introduction: "The celebrated Hensel's lemma, which is the
cornerstone of the theory of $p$-adic numbers, has been the object of
extensive studies. However, our aim in this paper is not to describe the
development of ideas and applications centered around Hensel's lemma, but
rather to examine closely the various formulations found in the literature. We
place ourselves in the framework of the theory of valued fields and show that
Hensel's lemma is logically equivalent to many propositions concerning the
number of extensions of the valuation to algebraic extensions, or the lifting
of polynomials from the residue field, or the determination of zeroes of a
polynomial by a method which dates back to Newton, or even to a geometric
formulation concerning the mutual distance between the zeroes of
polynomials. These facts are of a `folkloric' nature, yet no complete proof of
their equivalence has appeared in any one paper.
"This article is written at the level of research students."
          Reviewed by Antonio Jose Engler


Miola, A. (I-ROME-I); Mora, T. (I-GENO)  90f:68096 68Q40 13A18 13J10
Constructive lifting in graded structures: a unified view of Buchberger
and Hensel methods.
Computational aspects of commutative algebra.
J. Symbolic Comput. 6 (1988), no. 2-3, 305--322.
A graded structure is a filtered commutative ring $A$ which is filtered by a
totally ordered group and has a graded associated ring and a ring
completion. The authors define a process for solving, in the ring completion,
a polynomial multivariate equation over $A$ by successive approximations. They
discuss under which conditions this process converges.
The main interest of this theory is that Hensel lifting, Buchberger's
algorithm for Grobner basis computations in polynomial rings and Hironaka's
division process by a standard basis in rings of formal power series are
instances of the above process. For example, Hensel lifting is an
approximative resolution of $yz-a=0$, which needs some conditions on $a$ and
on the initial values of $y$ and $z$ to be convergent.
{For the entire collection see MR 89j:68004}.
          Reviewed by Daniel Lazard

