LTE para primo impar: demostración + Cono Sur 2014

La hipótesis que no se puede omitir

Antes de escribir una sola línea de la demostración hay que entender por qué el LTE exige $p \mid a - b$. No es un detalle burocrático: es la condición que hace que el monstruo $a^n - b^n$ sea divisible por $p$ en primer lugar.

Si $p \nmid a - b$, entonces $a \not\equiv b \pmod{p}$, y la expresión $a^n - b^n$ puede perfectamente no ser divisible por $p$ en absoluto. Por ejemplo, $5 \nmid 3 - 1$, y efectivamente $5 \nmid 3^7 - 1^7 = 2186 = 2 \cdot 1093$. El lema no tendría nada que decir.

La hipótesis completa es: $p$ primo impar, $p \nmid a$, $p \nmid b$, y $p \mid a - b$. Estas tres condiciones juntas garantizan que $v_p(a^n - b^n) \ge 1$ y le dan al lema su potencia.

El caso base: $n = p$

Comenzamos demostrando el caso más instructivo: $v_p(a^p - b^p) = v_p(a-b) + 1$. Este es el corazón del argumento.

Factorizamos usando la identidad algebraica clásica:

La suma $1 + r + r^2 + \cdots + r^{p-1}$ con $r = a/b$ (pensemos en el cociente) satisface: si $r \equiv 1 \pmod{p}$, entonces cada término $r^k \equiv 1$, y la suma completa es $\equiv p \equiv 0 \pmod{p}$. Formalizamos esto en la demostración.

La valuación del cociente $\Phi_p$

Sea $\Phi_p = a^{p-1} + a^{p-2}b + \cdots + b^{p-1}$ el segundo factor. Necesitamos calcular $v_p(\Phi_p)$ exactamente.

Como $p \mid a - b$, escribimos $a = b + kp$ para algún entero $k$. Entonces $a \equiv b \pmod{p}$. Sustituyendo en $\Phi_p$, cada término $a^{p-1-j} b^j \equiv b^{p-2} \cdot b = b^{p-1} \pmod{p}$. Hay $p$ términos, así que $\Phi_p \equiv p \cdot b^{p-1} \pmod{p^2}$.

Por el Pequeño Teorema de Fermat, $p \nmid b$ implica $b^{p-1} \equiv 1 \pmod{p}$, de modo que $b^{p-1}$ no es divisible por $p$. Concluimos que $v_p(\Phi_p) = 1$.

En consecuencia, $v_p(a^p - b^p) = v_p(a-b) + v_p(\Phi_p) = v_p(a-b) + 1$. El caso $n = p$ queda demostrado.

Extensión al caso general: $v_p(a^n - b^n) = v_p(a-b) + v_p(n)$

Para $n$ general, separamos el factor $p^{v_p(n)}$ de $n$. Escribimos $n = p^s \cdot m$ con $\gcd(m, p) = 1$ y $s = v_p(n) \ge 0$.

Primero tratamos el caso $s = 0$, es decir $p \nmid n$. En este caso, $a^n - b^n = (a - b)(a^{n-1} + \cdots + b^{n-1})$, y la suma del segundo factor tiene $n$ términos cada uno $\equiv b^{n-1} \pmod{p}$. Como $p \nmid n$ y $p \nmid b$, esa suma no es divisible por $p$, así que $v_p(a^n - b^n) = v_p(a-b) = v_p(a-b) + 0 = v_p(a-b) + v_p(n)$. Correcto.

Ahora el paso inductivo: supongamos el resultado válido para $n = p^{s-1} m$ y demostramos para $n = p^s m$. Escribimos $a^{p^s m} - b^{p^s m} = (a^{p^{s-1}m})^p - (b^{p^{s-1}m})^p$. Sea $A = a^{p^{s-1}m}$ y $B = b^{p^{s-1}m}$. Por hipótesis inductiva, $v_p(A - B) = v_p(a-b) + (s-1) + v_p(m) = v_p(a-b) + v_p(n) - 1$. Ahora aplicamos el caso base ($n = p$) a $A$ y $B$: necesitamos $p \mid A - B$, lo cual es cierto por la hipótesis inductiva (ya que $v_p(A-B) \ge 1$). Además $p \nmid A$ y $p \nmid B$ pues $p \nmid a, b$. Entonces:

