LTE para Primos Impares

Teoría

El Lema de Elevación del Exponente (LTE) es una herramienta súper potente en teoría de números que sirve para determinar la potencia de un primo $p$ que divide a una expresión de la forma $a^n - b^n$. Específicamente, relaciona la valuación $p$-ádica de $a^n - b^n$ con las valuaciones de $a-b$ y de $n$. La variante para "primos impares" es la forma más estándar del lema y se aplica cuando $p$ es un primo mayor a 2.

Esta técnica es esencial para resolver ecuaciones diofánticas avanzadas, sobre todo las que tienen términos exponenciales. Sin LTE, determinar la divisibilidad a veces requiere aritmética modular compleja o expansiones binomiales para cada exponente específico. LTE simplifica esto al convertir un problema multiplicativo (que involucra potencias $n$) en un problema aditivo (sumar valuaciones), lo que permite manejar de forma sistemática las restricciones de divisibilidad en problemas de olimpiada.

La intuición detrás del lema viene de la factorización $a^n - b^n = (a-b)(a^{n-1} + a^{n-2}b + \dots + b^{n-1})$. El lema cuantifica cuánta divisibilidad "extra" por $p$ aporta el segundo factor. Para primos impares, esta contribución se comporta de forma muy predecible, dependiendo casi por completo de cuántos factores de $p$ tiene el exponente $n$.

Fórmulas Clave

Usa $v_p(x)$ para denotar la valuación $p$-ádica de un entero $x$ (o sea, el exponente de la potencia más alta de $p$ que divide a $x$).

Teorema (LTE para Primos Impares): Sea $p$ un primo impar, y sean $a$ y $b$ enteros tales que $p \nmid a$ y $p \nmid b$. Si $p \mid (a - b)$, entonces para cualquier entero positivo $n$: $$v_p(a^n - b^n) = v_p(a - b) + v_p(n)$$

Condiciones para usarlo:

1. $p$ es un primo impar ($p \neq 2$).
2. $p \mid (a - b)$ (esto significa que $a \equiv b \pmod p$).
3. $p \nmid a$ y $p \nmid b$ (normalmente esto se cumple si se cumple la condición anterior y $p \nmid a$).

Caso Especial ($p \nmid n$): Si $\gcd(n, p) = 1$, la fórmula se simplifica a: $$v_p(a^n - b^n) = v_p(a - b)$$

Demostración

La idea es demostrar la fórmula $v_p(a^n - b^n) = v_p(a - b) + v_p(n)$ en dos pasos principales.

Paso 1: El caso donde $\gcd(n, p) = 1$. Toma un entero $n$ que no sea divisible por $p$. Factoriza la expresión como: $$a^n - b^n = (a - b)(a^{n-1} + a^{n-2}b + \dots + b^{n-1})$$ Como $p \mid (a - b)$, tienes que $a \equiv b \pmod p$. Ahora analiza el segundo factor módulo $p$: $$a^{n-1} + a^{n-2}b + \dots + b^{n-1} \equiv a^{n-1} + a^{n-2}(a) + \dots + (a)^{n-1} \pmod p$$ $$\equiv \sum_{k=0}^{n-1} a^{n-1} \equiv n \cdot a^{n-1} \pmod p$$ Como $p \nmid n$ (por lo que supusiste) y $p \nmid a$ (por los datos iniciales), el producto $n \cdot a^{n-1}$ no es divisible por $p$. Por lo tanto: $$v_p(a^{n-1} + \dots + b^{n-1}) = 0$$ Así que $v_p(a^n - b^n) = v_p(a - b) + 0 = v_p(a - b) + v_p(n)$, y el teorema se cumple.

Paso 2: El caso donde $n = p$. Supón que $v_p(a - b) = k \ge 1$. Puedes escribir $b = a + m p^k$, donde $p \nmid m$. Sustituye esto en $b^p$: $$b^p = (a + m p^k)^p = a^p + \binom{p}{1} a^{p-1}(m p^k) + \binom{p}{2} a^{p-2}(m p^k)^2 + \dots + (m p^k)^p$$ Reacomoda para obtener $b^p - a^p$: $$b^p - a^p = p \cdot a^{p-1} m p^k + \sum_{j=2}^{p} \binom{p}{j} a^{p-j} (m p^k)^j$$ Analiza la valuación de los términos:

1. El primer término es $a^{p-1} m p^{k+1}$. Su valuación es exactamente $k+1$.
2. Para $j \ge 2$, el término incluye $(p^k)^j = p^{kj}$. Como $k \ge 1$ y $j \ge 2$, entonces $kj \ge 2k$.
   • Específicamente, para $j=2$, el término contiene $\binom{p}{2} p^{2k}$. Como $p$ es impar, $v_p(\binom{p}{2}) = 1$. La valuación total es $1 + 2k$. Como $k \ge 1$, resulta que $1 + 2k > k + 1$.
   • Para $j = p$, el término es $(m p^k)^p$. La valuación es $pk$. Como $p \ge 3$, entonces $pk \ge 3k > k+1$.

Como la valuación del primer término ($k+1$) es estrictamente menor que la valuación de todos los términos que le siguen, la valuación de la suma la determina ese primer término. $$v_p(b^p - a^p) = k + 1 = v_p(a - b) + 1 = v_p(a - b) + v_p(p)$$

Paso 3: Caso General. Sea $n = p^k \cdot m$ donde $\gcd(m, p) = 1$. Usando el Paso 1, maneja el factor $m$: $$v_p(a^n - b^n) = v_p((a^{p^k})^m - (b^{p^k})^m) = v_p(a^{p^k} - b^{p^k})$$ Ahora aplica el Paso 2 repetidamente $k$ veces: $$v_p(a^{p^k} - b^{p^k}) = v_p(a^{p^{k-1}} - b^{p^{k-1}}) + 1 = \dots = v_p(a - b) + k$$ Como $k = v_p(n)$, concluyes que: $$v_p(a^n - b^n) = v_p(a - b) + v_p(