a_{k+1} = a_k - f(a_k)/f'(a_k).
La Iteración de Hensel es un método muy potente en teoría de números que sirve para resolver congruencias polinomiales módulo potencias de un primo $p$. Básicamente es el análogo $p$-ádico del Método de Newton (Newton-Raphson) de cálculo real. Aunque el Lema de Hensel estándar suele describir cómo elevar una solución de módulo $p^k$ a módulo $p^{k+1}$, la Iteración de Hensel se refiere a la forma de convergencia rápida que eleva una solución de módulo $p^k$ directamente a módulo $p^{2k}$. Esta "convergencia cuadrática" te permite construir soluciones módulo potencias muy altas de $p$ de manera eficiente.
Esta técnica es fundamental para estudiar los números $p$-ádicos, ya que permite demostrar que un polinomio tiene una raíz en el anillo de los enteros $p$-ádicos $\mathbb{Z}_p$. En las olimpiadas de matemáticas, la usas para resolver problemas avanzados de aritmética modular donde tienes que probar que existe una raíz o construir una clase de residuo específica que cumpla $f(x) \equiv 0 \pmod{p^n}$. La iteración se basa en la expansión de Taylor formal de los polinomios y requiere que la derivada del polinomio sea invertible módulo $p$ (o sea, la raíz debe ser "simple").
Intuitivamente, si tienes una raíz aproximada $a_k$ tal que $f(a_k)$ está cerca de 0 (es decir, es divisible por una potencia alta de $p$), puedes ajustar $a_k$ con un pequeño término de corrección para encontrar un nuevo valor $a_{k+1}$ que haga que $f(a_{k+1})$ esté todavía más cerca de 0. La fórmula $a_{k+1} = a_k - f(a_k)/f'(a_k)$ es igualita a la aproximación por la recta tangente que ves en cálculo, pero aquí la "cercanía" la define la divisibilidad entre $p$.
La Fórmula de Iteración Sea $f(x)$ un polinomio con coeficientes enteros. Toma $a_k$ como un entero tal que $f(a_k) \equiv 0 \pmod{p^n}$ para algún entero $n \ge 1$. Si $f'(a_k) \not\equiv 0 \pmod p$, entonces la siguiente aproximación es: $$a_{k+1} \equiv a_k - f(a_k) \cdot [f'(a_k)]^{-1} \pmod{p^{2n}}$$ Aquí, $[f'(a_k)]^{-1}$ es el inverso multiplicativo modular de $f'(a_k)$ módulo $p^{2n}$ (o módulo $p^n$, ya que el término de corrección ya es un múltiplo de $p^n$).
Propiedad de Convergencia Si $a_k$ cumple $f(a_k) \equiv 0 \pmod{p^n}$, entonces $a_{k+1}$ cumple: $$f(a_{k+1}) \equiv 0 \pmod{p^{2n}}$$ Esto duplica la precisión (el exponente de $p$) en cada paso.
Definición de la Sucesión Si la defines de forma recursiva, empezando con una raíz $a_0$ módulo $p$: $$a_{k+1} = a_k - \frac{f(a_k)}{f'(a_k)}$$ Esta sucesión converge a una única raíz $\alpha \in \mathbb{Z}_p$ tal que $f(\alpha) = 0$.
Teorema: Sea $f(x) \in \mathbb{Z}[x]$. Supón que $a$ es una solución de $f(a) \equiv 0 \pmod{p^n}$ tal que $f'(a) \not\equiv 0 \pmod p$. Entonces $b = a - f(a)\overline{f'(a)}$, donde $\overline{f'(a)}$ es el inverso de $f'(a)$ módulo $p^n$, es una solución de $f(b) \equiv 0 \pmod{p^{2n}}$.
Demostración: Buscas una solución $b$ módulo $p^{2n}$ que sea congruente a $a$ módulo $p^n$. Puedes escribir $b$ de la forma: $$b = a + y p^n$$ donde $y$ es un entero que hay que determinar.
Aplica la expansión de Taylor para polinomios alrededor de $x = a$. Para cualquier polinomio $P(x) \in \mathbb{Z}[x]$ y enteros $h$, la expansión es: $$f(a+h) = f(a) + f'(a)h + \frac{f''(a)}{2!}h^2 + \dots + \frac{f^{(d)}(a)}{d!}h^d$$ Nota que para polinomios con coeficientes enteros, los términos $\frac{f^{(k)}(a)}{k!}$ siempre son enteros.
Sustituye $h = y p^n$: $$f(a + y p^n) = f(a) + f'(a)(y p^n) + \sum_{k=2}^d \frac{f^{(k)}(a)}{k!} (y p^n)^k$$ Estás trabajando módulo $p^{2n}$. Fíjate en los términos de mayor orden para $k \ge 2$: $$(y p^n)^k = y^k p^{nk} = y^k p^{2n} p^{n(k-2)}$$ Como $n \ge 1$, entonces $nk \ge 2n$ para todo $k \ge 2$. Por lo tanto, todos los términos con $k \ge 2$ son divisibles entre $p^{2n}$. $$f(a + y p^n) \equiv f(a) + f'(a) y p^n \pmod{p^{2n}}$$ Quieres encontrar $y$ tal que $f(a + y p^n) \equiv 0 \pmod{p^{2n}}$. Si igualas el lado derecho a 0: $$f(a) + f'(a) y p^n \equiv 0 \pmod{p^{2n}}$$ Como $f(a) \equiv 0 \pmod{p^n}$ por hipótesis, puedes escribir $f(a) = q p^n$ para algún entero $q$. $$q p^n + f'(a) y p^n \equiv 0 \pmod{p^{2n}}$$ Si divides toda la congruencia entre $p^n$ (lo cual es válido porque el módulo es múltiplo de $p^n$): $$q + f'(a) y \equiv 0 \pmod{p^n}$$ $$f'(a) y \equiv -q \pmod{p^n}$$ Como $f'(a) \not\equiv 0 \pmod p$, es coprimo con $p$, y por lo tanto coprimo con $p^n$. El inverso $(f'(a))^{-1}$ existe módulo $p^n$. Llama $u$ a este inverso. $$y \equiv -q u \pmod{p^n}$$ Sustituyendo $q = f(a)/p^n$ y $u = (f'(a))^{-1}$: $$y \equiv -\frac{f(a)}{p^n} \cdot \frac{1}{f'(a)} \pmod{p^n}$$ Finalmente, al sustituir $y$ de vuelta en $b = a + y p^n$: $$b = a + p^n \left( -\frac{f(a)}{p^n f'(a)} \right) = a - \frac{f(a)}{f'(a)}$$ Este valor de $b$ cumple $f(b) \equiv 0 \pmod{p^{2n}}$, con lo que terminas la demostración. $\square$