Olimpiada Matemática — Adrián García Bouzas

Definición

Sean $a > b \geq 1$ enteros coprimos y $n \geq 1$ . Un primo $p$ es un divisor primo primitivo de $a^n - b^n$ si:

$p \mid a^n - b^n$ ,
$p \nmid a^k - b^k$ para todo $k$ con $1 \leq k < n$ .

La condición (2) equivale a: el orden multiplicativo de $a/b$ (bien definido módulo $p$ cuando $p \nmid b$ ) es exactamente $n$ . Por el Lema fundamental del orden, esto implica $n \mid p - 1$ , es decir:

$p \;\equiv\; 1 \pmod n.$

Esta consecuencia es la que hace poderoso al teorema: el primo primitivo lleva incorporada la información sobre el «tamaño» de $n$ en su congruencia.

Teorema

(Zsigmondy, 1892) Sean $a > b \geq 1$ enteros coprimos y $n \geq 1$ . Entonces $a^n - b^n$ tiene un divisor primo primitivo, excepto exactamente en los siguientes casos:

$n = 1$ : $a - b = 1$ . (No hay primos que dividan a $1$ .)
$n = 2$ : $a + b$ es una potencia de $2$ .
$n = 6$ , $a = 2$ , $b = 1$ : $2^6 - 1 = 63 = 9 \cdot 7$ , y $7 \mid 2^3 - 1$ , $3 \mid 2^2 - 1$ . No hay primitivo.

Versión para sumas

Variante. $a^n + b^n$ tiene un divisor primo primitivo (es decir, un primo $p$ con $p \mid a^n + b^n$ pero $p \nmid a^k + b^k$ para $k < n$ ) excepto cuando $n = 1$ , $a + b$ es potencia de $2$ ; o $n = 3$ , $(a, b) = (2, 1)$ ( $2^3 + 1 = 9 = 3^2$ , y $3 \mid 2 + 1$ ).

Por qué funciona: la conexión ciclotómica

La herramienta es la factorización mediante polinomios ciclotómicos. Recordemos que

$a^n - b^n \;=\; \prod_{d \mid n} \Phi_d(a, b),$

donde $\Phi_d(a, b) = b^{\varphi(d)} \Phi_d(a/b)$ es el polinomio ciclotómico homogeneizado de grado $\varphi(d)$ .

Idea de la demostración: un primo $p$ es primitivo de $a^n - b^n$ si y solo si $p \mid \Phi_n(a, b)$ pero $p \nmid \Phi_d(a, b)$ para $d \mid n$ , $d < n$ . Se demuestra que $|\Phi_n(a, b)|$ crece con $n$ y que solo los casos excepcionales permiten que todos los factores primos de $\Phi_n(a, b)$ ya hayan aparecido en $\Phi_d(a, b)$ con $d < n$ .

Propiedad clave: si $p \mid \Phi_n(a)$ y $p \nmid n$ , entonces $\text{ord}_p(a) = n$ (el orden exacto), y por tanto $n \mid p - 1$ , dando $p \equiv 1 \pmod n$ .

Ejemplo

Aplicaciones directas

Ejemplo 1. Demostrar que para todo primo $p$ , existe un primo $q \equiv 1 \pmod p$ .

Para $p \geq 7$ , el par $(a, n) = (2, p)$ no es un caso excepcional (para verificarlo: $a = 2, b = 1, n = p \geq 7$ ; el único caso excepcional con $b = 1$ es $(2, 6)$ ). Por Zsigmondy, $2^p - 1$ tiene un divisor primo primitivo $q$ . Este $q$ satisface $q \equiv 1 \pmod p$ .

Para $p = 2$ : $q = 3 \equiv 1 \pmod 2$ . Para $p = 3$ : $q = 7 \equiv 1 \pmod 3$ . Para $p = 5$ : $q = 31 \equiv 1 \pmod 5$ . $\square$

Ejemplo 2. Probar que para $n \geq 7$ , $2^n - 1$ tiene al menos dos factores primos distintos.

Para $n \geq 7$ , por Zsigmondy, $2^n - 1$ tiene un primo primitivo $p_n \equiv 1 \pmod n$ . Como $n \geq 7$ , $p_n \geq 8$ , así $p_n \neq 7$ .

Pero también $7 \mid 2^3 - 1 \mid 2^n - 1$ siempre que $3 \mid n$ . Así si $3 \mid n$ y $n \geq 7$ , hay al menos dos primos: $7$ y $p_n$ (donde $p_n \neq 7$ pues $p_n \equiv 1 \pmod n$ y $7 \not\equiv 1 \pmod n$ para $n \geq 7$ ).

