Lema de Elevación de Hensel

Teoría

El Lema de Elevación de Hensel es un resultado fundamental en teoría de números que te da un método sistemático para elevar soluciones de congruencias polinomiales módulo un primo $p$ a soluciones módulo potencias de ese primo, $p^k$. Es el análogo en aritmética modular del Método de Newton de cálculo, que aproxima raíces de funciones reales de forma iterativa. En el contexto de matemáticas de olimpiada, este lema te permite resolver congruencias polinomiales de grado alto $f(x) \equiv 0 \pmod{p^k}$ resolviendo primero el caso mucho más sencillo módulo $p$, y luego "elevando" esa solución de forma inductiva por la escalera de potencias ($p^2, p^3, \dots$).

El poder del Lema de Hensel está en que no solo te dice si existen soluciones, sino también cuántas hay y cómo es su estructura. El comportamiento del proceso de elevación depende totalmente de la derivada del polinomio, $f'(x)$. Si la derivada en la raíz no es cero módulo $p$ (una "raíz simple"), la solución se eleva de forma única a potencias mayores. Si la derivada es cero (una "raíz singular"), el proceso de elevación se vuelve más complejo, y puede que no resulten soluciones o que resulten múltiples soluciones en el siguiente nivel. Esta distinción es vital para problemas que involucran condiciones de solubilidad módulo $n$.

En problemas de olimpiada, esta técnica es esencial cuando el módulo es una potencia de un primo grande o cuando analizas las propiedades $p$-ádicas de los enteros. Se usa seguido junto con el Teorema del Residuo Chino; para resolver $f(x) \equiv 0 \pmod n$, factorizas $n$ en potencias de primos, aplicas el Lema de Hensel a cada potencia de primo y combinas los resultados.

Fórmulas Clave

Sea $f(x)$ un polinomio con coeficientes enteros, $p$ un primo y $k \ge 1$ un entero. Supón que $r$ es una solución a la congruencia: $$f(r) \equiv 0 \pmod{p^k}$$

Quieres encontrar una solución $s$ módulo $p^{k+1}$ tal que $s \equiv r \pmod{p^k}$. Una solución así debe tener la forma $s = r + t \cdot p^k$ para algún entero $t$ donde $0 \le t < p$.

La Fórmula General de Elevación: El valor de $t$ se determina con la congruencia lineal: $$f'(r) \cdot t \equiv -\frac{f(r)}{p^k} \pmod p$$

Caso 1: La Raíz Simple (Elevación Única) Si $f'(r) \not\equiv 0 \pmod p$, hay un único entero $t$ módulo $p$, y por lo tanto una única solución $s$ módulo $p^{k+1}$: $$s \equiv r - f(r) \cdot [f'(r)]^{-1} \pmod{p^{k+1}}$$ donde $[f'(r)]^{-1}$ denota el inverso modular módulo $p^{k+1}$ (o módulo $p$, dependiendo de la formulación específica que uses).

Caso 2: La Raíz Singular Si $f'(r) \equiv 0 \pmod p$, entonces $f'(r)$ no es invertible. Tienes que examinar el valor de $-\frac{f(r)}{p^k}$:

1. Si $\frac{f(r)}{p^k} \not\equiv 0 \pmod p$ (lo que significa que $f(r) \not\equiv 0 \pmod{p^{k+1}}$), hay cero soluciones módulo $p^{k+1}$.
2. Si $\frac{f(r)}{p^k} \equiv 0 \pmod p$ (lo que significa que $f(r) \equiv 0 \pmod{p^{k+1}}$), la congruencia $0 \cdot t \equiv 0 \pmod p$ se cumple para toda $t$. Hay $p$ soluciones distintas módulo $p^{k+1}$, dadas por $r, r+p^k, r+2p^k, \dots, r+(p-1)p^k$.

Demostración

Teorema: Sea $f(x)$ un polinomio con coeficientes enteros. Sea $k \ge 1$ y sea $r$ un entero tal que $f(r) \equiv 0 \pmod{p^k}$. Buscas una $s$ tal que $f(s) \equiv 0 \pmod{p^{k+1}}$ y $s \equiv r \pmod{p^k}$.

Demostración:

Como $s \equiv r \pmod{p^k}$, puedes escribir $s$ de la forma: $$s = r + t \cdot p^k$$ donde $t$ es un entero por determinar. Sustituye esto en el polinomio $f(x)$.

Usando la expansión de Taylor para polinomios (que es exacta y termina para polinomios), expande $f(r + t p^k)$ alrededor de $r$: $$f(r + t p^k) = f(r) + f'(r)(t p^k) + \frac{f''(r)}{2!}(t p^k)^2 + \dots + \frac{f^{(n)}(r)}{n!}(t p^k)^n$$

Nota que para un polinomio con coeficientes enteros, los términos $\frac{f^{(j)}(r)}{j!}$ son enteros. Estás trabajando módulo $p^{k+1}$. Observa el término que tiene la segunda derivada: $$\frac{f''(r)}{2!} (t p^k)^2 = \text{entero} \cdot t^2 \cdot p^{2k}$$ Como $k \ge 1$, tienes que $2k \ge k+1$. Por lo tanto, $p^{k+1}$ divide a $p^{2k}$. En consecuencia, todos los términos que tienen $(p^k)^2$ y potencias mayores son congruentes a $0$ módulo $p^{k+1}$

La expansión se simplifica a: $$f(r + t p^k) \equiv f(r) + t \cdot p^k \cdot f'(r) \pmod{p^{k+1}}$$

Quieres que $s$ sea una raíz, así que pon $f(s) \equiv 0 \pmod{p^{k+1}}$: $$f(r) + t \cdot p^k \cdot f'(r) \equiv 0 \pmod{p^{k+1}}$$

Como $r$ es una raíz módulo $p^k$, sabes que $f(r)$ es divisible entre $p^k$. Puedes escribir $f(r) = A \cdot p^k$ para algún entero $A$. Sustituyendo esto de nuevo en la congruencia: $$A \cdot p^k + t \cdot p^k \cdot f'(r) \equiv 0 \pmod{p^{k+1}}$$

Puedes dividir toda la congruencia entre $p^k$ (lo cual reduce el módulo de $p^{k+1}$ a $p$): $$A + t \cdot f'(r) \equiv 0 \pmod p$$ Sustituyendo $A = \frac{f(r)}{p^k}$ de vuelta, obtienes la congruencia lineal para $t$: $$t \cdot f'(r) \equiv -\frac{f(r)}{p^k} \pmod p$$

La existencia y el número de soluciones para $t$ (y por lo tanto para $s$) dependen de si $f'(r)$ es invertible módulo $p$, lo cual corresponde a los casos listados en la sección de Fórmulas Clave.

$\square$