Combo orden + LTE: el patrón estrella

Por qué el combo orden + LTE es tan poderoso

El orden multiplicativo y el LTE son herramientas complementarias que se potencian mutuamente. El orden dice qué primos dividen a una expresión y cuándo. El LTE dice con qué multiplicidad esos primos aparecen.

El patrón estrella funciona así: se tiene una condición $n \mid a^n + b^n$ (o una variante). Primero, usamos el orden de $a \cdot b^{-1}$ módulo un primo $p \mid n$ para deducir que $n$ debe tener cierta forma. Luego, una vez encontrado el primo $p$ candidato, aplicamos el LTE para calcular $v_p(a^n + b^n)$ y ver si puede alcanzar $v_p(n^2)$ o la cota requerida.

Este combo aparece en el famoso problema Cono Sur 2014 (que resolvimos en el Capítulo 4) pero también en docenas de problemas de selecciones nacionales y Shortlists. Quien domine este patrón pasa del rango de "resolvo el 30% de los problemas de teoría de números" al "resolvo el 70%".

Ejemplo estrella: $n \mid a^n - 1$ para $a$ fijo

Sea $a \ge 2$ un entero fijo. Clasificamos todos los $n$ con $n \mid a^n - 1$.

Paso 1 — Orden. Sea $p$ el menor primo divisor de $n$. Entonces $p \mid a^n - 1$, así $\text{ord}_p(a) \mid n$. Como $\text{ord}_p(a) \mid p-1$ y $\gcd(n, p-1) = 1$ (argumento del primo mínimo), concluimos $\text{ord}_p(a) = 1$, es decir $a \equiv 1 \pmod p$.

Paso 2 — LTE. Como $p \mid a - 1$ y $p \nmid a$, $p \nmid 1$, el LTE es aplicable: $v_p(a^n - 1) = v_p(a-1) + v_p(n)$. La condición $n \mid a^n - 1$ exige $v_p(n) \le v_p(a^n-1) = v_p(a-1) + v_p(n)$, lo cual es siempre cierto. Esto confirma que para el primo $p$, la condición no genera contradicción. Pero el Paso 1 ya mostró que si $n > 1$ entonces $n = 1$ (paradoja): la única salida es $n = 1$.

Lección. El orden encontró que $p \mid a - 1$. El LTE confirmó la consistencia. El argumento del primo mínimo cerró la puerta a todo $n > 1$. Los tres ingredientes trabajaron juntos.

El patrón en problemas con $n^2 \mid f(n)$

Los problemas más difíciles piden $n^2 \mid a^n \pm b^n$. Aquí el combo orden + LTE es esencial porque: el orden determina qué primos $p$ dividen a $a^n \pm b^n$, y el LTE calcula si $v_p(a^n \pm b^n) \ge 2 v_p(n)$.

El esquema general: sea $p^s \| n$ (es decir, $p^s \mid n$ pero $p^{s+1} \nmid n$). La condición $n^2 \mid a^n - b^n$ implica $p^{2s} \mid a^n - b^n$, es decir $v_p(a^n - b^n) \ge 2s$. Si $p \mid a - b$: por LTE, $v_p(a^n-b^n) = v_p(a-b) + v_p(n) = v_p(a-b) + s$. Entonces la condición se vuelve $v_p(a-b) + s \ge 2s$, es decir $v_p(a-b) \ge s$. Si $p \nmid a-b$: el orden de $ab^{-1}$ módulo $p$ no es 1, y hay restricciones sobre $n$ para que $p \mid a^n - b^n$.

Este análisis prima a prima, coordinado por el LTE y guiado por el orden, es la técnica definitiva para los problemas de tipo "$n^2 \mid$". Conviene siempre comenzar con los primos pequeños (2, 3, 5) para ver cuáles aparecen, y luego usar el primo mínimo para concluir que no hay otros.

Problema completo: ONEM 2017 estilo — $n^2 \mid 3^n + 2^n$

Problema. Encuentra todos los enteros positivos $n$ tales que $n^2 \mid 3^n + 2^n$.