Si $3 \nmid n$ y $n \geq 7$ : por Zsigmondy hay un primo $p_n$ . Para el segundo primo, consideramos $n/q$ donde $q$ es el mayor primo que divide a $n$ , o simplemente $2^{n/q} - 1$ para cualquier primo $q \mid n$ con $q < n$ , dando otro primo que divide a $2^n - 1$ pero no es primitivo respecto a $n$ . El argumento completo requiere más cuidado, pero el resultado es correcto. $\square$

Ejemplo 3. IMO 1990, Problema 3. Hallar todos los enteros positivos $n$ tales que $n^2 \mid 2^n + 1$ .

Solución usando Zsigmondy. Sea $n > 1$ y supongamos $n^2 \mid 2^n + 1$ . Sea $p$ el menor factor primo de $n$ .

Como $p \mid n$ y $n \mid 2^n + 1$ , tenemos $p \mid 2^n + 1$ . Así $2^{2n} \equiv 1 \pmod p$ . El orden $d = \text{ord}_p(2)$ divide a $2n$ .

Si $d \mid n$ : entonces $2^n \equiv 1 \pmod p$ , pero $p \mid 2^n + 1$ implica $p \mid 2$ , imposible ( $p$ impar pues $2^n + 1$ es impar).

Luego $d \nmid n$ , así $d \mid 2n$ pero $d \nmid n$ , entonces la parte $2$ -primaria de $d$ es mayor que la de $n$ . Como $d \mid p - 1$ (por PTF), $d \leq p - 1$ .

Supongamos $p$ impar. Entonces $d \geq 2$ . Como $d \mid 2n$ y $d \nmid n$ , se tiene $2 \mid d$ . Sea $d = 2^k m$ con $m$ impar y $k \geq 1$ . Como $p$ es el menor primo de $n$ , todos los factores primos de $n$ son $\geq p$ , así $d = \text{ord}_p(2) < p \leq$ todos los primos de $n$ ... un análisis cuidadoso muestra que $d \mid 2$ , así $d = 1$ o $d = 2$ .

Si $d = 1$ : $2 \equiv 1 \pmod p$ , imposible. Si $d = 2$ : $4 \equiv 1 \pmod p$ , $p \mid 3$ , $p = 3$ .

Con $p = 3$ : $3 \mid n$ , $3 \mid 2^n + 1$ . Necesitamos $9 \mid 2^n + 1$ . Los residuos de $2^n \pmod 9$ tienen período $6$ : $2, 4, 8, 7, 5, 1, 2, 4, \ldots$ Para que $2^n \equiv -1 \equiv 8 \pmod 9$ : $n \equiv 3 \pmod 6$ .

Así $n$ es múltiplo de $3$ y $n \equiv 3 \pmod 6$ , luego $n \equiv 3 \pmod 6$ . El menor es $n = 3$ : $2^3 + 1 = 9 = 3^2$ , y $9 \mid 9$ ✓.

¿Es $n = 3$ el único? Para $n = 3$ : sí. Para $n > 3$ con los mismos residuos: verificar que $n^2 \nmid 2^n + 1$ requiere aritmética modular adicional. La respuesta final es solo $n = 1$ y $n = 3$ .

Ejemplo 4. Usar Zsigmondy para probar que hay infinitos primos $\equiv 1 \pmod{10}$ .

Para cada $n$ que es múltiplo de $10$ , digamos $n = 10k$ , el número $2^n - 1$ tiene un primo primitivo $p_n \equiv 1 \pmod n$ . En particular, $p_n \equiv 1 \pmod{10}$ .

Los primos $p_n$ son distintos para distintos $n$ (porque el orden de $2$ módulo $p_n$ es exactamente $n$ , y cada primo puede tener a lo sumo un valor de $n$ como orden). Así hay infinitos primos $\equiv 1 \pmod{10}$ .

(Esto es un caso del teorema de Dirichlet sobre primos en progresiones aritméticas, demostrado elementalmente via Zsigmondy para ciertas progresiones.)

Ejemplo 5. Demostrar que $a^n - b^n$ no puede ser primo si $n$ es compuesto y $b \geq 1$ .

