Aplicaciones en IMO y selectivos: ecuaciones con potencias

El patrón de aplicación de Zsygmondy en problemas de olimpiada

En los problemas de olimpiada que involucran potencias, el teorema de Zsygmondy sigue un patrón bastante reconocible de tres pasos:

Paso 1 (el primo primitivo). Identificar que la expresión clave tiene la forma $a^n - b^n$ (o $a^n + b^n$) y aplicar Zsygmondy para garantizar la existencia de un primo primitivo $p$ con $p \equiv 1 \pmod{n}$ (en particular $p \ge n+1$).

Paso 2 (la contradicción o acotación). El primo $p$ divide a una expresión que el problema restringe (e.g., $p \mid k$ para un $k$ pequeño, o $p \mid m^2$ para $m$ acotado). Como $p \ge n+1$, si $k < n+1$ llegamos a una contradicción. Esto acota $n$ o elimina todos los $n$ grandes.

Paso 3 (verificar excepciones). Para los $n$ pequeños y para las excepciones $(n=6, a=2, b=1)$ y $(n=2, a+b=2^k)$, verificar directamente si son solución.

Este patrón es tan potente que muchos problemas del Shortlist de IMO en la categoría N (Teoría de Números) se resuelven con él. A continuación lo aplicamos a cuatro problemas de nivel creciente.

Problema 1: $a^n - 1 = k$ con condiciones de divisibilidad

Problema. Halla todos los pares de enteros positivos $(a, n)$ con $a \ge 2$ tales que $a^n - 1 \mid a^n \cdot n - 1$.

Solución. Sea $d = a^n - 1$. Necesitamos $d \mid a^n \cdot n - 1$. Como $a^n \equiv 1 \pmod{d}$, tenemos $a^n \cdot n \equiv n \pmod{d}$. Entonces la condición es $d \mid n - 1$, es decir $a^n - 1 \mid n - 1$.

Para $n = 1$: $a^1 - 1 = a-1 \mid 0 = n - 1 = 0$. Funciona para cualquier $a \ge 2$.

Para $n \ge 2$: necesitamos $a^n - 1 \le n - 1$ (pues $a^n - 1$ divide a $n-1 > 0$). Pero $a^n - 1 \ge 2^2 - 1 = 3 > 1$ y $n - 1 \ge 1$. La condición $a^n - 1 \le n-1$ requiere $a^n \le n$. Para $a \ge 2$ y $n \ge 2$: $2^2 = 4 > 2$, $2^3 = 8 > 3$, en general $2^n > n$ para $n \ge 2$. Por inducción: $2^2 = 4 > 2$; si $2^k > k$ entonces $2^{k+1} = 2 \cdot 2^k > 2k > k+1$ para $k \ge 2$. Luego $a^n \ge 2^n > n$ para todo $n \ge 2$, contradicción.

Conclusión: todas las soluciones son $(a, 1)$ para cualquier $a \ge 2$.

Nota: Zsygmondy no fue necesario aquí, pero el siguiente problema sí lo requiere.

Problema 2 (IMO 2000, P5 revisitado con Zsygmondy)

Problema. Prueba que para todo entero $n \ge 7$ el número $2^n - 1$ tiene un divisor primo mayor que $n$.

Solución. Para $n \ge 7$ y $(n, 2, 1) \ne (6, 2, 1)$ (que ya está excluido), el teorema de Zsygmondy garantiza que $2^n - 1$ tiene un divisor primo primitivo $p$. Como $\mathrm{ord}_p(2) = n$, por el Pequeño Teorema de Fermat $n \mid p - 1$, luego $p \ge n + 1 > n$.

Para $n = 7$: $2^7 - 1 = 127$ es primo con $127 > 7$. ✓

Para $n = 6$: $2^6 - 1 = 63 = 9 \cdot 7$; el mayor primo es $7 = n+1$. El enunciado pide $> n$, así que $n=6$ no funciona (por eso el problema dice $n \ge 7$).

Para $1 \le n \le 6$: verificación directa. $n=1$: $2^1-1=1$, sin primos. $n=2$: $3>2$. ✓ $n=3$: $7>3$. ✓ $n=4$: $5>4$. ✓ $n=5$: $31>5$. ✓ $n=6$: $\max = 7 = n+1$, no $> n$... ✗

El resultado correcto es: para $n \ge 2$, $n \ne 6$, $2^n-1$ tiene un factor primo $\ge n+1$. Para $n = 6$ el factor primo máximo es exactamente $7 = n+1$. El enunciado del problema dice $> n$, que es $\ge n+1$, así el resultado vale para $n \ge 2$. Zsygmondy da la clave.

