El truco que separa: introducción al LTE

El problema que motiva todo

Antes de ver una sola fórmula, mira este problema. Es de la Olimpiada del Cono Sur, año 2014, problema 5:

Determina todos los enteros positivos $n$ tales que $n^2 \mid 2^n + 1$.

Si tu primer instinto es probar números — $n=1$ funciona, $n=2$ no, $n=3$ funciona — vas bien al inicio. Pero pronto te das cuenta de que $2^{100}$ crece tan rápido que no cabe en ninguna calculadora del mundo. La fuerza bruta colapsa.

Lo que necesitamos no es calcular. Lo que necesitamos es entender con precisión qué potencia de cada primo divide a $2^n+1$. Esa idea —exacta, no aproximada— es el lema de levantamiento del exponente.

El concepto clave: valuación p-ádica

Sea $p$ un primo y $n$ un entero distinto de cero. La **valuación p-ádica de $n$**, que escribimos $v_p(n)$, es el mayor entero $k$ tal que $p^k \mid n$.

En palabras: $v_p(n)$ te dice cuántas veces aparece el primo $p$ en la factorización de $n$.

Ejemplo concreto: $n = 48 = 2^4 \cdot 3$. Entonces $v_2(48) = 4$ (hay cuatro doses) y $v_3(48) = 1$ (hay un solo tres).

El enunciado del LTE (primo impar)

Sea $p$ un primo impar. Sean $a, b$ enteros tales que $p \nmid a$, $p \nmid b$ y $p \mid a-b$. Entonces, para todo $n \ge 1$:

Por qué esto lo cambia todo

Si conoces la valuación de $a-b$ —un número pequeño y manejable— y la valuación de $n$ —también manejable— sabes exactamente la valuación del monstruo $a^n - b^n$. Sin calcular el monstruo. Sin factorizar. Sin sufrir.

En la próxima lección usaremos este lema, paso a paso, para resolver completamente el problema del Cono Sur. Cuando termines esa lección vas a mirar el problema y vas a decir "esto era todo".

Sigan trabajando con paciencia.