Excepciones al teorema de Zsygmondy y por qué importan

Las excepciones no son errores: son la clave de los casos difíciles

En olimpiadas, cuando aplicas un teorema para concluir que algo no existe salvo en ciertos casos, precisamente esos "ciertos casos" son los que el problema te pide encontrar. Las excepciones al teorema de Zsygmondy son exactamente así: no son obstáculos, son los candidatos a solución.

Muchos problemas del estilo "encuentra todos los $n$ tales que..." tienen como respuesta los valores de $n$ correspondientes a las excepciones de Zsygmondy. Entender por qué ocurren —no solo memorizarlas— te permite identificarlas rápidamente durante una competencia.

Recordatorio del teorema: para $a > b \ge 1$, $\gcd(a,b) = 1$, $n \ge 1$, las únicas excepciones a la existencia de primo primitivo de $a^n - b^n$ son:

(E1) $n = 1$: $a^1 - b^1 = a - b$, que puede ser 1 (si $a - b = 1$) o un entero sin factores primos "primitivos" porque simplemente no hay término anterior con el que comparar... en realidad $n=1$ siempre tiene un primo primitivo salvo $a-b=1$.

(E2) $n = 2$, $a + b = 2^k$: aquí $a^2 - b^2 = (a-b)(a+b)$ y $a + b = 2^k$, así todos los factores impares de $a^2-b^2$ ya dividen a $a - b = a^1 - b^1$.

(E3) $a = 2$, $b = 1$, $n = 6$: $2^6 - 1 = 63 = 3^2 \cdot 7$, y $3 \mid 2^2-1$ y $7 \mid 2^3-1$, así no hay primo nuevo.

Clasificación completa de las excepciones

Teorema (Clasificación completa de Zsygmondy). Sean $a > b \ge 1$, $\gcd(a,b)=1$, $n \ge 1$. Entonces $a^n - b^n$ NO tiene divisor primo primitivo si y solo si se cumple uno de los siguientes casos:

**(C1) $a - b = 1$, $n = 1$.** Entonces $a^1 - b^1 = 1$, que no tiene factores primos.

**(C2) $n = 2$, $a + b$ es una potencia de $2$ (incluyendo $2^1 = 2$).** Aquí $a^2 - b^2 = (a-b)(a+b)$ con $a+b = 2^s$. Como $a-b$ es impar (pues $a,b$ tienen misma paridad dado que $a+b$ es potencia de 2 $\ge 2$... espera: si $a+b=2^s$ con $a,b$ con $\gcd(a,b)=1$ y $a > b \ge 1$, entonces $a,b$ deben tener paridades distintas si $s=1$, o misma paridad si $s \ge 2$). En general, los factores impares de $a^2-b^2$ son los mismos que los de $a-b$, y $a-b = a^1-b^1$, así no hay primo primitivo para $n=2$.

**(C3) $a = 2$, $b = 1$, $n = 6$.** Como vimos, $2^6 - 1 = 63 = 3^2 \cdot 7$ y los únicos primos son $3 \mid 2^2-1$ y $7 \mid 2^3-1$.

Demostración de (C2) con la factorización ciclotómica. $\Phi_2(a,b) = a + b = 2^s$. Todos los factores primos de $\Phi_2(a,b)$ son iguales a $2$. Pero $2 \mid a^1 - b^1 = a-b$ si $a,b$ tienen la misma paridad... hmm, si $a+b=2^s$ y $\gcd(a,b)=1$, entonces $a$ y $b$ son de distintas paridades (si $s=1$) o ambos impares (imposible con $\gcd(a,b)=1$ si $s \ge 2$ y ambos impares...): en realidad si $a+b=2^s$, como $\gcd(a,b)=1$, los únicos primos de $a+b$ son potencias de $2$. El primo $2$ divide a $a-b$ si y solo si $a$ y $b$ tienen la misma paridad; si $a+b=2^s \ge 4$, ambos son impares (pues si uno es par y $\gcd(a,b)=1$, el otro es impar y su suma no sería potencia de $2$ salvo $2$). Entonces ambos son impares, $a - b$ es par, y el único primo de $a+b = 2^s$ es $2$, que también divide a $a - b$. Luego $\Phi_2(a,b) = a+b$ no aporta primo primitivo.