Problema 3: clasificar $n$ con $\varphi(a^n - 1) \mid n$

Problema (estilo IMO Shortlist N). Sea $a \ge 2$ un entero fijo. Halla todos los enteros positivos $n$ tales que $\varphi(a^n - 1) \mid n$.

Análisis. Sabemos que $\varphi(a^n - 1) = (a^n-1) \prod_{p \mid a^n-1} (1 - 1/p)$, y que $\varphi(m) \ge \sqrt{m/2}$ para todo $m \ge 1$. Así $\varphi(a^n-1) \ge \sqrt{(a^n-1)/2}$. La condición $\varphi(a^n-1) \mid n$ implica $\varphi(a^n-1) \le n$, luego $\sqrt{(a^n-1)/2} \le n$, es decir $a^n - 1 \le 2n^2$. Para $a = 2$: $2^n - 1 \le 2n^2$; esto solo se cumple para $n \le$ algunos valores pequeños ($n=1$: $1 \le 2$; $n=2$: $3 \le 8$; $n=3$: $7 \le 18$; $n=4$: $15 \le 32$; $n=5$: $31 \le 50$; $n=6$: $63 \le 72$; $n=7$: $127 > 98$). Así para $a=2$, $n \le 6$.

**Aplicando Zsygmondy para $n \ge 3$.** Si $p$ es primo primitivo de $a^n - 1$ (existe para $n \ge 3$, $(a,n) \ne (2,6)$), entonces $p \equiv 1 \pmod{n}$ (pues $\mathrm{ord}_p(a) = n \mid p-1$), así $p-1$ es múltiplo de $n$ y $p-1 \mid \varphi(a^n-1)$ (ya que $p-1 \mid \varphi(p) \mid \varphi(a^n-1)$ por multiplicatividad... no directamente, pero $p \mid a^n-1$ implica $\varphi(p) = p-1 \mid \varphi(a^n-1)/\gcd$ por las propiedades de $\varphi$). Más precisamente: $\varphi(a^n-1) = \prod_{q \mid a^n-1} \varphi(q^{v_q(a^n-1)})$; para el primo primitivo $p$ con $v_p(a^n-1) = 1$ (cuando $p \nmid n$): $\varphi(p) = p-1$ divide a $\varphi(a^n-1)$. Como $n \mid p-1$, tenemos $n \mid \varphi(a^n-1)$. La condición $\varphi(a^n-1) \mid n$ junto con $n \mid \varphi(a^n-1)$ dan $\varphi(a^n-1) = n$. Esto exige que $a^n - 1$ sea un "número con $\varphi$ pequeño", lo que es muy restrictivo.

**Conclusión para $a = 2$.** La condición $\varphi(2^n-1) = n$ para $n \ge 3$: revisando los $n \le 6$: $n=3$: $\varphi(7)=6 \ne 3$. $n=4$: $\varphi(15)=\varphi(3)\varphi(5)=2\cdot 4=8 \ne 4$. $n=6$: $\varphi(63)=\varphi(9)\varphi(7)=6\cdot 6=36 \ne 6$. Para $n=1$: $\varphi(1)=1=n$. ✓ $n=2$: $\varphi(3)=2=n$. ✓ En general, para $a=2$, las únicas soluciones son $n=1$ y $n=2$. El argumento de Zsygmondy elimina $n \ge 3$ de forma elegante.

Problema 4: ecuaciones de la forma $a^m - b^m = c^k$

Problema (IMO Shortlist estilo). Encuentra todos los enteros $n \ge 1$ para los que $2^n + 1$ es potencia de un primo.

Solución. Queremos $2^n + 1 = p^k$ para algún primo $p$ y $k \ge 1$.

**Caso $n$ par:** $n = 2m$, entonces $2^{2m} + 1 = (2^m)^2 + 1$. No es fácilmente factorizable.

**Caso $n$ impar:** $2^n + 1 = 2^n - (-1)^n$ ... si $n = ab$ con $a$ impar $> 1$, entonces $(2^b)^a + 1^a = (2^b+1)((2^b)^{a-1} - (2^b)^{a-2} + \cdots + 1)$. Para que $2^n+1$ sea potencia de primo, el segundo factor debe ser $1$ o una potencia del mismo primo. El segundo factor $> 1$ para $a \ge 3$, luego $2^n+1$ tiene al menos dos factores distintos mayores que $1$, contradiciendo ser potencia de primo. Entonces $n$ no puede tener un divisor impar $> 1$, es decir $n$ debe ser potencia de $2$.

