f(a) ≡ 0, f'(a) ≢ 0 mod p.
El Lifting de Raíces Simples es una técnica fundamental en teoría de números que viene del Lema de Hensel. Te da un método sistemático para resolver congruencias polinomiales módulo potencias de primos, $p^k$. La idea central es iterativa: si conoces una solución a una congruencia polinomial $f(x) \equiv 0 \pmod{p^k}$, puedes "elevar" (hacer un lift de) esta solución a una solución módulo $p^{k+1}$. Esta técnica aplica específicamente cuando la raíz es "simple" (o no singular), lo que significa que la derivada del polinomio evaluada en la raíz no es divisible entre $p$.
Este concepto es crucial porque reduce el problema de resolver $f(x) \equiv 0 \pmod{p^n}$ a simplemente encontrar las raíces módulo $p$. Una vez que encuentras las raíces módulo $p$, si la condición de no singularidad se cumple, puedes elevarlas de forma única a cualquier potencia mayor $p^n$ sin tener que usar prueba y error. En el contexto de las olimpiadas de matemáticas, esto te permite analizar la existencia y el número de soluciones para congruencias con módulos grandes, descomponiendo el módulo en potencias de primos y aplicando el lifting.
Intuitivamente, este proceso es el análogo en teoría de números del Método de Newton de cálculo. Así como el Método de Newton usa la recta tangente (la derivada) para mejorar la aproximación de una raíz, el Lema de Hensel usa la derivada formal para mejorar una solución de un módulo menor a uno mayor. La condición $f'(a) \not\equiv 0 \pmod p$ asegura que la "tangente" no sea horizontal, lo que garantiza que el paso de refinamiento te dé un resultado único.
El Teorema Principal (Lema de Hensel para Raíces Simples): Sea $f(x)$ un polinomio con coeficientes enteros, $p$ un primo y $k \ge 1$ un entero. Supón que existe un entero $a$ tal que: $$f(a) \equiv 0 \pmod{p^k} \quad \text{y} \quad f'(a) \not\equiv 0 \pmod p$$ Entonces existe un único entero $b$ módulo $p^{k+1}$ tal que: $$f(b) \equiv 0 \pmod{p^{k+1}} \quad \text{y} \quad b \equiv a \pmod{p^k}$$
La Fórmula de Lifting: Puedes calcular el lift único $b$ explícitamente usando la fórmula: $$b = a - f(a) \cdot [f'(a)]^{-1} \pmod{p^{k+1}}$$ donde $[f'(a)]^{-1}$ denota el inverso multiplicativo modular de $f'(a)$ módulo $p$. Nota que aunque calculas el inverso mod $p$, la aritmética para $a - f(a)[\dots]$ la haces módulo $p^{k+1}$.
Generalización: Si $r$ es una solución de $f(x) \equiv 0 \pmod p$ tal que $f'(r) \not\equiv 0 \pmod p$, entonces para cualquier entero $n \ge 1$, hay una única solución $x_n$ módulo $p^n$ tal que $x_n \equiv r \pmod p$.
Lo que hay que demostrar es que dado un $a$ tal que $f(a) \equiv 0 \pmod{p^k}$ y $f'(a) \not\equiv 0 \pmod p$, existe un único $b \pmod{p^{k+1}}$ que cumple las condiciones.
Paso 1: Parametrización del lift Como necesitas que $b \equiv a \pmod{p^k}$, cualquier $b$ de este tipo debe tener la forma: $$b = a + t \cdot p^k$$ para algún entero $t$. El objetivo es encontrar un valor de $t$ tal que $f(a + t p^k) \equiv 0 \pmod{p^{k+1}}$.
Paso 2: Expansión de Taylor Expande el polinomio $f(a + t p^k)$ usando la expansión en serie de Taylor para polinomios. Como $f(x)$ es un polinomio, la expansión es finita y tiene coeficientes enteros (después de ajustar los factoriales): $$f(a + t p^k) = f(a) + f'(a)(t p^k) + \frac{f''(