Por qué $n=6$, $a=2$, $b=1$ es especial

La excepción $(a,b,n) = (2,1,6)$ parece arbitraria, pero tiene una explicación profunda. Calculemos $\Phi_6(2,1) = 2^2 - 2 + 1 = 3$. Entonces $3 \mid \Phi_6(2,1)$. Ahora, $3$ es primitivo de $\Phi_6$ si y solo si $\mathrm{ord}_3(2) = 6$. Pero $\mathrm{ord}_3(2) = 2$ (pues $2^2 = 4 \equiv 1 \pmod{3}$). Entonces $3 \mid 2^2 - 1 = 3$, es decir, $3$ divide a $a^2 - b^2$. El primo $3$ no es primitivo de $a^6 - b^6$.

¿Por qué el orden de $2$ módulo $3$ es $2$ y no $6$? Porque $3 \mid \Phi_6(2,1) = 3$ y simultáneamente $3 \mid \Phi_2(2,1) = 3$. Esto ocurre porque $\Phi_6(x) = \Phi_2(-x)$... no exactamente, pero $\Phi_6(x) = x^2 - x + 1$ y $\Phi_3(x) = x^2 + x + 1$ y $\Phi_6(x) = \Phi_3(-x)$. Para $x = 2$: $\Phi_6(2) = 3 = \Phi_3(-2)$. Cuando $p \mid \Phi_n(a,b)$ y $p \mid \Phi_d(a,b)$ para algún $d \mid n$, $d < n$, ocurre que $p \mid n/d$ (esto es un resultado estándar de la teoría ciclotómica). Para $(2,1,6)$: $p = 3$ divide $\Phi_2(2,1) = 3$ y $\Phi_6(2,1) = 3$. Aquí $6/2 = 3 = p$. Exactamente el caso especial donde el "pequeño" factor ciclotómico absorbe al grande.

Regla práctica. La excepción de Zsygmondy para $n=6, a=2, b=1$ es la única excepción "genuinamente excepcional" en el rango $n \ge 3$ (la de $n=2$ con $a+b=2^k$ es una familia infinita pero estructuralmente diferente). Para cualquier otro par $(a,b,n)$ con $n \ge 3$ y $(a,b,n) \ne (2,1,6)$, el teorema garantiza la existencia de un primo primitivo.

**Verificación completa de $(2,1,6)$:** Los divisores de $6$ son $1,2,3,6$. Los factores ciclotómicos: $\Phi_1(2,1)=1$, $\Phi_2(2,1)=3$, $\Phi_3(2,1)=7$, $\Phi_6(2,1)=3$. Así $2^6-1=63 = 1\cdot 3\cdot 7\cdot 3 = 63$. Los primos de $\Phi_6(2,1) = 3$ también dividen a $\Phi_2(2,1) = 3$ (correspondiente a $d=2 < 6$), entonces el primo $3$ no es primitivo de $2^6 - 1$.

Ejemplo trabajado: $2^n - 1$ tiene primo primitivo excepto $n = 1, 2, 6$

Proposición. Para $a = 2$, $b = 1$: $2^n - 1$ tiene un divisor primo primitivo para todo $n \ge 1$ excepto $n = 1$ (donde $2^1-1=1$) y $n = 6$ (donde $2^6-1=63$ no tiene primo nuevo). Para $n = 2$: $2^2-1=3$ es primo y $3 \nmid 2^1-1=1$, así $3$ es primitivo.

Demostración. Para $a=2, b=1$, la excepción (C2) requiere $a+b = 3 = 2^k$; pero $3$ no es potencia de $2$, así (C2) no aplica para ningún $n \ge 2$. La excepción (C3) aplica solo para $n=6$. La excepción (C1) aplica para $n=1$ (pues $2^1-1=1$).