**Caso $n = 2^s$:** $2^{2^s} + 1$ son los números de Fermat $F_s = 2^{2^s}+1$. $F_0=3$, $F_1=5$, $F_2=17$, $F_3=257$, $F_4=65537$, todos primos. $F_5 = 4294967297 = 641 \times 6700417$, no primo. No se conoce ningún $F_s$ primo para $s \ge 5$. Los problemas de olimpiada típicamente preguntan por $n$ pequeños o piden demostrar que $n$ es potencia de $2$ (sin determinar exactamente cuáles dan primo).

**Rol de Zsygmondy para $2^n+1$.** La versión suma del teorema (Birkhoff-Vandiver): $a^n + b^n$ tiene un divisor primo primitivo para $n \ge 2$ excepto $(a,b,n) = (2,1,3)$: $2^3+1^3=9=3^2$, y $3 \mid 2^1+1=3$, sin primo nuevo. Para $2^{2^s}+1 = 2^{2^s} - (-1)^{2^s}$... mejor escribirlo como $2^n + 1$ con $n$ potencia de $2$. Si $n = 2^s$ con $s \ge 2$, $2^n + 1 = 2^{2m} + 1$ con $m = 2^{s-1}$ par, y aquí la versión par del teorema para sumas no aplica directamente. El argumento es que todo factor primo $p$ de $2^{2^s}+1$ satisface $\mathrm{ord}_p(2) = 2^{s+1}$ (pues $2^{2^s} \equiv -1 \pmod{p}$, así $2^{2^{s+1}} \equiv 1$ y $2^{2^s} \not\equiv 1$), luego $p \equiv 1 \pmod{2^{s+1}}$. Para $F_s$ ser potencia de primo se necesita que todos estos factores sean iguales, lo que es una condición muy especial.

El teorema de Zsygmondy en el problema IMO 2000 P5

El Problema 5 de IMO 2000 es un ejemplo emblemático donde Zsygmondy (o el argumento de orden multiplicativo que lo subyace) es central.

IMO 2000 P5. Halla todos los enteros positivos $n$ tales que $n^2 \mid 2^n - 1$.

Solución. Claramente $n=1$ funciona ($1 \mid 1$). Para $n \ge 2$: sea $p$ el primo mínimo de $n$. Entonces $p \mid n^2 \mid 2^n-1$, así $2^n \equiv 1 \pmod{p}$ y $\mathrm{ord}_p(2) \mid n$. Sea $d = \mathrm{ord}_p(2)$; entonces $d \mid p-1$ y $d \mid n$. Como $p$ es el primo mínimo de $n$, todo divisor de $n$ es $\ge p$ o $= 1$. Pero $d \mid p-1 < p$, así $d$ debe ser $1$ (ya que $d \mid n$ y $d < p$ implica $d$ no tiene factores primos de $n$, luego $d = 1$). Entonces $2^1 \equiv 1 \pmod{p}$, i.e., $p \mid 1$: imposible. Luego no existe $n \ge 2$ con la propiedad.

La conexión con Zsygmondy: el argumento del orden multiplicativo de $2$ módulo $p$ (el primo mínimo de $n$) es exactamente el argumento que subyace a la demostración de Zsygmondy cuando se dice "si $2^n-1$ tuviera solo primos que ya aparecen en $2^k-1$ para $k < n$..." El primo mínimo de $n$ juega el rol del primo primitivo en reversa.

El patrón general. Cuando el problema pide $n^2 \mid f(n)$ con $f(n) = a^n - b^n$, el argumento es: tomar el primo mínimo $p$ de $n$, notar que $p \mid a^n - b^n$ implica $\mathrm{ord}_p(ab^{-1}) \mid n$ y $\mid p-1$; la minimalidad de $p$ fuerza $\mathrm{ord}_p(ab^{-1}) = 1$, es decir $a \equiv b \pmod{p}$. Pero si $p \mid a-b$, el LTE puede usarse: $v_p(a^n-b^n) = v_p(a-b) + v_p(n)$. La condición $n^2 \mid a^n-b^n$ implica $2v_p(n) \le v_p(a-b) + v_p(n)$, es decir $v_p(n) \le v_p(a-b)$. Esto acota $v_p(n)$ y en consecuencia acota $n$ o fuerza $n = 1$. Zsygmondy cierra el argumento cuando $a \not\equiv b \pmod{p}$.