El método del análisis p-ádico avanzado: LTE generalizado

Revisión del LTE y sus hipótesis exactas

El Lema de Levantamiento de la Exponente (LTE) es una de las herramientas más potentes de la TdN olímpica. Recordemos sus dos versiones:

LTE para primos impares. Sea $p$ primo impar, $p \mid a - b$, $p \nmid a$, $p \nmid b$, $n$ entero positivo. Entonces:

$v_p(a^n - b^n) = v_p(a - b) + v_p(n),$

donde $v_p(m)$ denota la valuación $p$-ádica de $m$ (el mayor exponente $k$ tal que $p^k \mid m$).

**LTE para $p = 2$.** Con $2 \mid a - b$ (i.e., $a \equiv b \pmod{2}$), $n$ par positivo: $v_2(a^n - b^n) = v_2(a-b) + v_2(a+b) + v_2(n) - 1$. Para $n$ impar: $v_2(a^n - b^n) = v_2(a - b)$.

Atención a las hipótesis. En el LTE para primos impares, la condición $p \mid a - b$ es esencial. Si $p \nmid a - b$ pero $p \mid a^n - b^n$, la fórmula no aplica directamente; en ese caso $v_p(a^n - b^n) = v_p(\Phi_d(a,b))$ donde $d = \mathrm{ord}_p(ab^{-1})$, conectando con la teoría de Zsygmondy.

LTE para sumas: $a^n + b^n$

La variante del LTE para sumas $a^n + b^n$ es igualmente útil. Recordemos: $a^n + b^n = a^n - (-b)^n$ cuando $n$ es impar.

**LTE para sumas, primo impar $p$.** Sea $p$ primo impar, $p \mid a + b$, $p \nmid a$, $p \nmid b$, $n$ entero positivo impar. Entonces:

$v_p(a^n + b^n) = v_p(a + b) + v_p(n).$

Extensión a sumas de cubos y potencias. La fórmula $a^3 + b^3 = (a+b)(a^2 - ab + b^2)$ permite analizar $v_p(a^3 + b^3)$ para cualquier primo $p$: si $p \mid a + b$ y $p \nmid a^2 - ab + b^2$, entonces $v_p(a^3+b^3) = v_p(a+b)$. Nótese que $a^2 - ab + b^2 \equiv (a+b)^2 - 3ab$. Si $p = 3$ y $3 \mid a + b$: $a^2 - ab + b^2 \equiv a^2 + 2a(-a) + a^2 = 0 \pmod 3$, así $3 \mid a^2 - ab + b^2$ y hay que ser más cuidadoso. En general: para $p \ne 3$ con $p \mid a+b$, se tiene $v_p(a^3+b^3) = v_p(a+b)$.

Ejemplo ilustrativo: $v_3(10^{2023} + 2^{2023})$. Aquí $a = 10$, $b = 2$, $a + b = 12$, $3 \mid 12$ y $3 \nmid a, b$. Por LTE: $v_3(10^{2023} + 2^{2023}) = v_3(12) + v_3(2023) = 1 + v_3(7 \cdot 17^2) = 1 + 0 = 1$.

El valor absoluto $p$-ádico y la desigualdad ultramétrica

El LTE tiene una interpretación profunda en términos de los números $p$-ádicos $\mathbb{Q}_p$. El **valor absoluto $p$-ádico** de un racional $x = p^k \cdot a/b$ (con $p \nmid a, p\nmid b$) es $|x|_p = p^{-k}$. Por convención $|0|_p = 0$.

Este valor absoluto satisface la desigualdad ultramétrica (o no-arquimediana): $|x + y|_p \le \max(|x|_p, |y|_p)$, con igualdad cuando $|x|_p \ne |y|_p$.

En términos de valuaciones: $v_p(x + y) \ge \min(v_p(x), v_p(y))$, con igualdad si $v_p(x) \ne v_p(y)$.

La desigualdad ultramétrica es la responsable de que muchos argumentos sobre divisibilidad "funcionen mejor" que en los reales. Por ejemplo: si $v_p(x) > v_p(y)$, entonces $v_p(x + y) = v_p(y)$ exactamente. Esto es intuitivo: "la parte más pequeña domina".

Aplicación directa: si $f(x) = a_n x^n + \cdots + a_0$ es un polinomio y queremos estimar $v_p(f(m))$ para entero $m$, la desigualdad ultramétrica dice que $v_p(f(m)) \ge \min_k(v_p(a_k m^k))$, con igualdad si el mínimo se alcanza en un único término.

El lema de Hensel: levantar raíces de $p$ a $p^k$