$v_p(A^p - B^p) = v_p(A-B) + 1 = (v_p(a-b) + v_p(n) - 1) + 1 = v_p(a-b) + v_p(n)$. La demostración está completa.

La versión suma: $v_p(a^n + b^n)$ para $n$ impar

Para los problemas que involucran sumas en lugar de diferencias, existe una versión análoga. Si $p$ es impar, $p \nmid a$, $p \nmid b$, $p \mid a + b$, y $n$ es un entero positivo impar, entonces:

La derivación es inmediata: $a^n + b^n = a^n - (-b)^n$ (porque $n$ es impar). Como $p \mid a - (-b) = a + b$, aplicamos el LTE original a $a$ y $-b$. Obtenemos $v_p(a^n + b^n) = v_p(a + b) + v_p(n)$.

Esta versión es exactamente la que necesitamos para el Cono Sur 2014, donde aparece $2^n + 1 = 2^n + 1^n$ con $n$ impar.

Solución completa: Cono Sur 2014, Problema 5

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

**Paso 1: $n$ debe ser impar.** Si $n$ fuera par, $2^n + 1 \equiv 1 \pmod{2}$, es decir, $2^n + 1$ es impar. Pero entonces $n^2 \mid 2^n + 1$ con $n$ par implicaría que $4 \mid 2^n + 1$, y sin embargo $2^n + 1 \equiv 2 \pmod{4}$ para $n \ge 1$ par. Contradicción. Entonces $n$ es impar.

**Paso 2: Identificar el primo más pequeño de $n$.** Sea $p$ el menor primo que divide a $n$. Entonces $p^2 \mid n^2 \mid 2^n + 1$, en particular $p \mid 2^n + 1$, o sea $2^n \equiv -1 \pmod{p}$. Elevando al cuadrado, $2^{2n} \equiv 1 \pmod{p}$. El orden de 2 módulo $p$ (llamémoslo $d$) divide a $2n$ pero no a $n$ (pues $2^n \equiv -1 \not\equiv 1$). Por lo tanto $d \mid 2n$ y $d \nmid n$, lo que fuerza que $d$ sea par y $d/2 \mid n$. Además $d \mid p-1$ (Fermat). El divisor mínimo de $d/2$ que divide a $n$ debe ser $\ge p$ (por minimalidad de $p$). Pero $d/2 \mid p-1 < p$, así que $d/2 = 1$, dando $d = 2$. Entonces $p \mid 2^2 - 1 = 3$, así que $p = 3$.

Paso 3: Aplicar LTE. Ya sabemos $3 \mid n$ y $n$ es impar. Aplicamos la versión suma del LTE con $a = 2$, $b = 1$, primo $p = 3$: se cumple $3 \mid 2 + 1 = 3$, $3 \nmid 2$, $3 \nmid 1$, y $n$ es impar. Entonces $v_3(2^n + 1^n) = v_3(3) + v_3(n) = 1 + v_3(n)$.

**Paso 4: La condición $n^2 \mid 2^n + 1$ sobre el primo 3.** Como $3 \mid n$, tenemos $3^2 \mid n^2 \mid 2^n + 1$. Es decir, $v_3(2^n + 1) \ge 2 v_3(n)$. Sustituyendo lo que calculamos: $1 + v_3(n) \ge 2\,v_3(n)$, lo que da $v_3(n) \le 1$. Como $3 \mid n$, tenemos $v_3(n) = 1$.

**Paso 5: Ningún otro primo puede dividir a $n$.** Sea $q$ otro primo que divide a $n$ (con $q \ne 3$, $q \ge 5$ por minimalidad). Repitiendo el argumento del Paso 2 para $q$ en lugar de $p$, obtenemos que el orden de 2 módulo $q$ divide $2n$ pero no $n$. El mismo razonamiento produce $q \mid 3$, imposible. Por tanto $n$ no tiene otros factores primos.

Conclusión. $n = 3^{v_3(n)}$ con $v_3(n) \in \{0, 1\}$. Verificamos: $n=1$: $1 \mid 3$. $n=3$: $9 \mid 2^3 + 1 = 9$. Ambos funcionan.