Entonces para $n \ge 2$, $n \ne 6$, $2^n - 1$ tiene siempre un divisor primo primitivo.

Tabla de los primeros valores:

$n=2$: $2^2-1=3$. Primo primitivo: $3$ (pues $3 \nmid 1 = 2^1-1$). ✓

$n=3$: $2^3-1=7$. Primo primitivo: $7$ (pues $7 \nmid 1$ ni $7 \nmid 3$). ✓

$n=4$: $2^4-1=15=3\cdot 5$. Primo primitivo: $5$ (pues $5 \nmid 1, 3, 7$). ✓

$n=5$: $2^5-1=31$. Primo primitivo: $31$. ✓

$n=6$: $2^6-1=63=9\cdot 7$. Los únicos primos son $3$ y $7$. $3 \mid 2^2-1$ y $7 \mid 2^3-1$. Sin primo primitivo. ✗ (excepción)

$n=7$: $2^7-1=127$ (primo). Primo primitivo: $127$. ✓

$n=8$: $2^8-1=255=3\cdot 5\cdot 17$. Primo primitivo: $17$ (pues $17 \nmid 2^k-1$ para $k < 8$: $\mathrm{ord}_{17}(2)=8$). ✓

Cómo usar esto en olimpiadas. Si un problema involucra $2^n - 1$ y pide "probar que tiene un factor primo mayor que $n$", el primo primitivo $p$ satisface $p \ge n+1$ (pues $p \equiv 1 \pmod{n}$), así $p \ge n+1 > n$. La excepción $n=6$ puede hacer que el resultado sea falso para $n=6$: $2^6-1=63=9\cdot 7$, y todos los factores primos ($3, 7$) son menores que $6+1=7$... en realidad $7 = 6+1$, así el primo $7$ satisface $p = n+1$, no $p > n$. El enunciado correcto sería $p \ge n+1$, que se cumple incluso para $n=6$ (con $p=7$).

Las excepciones como fronteras en problemas IMO

El patrón que se repite en problemas olímpicos: aplicar Zsygmondy para concluir que $a^n - b^n$ tiene un primo primitivo $p$ (grande, $\ge n+1$), y ese primo impone una restricción tan fuerte que solo puede cumplirse para $n$ pequeños o para los $n$ de las excepciones.

Ejemplo modelo. Problema: "Halla todos los $n \ge 1$ tales que $n \mid 2^n - 1$." Si $n \ge 2$ y $p$ es el primo mínimo que divide a $n$, entonces $p \mid n \mid 2^n - 1$, así $\mathrm{ord}_p(2) \mid n$. El orden $\mathrm{ord}_p(2)$ también divide a $p-1$ (por Fermat). El primo mínimo $p$ de $n$ implica $\gcd(n, p-1) = 1$ o más delicadamente: los divisores propios de $p-1$ son menores que $p$, y el menor primo de $n$ es $p$, así si $q \mid p-1$ y $q \mid n$ entonces $q = p$ (imposible pues $q \mid p-1 < p$). Luego $\gcd(n, p-1) = 1$, lo que fuerza $\mathrm{ord}_p(2) = 1$, es decir $2 \equiv 1 \pmod{p}$, o sea $p \mid 1$: imposible. Entonces no existe primo $p$ que divida a $n$, luego $n = 1$. La única solución es $n = 1$.

La excepción de Zsygmondy para $n=6$ aparece así: si el problema fuera "$n \mid 2^n + 1$" en vez de "$n \mid 2^n - 1$", el análisis es diferente y las excepciones de Zsygmondy para sumas juegan un rol. Conocerlas permite anticipar cuándo el argumento falla.

Regla mnemotécnica. Al aplicar Zsygmondy, siempre hay que verificar si el problema cae en la excepción $(2, 1, 6)$ y si $n = 2$ con $a+b$ potencia de $2$. Si no cae, el primo primitivo existe y tiene las propiedades fuertes que necesitamos.