El lema de Hensel permite "levantar" raíces de un polinomio módulo $p$ a raíces módulo $p^k$ para cualquier $k$. Es el análogo $p$-ádico del teorema de la función implícita.

Teorema (Hensel). Sea $f(x) \in \mathbb{Z}[x]$ un polinomio y $a \in \mathbb{Z}$ tal que $f(a) \equiv 0 \pmod{p}$ y $f'(a) \not\equiv 0 \pmod{p}$. Entonces para todo $k \ge 1$ existe un único $a_k \in \mathbb{Z}/p^k\mathbb{Z}$ con $f(a_k) \equiv 0 \pmod{p^k}$ y $a_k \equiv a \pmod{p}$.

Construcción iterativa. Dados $a_k$ con $f(a_k) \equiv 0 \pmod{p^k}$, buscamos $a_{k+1} = a_k + t \cdot p^k$ con $t \in \{0, 1, \ldots, p-1\}$ tal que $f(a_{k+1}) \equiv 0 \pmod{p^{k+1}}$. Expandiendo por Taylor: $f(a_k + tp^k) \equiv f(a_k) + f'(a_k) \cdot tp^k \pmod{p^{k+1}}$. Como $f(a_k) = c \cdot p^k$ para algún entero $c$ (pues $p^k \mid f(a_k)$), necesitamos $c + f'(a_k) t \equiv 0 \pmod{p}$, es decir $t \equiv -c (f'(a_k))^{-1} \pmod{p}$ (que es único pues $f'(a_k) \not\equiv 0 \pmod{p}$).

Contraejemplo sin la hipótesis. Si $f'(a) \equiv 0 \pmod{p}$ y $f(a) \not\equiv 0 \pmod{p^2}$, entonces $a$ no se levanta. Por ejemplo: $f(x) = x^2 + p$, $a = 0$. $f(0) = p \equiv 0 \pmod{p}$, $f'(0) = 0 \equiv 0 \pmod{p}$. Para $k = 2$: $f(tp) = t^2p^2 + p$; esto nunca es $\equiv 0 \pmod{p^2}$ pues $p \not\equiv 0 \pmod{p^2}$.

Uso olímpico. El lema de Hensel es la clave para preguntas del tipo "¿para cuáles $k$ tiene solución $x^n \equiv a \pmod{p^k}$?". La respuesta, cuando $p \nmid a$: si $x^n \equiv a \pmod p$ tiene solución $a_1$ con $f'(a_1) = n a_1^{n-1} \not\equiv 0 \pmod p$ (es decir, $p \nmid n$ y $p \nmid a_1$), entonces se puede levantar a todos los $p^k$.

Problema olímpico resuelto: LTE avanzado

Problema (estilo IMO/selectivo). Sea $p$ un primo impar. Encuentra todos los enteros positivos $n$ tales que $p^2 \mid 2^n - 1$ si $p \mid 2^{\mathrm{ord}_p(2)} - 1$ y $p \nmid n / \mathrm{ord}_p(2)$.

Solución. Sea $d = \mathrm{ord}_p(2)$, el orden multiplicativo de $2$ módulo $p$. Entonces $p \mid 2^n - 1 \iff d \mid n$.

Supongamos $d \mid n$, digamos $n = d \cdot m$. Escribimos $2^n - 1 = (2^d)^m - 1^m$. Como $p \mid 2^d - 1$, aplicamos LTE con $a = 2^d$, $b = 1$, primo $p$: $v_p(a^m - b^m) = v_p(a - b) + v_p(m) = v_p(2^d - 1) + v_p(m).$

Entonces: $v_p(2^n - 1) = v_p(2^d - 1) + v_p(n/d)$.

La condición $p^2 \mid 2^n - 1$ equivale a $v_p(2^n - 1) \ge 2$, es decir $v_p(2^d - 1) + v_p(n/d) \ge 2$.

Caso 1: $v_p(2^d - 1) \ge 2$ (p es un "primo de Wieferich respecto a base 2 con exponente $d$"). Entonces $p^2 \mid 2^n - 1$ para todo $n$ múltiplo de $d$.

Caso 2: $v_p(2^d - 1) = 1$ (el caso genérico). Entonces necesitamos $v_p(n/d) \ge 1$, es decir $p \mid n/d$, i.e., $pd \mid n$. La condición $p^2 \mid 2^n - 1$ es equivalente a $pd \mid n$ en este caso. Resultado: los $n$ buscados son exactamente los múltiplos de $pd$ (generalmente) o de $d$ (si $p^2 \mid 2^d - 1$). $\square$