**Paso 1 — $n$ debe ser impar.** Si $2 \mid n$: $3^n + 2^n \equiv 1 + 0 = 1 \pmod 2$, impar. Pero $n^2$ es par si $n$ es par, y un par no divide a un impar. Contradicción. Entonces $n$ es impar.

**Paso 2 — Primo mínimo de $n$.** Sea $p$ el menor primo divisor de $n$ (y $p \ge 3$ por lo anterior). Entonces $p \mid 3^n + 2^n$, es decir $3^n \equiv -2^n \pmod p$, o $(3 \cdot 2^{-1})^n \equiv -1 \pmod p$. Elevando al cuadrado: $(3 \cdot 2^{-1})^{2n} \equiv 1 \pmod p$. Sea $d = \text{ord}_p(3 \cdot 2^{-1})$. Entonces $d \mid 2n$ pero $d \nmid n$ (pues $(3\cdot 2^{-1})^n \equiv -1 \not\equiv 1$). Luego $d$ es par y $d/2 \mid n$. Por minimalidad de $p$: $d/2 \mid p-1 < p$ implica todos los factores primos de $d/2$ son $< p$, y $d/2 \mid n$ implica todos sus factores primos son $\ge p$. Luego $d/2 = 1$, $d = 2$. Entonces $p \mid (3 \cdot 2^{-1})^2 - 1 = 9 \cdot 4^{-1} - 1 = \frac{5}{4}$... mejor: $d=2$ significa $(3 \cdot 2^{-1})^2 \equiv 1 \pmod p$, es decir $p \mid 9 \cdot (4^{-1}) \cdot 4 - 4 = 9 - 4 = 5$. Entonces $p = 5$.

**Paso 3 — LTE para $p=5$.** Tenemos $5 \mid n$ y $3^n + 2^n = 3^n + 2^n$. Como $n$ es impar y $5 \mid 3 + 2 = 5$: $v_5(3^n + 2^n) = v_5(3+2) + v_5(n) = 1 + v_5(n)$. La condición $5^{2v_5(n)} \mid 3^n+2^n$ requiere $1 + v_5(n) \ge 2 v_5(n)$, es decir $v_5(n) \le 1$. Como $5 \mid n$, $v_5(n) = 1$.

Paso 4 — Ningún otro primo. Para un primo $q \mid n$ con $q \ne 5$, el mismo argumento del Paso 2 daría $q \mid 5$, imposible para $q \ge 3$, $q \ne 5$. Luego $n$ no tiene otros factores primos. Concluimos $n = 5$. Verificación: $3^5 + 2^5 = 243 + 32 = 275 = 25 \cdot 11$. Efectivamente $25 = 5^2 \mid 275$.

Coda: el mapa de herramientas del Capítulo 3

Al finalizar el Capítulo 3, disponemos de tres herramientas interconectadas: el orden multiplicativo (determina la estructura periódica de las potencias y qué primos dividen a $a^n - 1$), las raíces primitivas (garantizan que $(\mathbb{Z}/p\mathbb{Z})^*$ es cíclico, permiten construir índices y resolver ecuaciones potenciales modulares), y el LTE (calcula valuaciones exactas una vez que el orden ha identificado el primo relevante).

El "patrón estrella" es: orden $\to$ primo candidato $\to$ LTE $\to$ condición sobre $v_p(n)$ $\to$ conclusión. Este camino de cinco pasos resuelve la mayoría de los problemas difíciles de divisibilidad con exponentes variables en competencias de nivel Iberoamericana, Cono Sur y parte de IMO.

En el Capítulo 4 profundizamos en el LTE puro (demostraciones y la versión para $p=2$). En el Capítulo 5 (si existe en el módulo) estudiaremos la ley de reciprocidad cuadrática, donde las raíces primitivas vuelven a ser protagonistas. El hilo conductor es siempre el mismo: entender la estructura multiplicativa de $\mathbb{Z}/n\mathbb{Z}$.