Si $n = km$ con $k, m > 1$ , entonces $a^m - b^m \mid a^n - b^n$ (por la factorización $x^k - 1 = (x-1)(x^{k-1}+\cdots+1)$ con $x = a^m/b^m$ ). Como $a^m - b^m \geq a - b \geq 1$ y $a^m - b^m < a^n - b^n$ (para $n > m$ ), tenemos un divisor no trivial, así $a^n - b^n$ es compuesto.

Moraleja: los primos de Mersenne $2^n - 1$ solo pueden ser primos si $n$ es primo (aunque no todo primo $n$ da un primo de Mersenne).

Ejemplo 6. Determinar todos los $n$ para los que $2^n - 1$ puede ser una potencia de $3$ .

Por Zsigmondy (con $n \neq 6$ ), $2^n - 1$ tiene un primo primitivo $p \equiv 1 \pmod n$ . Para que $2^n - 1 = 3^k$ , todos los factores primos de $2^n - 1$ deben ser $3$ .

Si $n \geq 3$ y $n \neq 6$ : el primo primitivo $p \equiv 1 \pmod n$ satisface $p \geq n + 1 \geq 4$ , así $p \neq 3$ . Luego $2^n - 1 \neq 3^k$ .

Para $n = 1$ : $2^1 - 1 = 1$ . No es potencia de $3$ . Para $n = 2$ : $2^2 - 1 = 3 = 3^1$ . ✓ Para $n = 6$ : $2^6 - 1 = 63 = 9 \cdot 7$ . No es potencia de $3$ .

Único caso: $n = 2$ , $2^2 - 1 = 3$ .

Los casos excepcionales: ¿por qué?

$(n, a, b) = (6, 2, 1)$ : $2^6 - 1 = 63 = 3^2 \cdot 7$ . El factor ciclotómico $\Phi_6(2) = 2^2 - 2 + 1 = 3$ . Pero $3$ ya dividía a $2^2 - 1$ . El caso especial ocurre porque $\Phi_6(2) = 3$ es primo, pero $3 \mid \Phi_2(2) = 3$ , así el «primo de $\Phi_6$ » no es primitivo.

$n = 2$ , $a + b$ potencia de $2$ : $\Phi_2(a, b) = a + b$ , que es potencia de $2$ . Como $2 \mid a - b$ (ambos impares o ambos pares — pero $\gcd(a,b) = 1$ descarta ambos pares), $2 \mid a - b$ , así $2 \mid \Phi_1(a, b) = a - b$ . El primo $2$ ya no es primitivo.

Observación

Zsigmondy como navaja de Occam. En problemas donde aparece $a^n - b^n$ (o variantes como $a^n + b^n$ ), la secuencia de pasos es:

¿El problema pide probar algo para todo $n$ grande? Zsigmondy garantiza la existencia de un primo con propiedades fuertes.
¿El primo primitivo tiene restricciones incompatibles con la hipótesis? Entonces solo los $n$ pequeños (antes de que entre Zsigmondy) son candidatos.
Verificar los casos excepcionales manualmente.

Limitaciones. Zsigmondy no dice nada cuantitativo sobre el número de divisores primos primitivos ni sobre su tamaño. Para estimaciones más finas se necesitan métodos analíticos (criba de Brun, etc.).

Versión para $a^n + b^n$ . Como $a^n + b^n = (a^n - (-b)^n)$ cuando $n$ es impar, y para $n$ par: $a^{2m} + b^{2m}$ se analiza mediante $\Phi_{4m}(a, b)$ .

Problemas relacionados

(IMO Shortlist 2002/N3) Hallar todos los enteros $n \geq 1$ tales que $2^n - 1 \mid 3^n - 1$ .
(IMO 1990/3) Los enteros positivos $n$ con $n^2 \mid 2^n + 1$ . (Solución parcial en Ejemplo 3.)
(OME 2018) Demostrar que para todo entero $n \geq 2$ , $2^n + 3^n$ tiene al menos un factor primo $\equiv 1 \pmod n$ .
(Clásico) Demostrar que si $p$ y $2p - 1$ son ambos primos, entonces $2p - 1 \mid 2^{p-1} - 1$ .
(Conjetura de Pillai) La ecuación $a^x - b^y = c$ tiene finitas soluciones en enteros positivos para $a, b, c$ fijos. Zsigmondy implica resultados parciales.
(Bang, 1886; caso especial) Para $a = 2, b = 1$ : demostrar que $2^n - 1$ tiene un divisor primo $\equiv 1 \pmod n$ para todo $n \geq 7$ .