I am trying to understand Hensel's lemma[wiki] with Newton iteration. But I dont understand how $r_{k+1}=r_k+t p^k=r_k-\frac{f(r_k)}{f'(r_k)}$ is the same. More detailed in examples: They get $10^2 \cong 2 \pmod{7^2}$ and say "with $7$-adic numbers you get $\frac{11}{6} \cong 10 \pmod{7^2}$
How is that calculated?
Thank you.
This comes from the end of the "Derivation" part on the wiki link. Let $f$ be a polynomial function and $r$ be one root of $f$ modulo $p^k$ such as that: $$f(r) \equiv 0 \pmod{p^k}, f'(r) \not\equiv 0 \pmod{p}$$ Hensel's Lemma states that there is a root $s$ of $f$ modulo $p^k$, congruent to $r$, that lifts to a root modulo $p^{k + m}$ for a positive integer $m \leq k$. The Taylor expansion of $f$ around $r$ gives the following:
$$f(x) = f(r) + f'(r) (x - r) + \frac{f''(r)}{2}(x - r)^2 + \cdots$$
For $r \equiv s \bmod{p^k}$, we need $s = r + p^kq$ for some $q \in \mathbb{Z}$. If we substitute it on the Taylor expansion, we get:
$$f(s) = f(r) + f'(r)(p^kq) + \frac{f''(r)}{2}(p^kq)^2 + \cdots$$ $$f(s) = f(r) + qf'(r)p^k + q\frac{f''(r)}{2}p^{2k} + \cdots$$
If we reduce modulo $p^{k + m}$, the latter terms will vanish, once $k + m < 2k$. We can also substitute $f(r) = zp^k$, because $r$ is a root modulo $k$. So:
$$0 \equiv zp^k + qf'(r)p^k \pmod{p^{k + m}}$$
We can use congruence properties to remove a factor of $p^k$:
$$0 \equiv z + qf'(r) \pmod{p^m}$$ $$q \equiv -\frac{z}{f'(r)} \pmod{p^m}$$ $$q = -\frac{z}{f'(r)} + jp^m\text{, for some integer } j$$
Remember that $zp^k = f(r) $. Thus, we conclude the formula:
$$s = r + p^kq$$ $$s = r - \frac{p^kz}{f'(r)} + jp^kp^m$$ $$s = r - \frac{f(r)}{f'(r)} + jp^{k + m}$$
Once we are lifting $s$ from modulo $p^k$ to modulo $p^{k + m}$, the last term vanishes.
Now to the examples. Suppose you want to find a solution of $x^2 - 2 = 0$ modulo $7^2$. We can try and find a solution modulo 7 first. Actually, $x = 3$ is a solution:
$$3^2 - 2 \equiv 9 - 2 \equiv 7 \equiv 0 \pmod 7$$
If we take the derivative, $2x$ we see that it is not congruent to $0$ modulo $7$. Therefore, we can apply Hensel's Lemma to lift it modulo $7^2$ (here, our $k$ is $1$, so we can only lift it using $m = 1$). We have:
$$f(3) \equiv 7 \pmod{7^2}$$ $$f'(3) \equiv 6 \pmod{7^2}$$
Hensel's Lemma gives that we can lift a solution $x$ to a solution $y$ using:
$$y = x - \frac{f(x)}{f'(x)} \pmod{7^2}$$ $$y = 3 - (7 \cdot 6^{-1}) \pmod{7^2}$$
on this line, you can say $3 - \frac{7}{6} = \frac{11}{6} \bmod{7^2}$ is a solution, but let's not talk of fractions on a ring of integers. The inverse of $6$ modulo $7^2$ is 41. So:
$$y = 3 - 7\cdot41 \pmod{7^2}$$ $$y = -284 \equiv 10 \pmod{7^2}$$