El teorema de Zsygmondy: primos primitivos de $a^n - b^n$

El problema que motiva: ¿siempre aparecen primos nuevos?

Considera la sucesión $a^1 - b^1,\; a^2 - b^2,\; a^3 - b^3, \ldots$ para enteros $a > b \ge 1$ con $\gcd(a,b)=1$. Por ejemplo, con $a=2$, $b=1$:

$2^1 - 1 = 1,\quad 2^2-1=3,\quad 2^3-1=7,\quad 2^4-1=15=3\cdot 5,\quad 2^5-1=31,\quad 2^6-1=63=9\cdot 7.$

Observa que $2^3-1=7$ introduce el primo $7$ por primera vez. El primo $5$ aparece por primera vez en $2^4-1$. El primo $31$ en $2^5-1$. Todos son "primos nuevos" para su $n$ respectivo.

¿Es siempre así? ¿Para cada $n$ suficientemente grande, $a^n - b^n$ tiene un factor primo que no aparecía antes? La respuesta es sí —casi siempre— y ese es el teorema de Zsygmondy de 1892.

Este resultado tiene consecuencias sorprendentes en olimpiadas: cuando el problema dice "para todo $n$, el número $f(n)$ es compuesto" o "hallar todas las $n$ con tal propiedad", el teorema de Zsygmondy a menudo da la llave maestra.

Definición: primo primitivo de $a^n - b^n$

Definición. Sea $a > b \ge 1$ con $\gcd(a,b) = 1$. Un primo $p$ es un **primo primitivo de $a^n - b^n$ (también llamado divisor primo primitivo**, en inglés *primitive prime divisor*) si:

(1) $p \mid a^n - b^n$,

(2) $p \nmid a^k - b^k$ para todo $1 \le k < n$.

En términos del orden multiplicativo: la condición (1) dice $a^n \equiv b^n \pmod{p}$, es decir $(ab^{-1})^n \equiv 1 \pmod{p}$ (donde $b^{-1}$ es el inverso de $b$ módulo $p$, que existe pues $\gcd(b,p)=1$ dado que $p \nmid b$). La condición (2) dice que $n$ es el menor entero positivo con esta propiedad. Por lo tanto:

**Un primo $p$ es primitivo de $a^n - b^n$ si y solo si $\mathrm{ord}_p(ab^{-1}) = n$.**

Por el pequeño teorema de Fermat, $n \mid p - 1$. En particular $p \equiv 1 \pmod{n}$, lo que implica $p \ge n + 1$.

Esta cota $p \ge n+1$ es fundamental: dice que el primo primitivo es siempre "grande" en relación con $n$.

Enunciado del teorema de Zsygmondy

Teorema (Zsygmondy, 1892; Birkhoff-Vandiver, 1904). Sean $a > b \ge 1$ enteros con $\gcd(a,b) = 1$. Entonces $a^n - b^n$ tiene un divisor primo primitivo para todo entero $n \ge 3$, con las siguientes excepciones:

(E1) $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 primo primitivo.

(E2) $n = 2$, $a + b$ es una potencia de 2 (entonces $a^2 - b^2 = (a-b)(a+b)$ y todos sus factores primos impares dividen a $a - b = a^1 - b^1$).

(E3) $a = 2$, $b = 1$, $n = 1$: $2^1 - 1 = 1$, sin factores primos.

Para el caso $a^n + b^n$ (sumas), la versión análoga de Birkhoff-Vandiver establece que $a^n + b^n$ tiene un divisor primo primitivo (primo $p$ con $p \mid a^n + b^n$ pero $p \nmid a^k + b^k$ para $0 < k < n$ y $p \nmid a^k - b^k$ para $k < 2n$) para todo $n \ge 2$, con excepciones análogas.

La hipótesis $n \ge 3$ no es arbitraria: para $n = 2$, la excepción (E2) ocurre cuando $a + b = 2^k$, que incluye infinitos casos (p.ej. $a=3, b=1$: $a^2-b^2 = 8 = 2^3$, el único primo es $2$ que ya divide a $2^1-1=1$... espera, $2 \nmid 1$. En realidad $2 \mid a^2-b^2 = 8$ y $2 \nmid a-b = 2$... sí divide. Revisión: para $a=3, b=1$: $a-b=2$, $a+b=4=2^2$. $a^2-b^2 = 8 = 2^3$. El único primo es $2$, que divide a $a-b=2 = a^1-b^1$. Así no hay primo primitivo para $n=2$ en este caso.)

Estrategia de la demostración

La demostración completa del teorema de Zsygmondy es técnicamente extensa, pero la idea central es elemental y hermosa. Presentamos la estrategia principal.

Paso 1: El orden multiplicativo como guía. Sea $d(p) = \mathrm{ord}_p(ab^{-1})$ para cada primo $p \mid a^n - b^n$. Si $d(p) = n$ para algún $p$, ese $p$ es el primo primitivo buscado. Si para todos los primos $p \mid a^n - b^n$ se tiene $d(p) < n$, entonces $d(p) \mid n$ y $d(p) \mid n-1$... no, $d(p) \mid n$ (pues $p \mid a^n - b^n$ implica $d(p) \mid n$) y $d(p) \ne n$ significaría $d(p) \mid m$ para algún divisor propio $m$ de $n$, luego $p \mid a^m - b^m$.

Paso 2: Comparar tamaños. Supongamos que todos los primos de $a^n - b^n$ también dividen a $a^m - b^m$ para algún $m < n$ (divisor propio de $n$). Entonces $a^n - b^n$ y $\prod_{m \mid n, m < n} (a^m - b^m)$ comparten todos los factores primos. Usando el LTE, podemos calcular exactamente cuántas veces cada primo $p$ divide a $a^n - b^n$ versus $\prod_{m < n, m \mid n} (a^m - b^m)$. Si $a^n - b^n > \prod_{m < n, m \mid n} (a^m - b^m)^{\text{exp max}}$, la hipótesis es imposible.

Paso 3: La fórmula cíclica. La función clave es el polinomio ciclotómico $\Phi_n(a,b) = \prod_{\gcd(k,n)=1,\, 1 \le k \le n} (a - \zeta^k b)$ donde $\zeta = e^{2\pi i/n}$. Este es un entero (por el lema de Gauss para polinomios) y satisface $a^n - b^n = \prod_{d \mid n} \Phi_d(a,b)$. El primo primitivo de $a^n - b^n$ es exactamente el primo que divide a $\Phi_n(a,b)$ pero no a ningún $\Phi_d(a,b)$ con $d < n$. La demostración reduce a mostrar que $\Phi_n(a,b)$ tiene algún factor primo primitivo, lo que se hace estimando su tamaño: $\Phi_n(a,b) \ge (a-b)^{\phi(n)} \to \infty$ con $n$, superando a los factores "viejos" que podrían absorberlo.

El rol del LTE. Para el primo primitivo $p$ se tiene que $v_p(a^n - b^n) = v_p(a-b) + v_p(n) = 0 + v_p(n)$ si $p \nmid a-b$. Pero si $p$ es primitivo y $p \nmid a-b$, entonces $p \mid a^n - b^n$ sin $p \mid a - b$. El LTE en su forma para $p \nmid a-b$ dice que $v_p(a^n - b^n) = v_p(\Phi_n(a,b)) + \text{(contribuciones de divisores de } n\text{)}$; si $p$ es primitivo, la única contribución viene del factor ciclotómico $\Phi_n(a,b)$, y el LTE garantiza $v_p(\Phi_n(a,b)) = 1$ cuando $p \nmid n$.

El LTE y la valuación del primo primitivo

Proposición clave. Sea $p$ un primo primitivo de $a^n - b^n$ (con $p \nmid n$). Entonces $v_p(a^n - b^n) = 1$.

Demostración. Como $p$ es primitivo, $\mathrm{ord}_p(ab^{-1}) = n$. En particular $p \nmid a - b$ (si $p \mid a-b$ entonces $ab^{-1} \equiv 1 \pmod{p}$, así $\mathrm{ord}_p(ab^{-1}) = 1 \ne n$ para $n > 1$). Por el LTE (versión sin $p \mid a-b$): como $p \nmid a-b$ y $p \mid a^n - b^n$, el LTE no se aplica directamente en su forma estándar; en cambio, usamos la factorización cíclica. Tenemos $a^n - b^n = \Phi_n(a,b) \cdot \prod_{d \mid n, d < n} \Phi_d(a,b)$. El primo $p$ no divide a ningún $\Phi_d(a,b)$ con $d < n$ (pues si lo hiciera, $p$ dividiría $a^d - b^d$, contradiciendo la primitividad). Por lo tanto, $v_p(a^n - b^n) = v_p(\Phi_n(a,b))$.

Ahora, $\Phi_n(a,b) \equiv \Phi_n(1,1) \cdot (\text{término de orden} \ge 1 \text{ en } a-1, b-1) \pmod{p}$... mejor argumento: como $p \mid \Phi_n(a,b)$ y $p$ es primo, consideramos $\Phi_n(x) = \prod_{\gcd(k,n)=1}(x - \zeta^k)$ evaluado en $x = ab^{-1}$. La derivada $\Phi_n'(x) = \Phi_n(x) \cdot \sum_{\gcd(k,n)=1} \frac{1}{x - \zeta^k}$; en $x = ab^{-1}$, solo el factor con $\zeta^k = 1$ (i.e., $k = 0$... pero $\gcd(0,n) = n \ne 1$ para $n > 1$) contribuiría un cero. En realidad, $x = ab^{-1}$ es una raíz simple de $\Phi_n$ (pues las raíces de unidad primitivas son simples), luego $v_p(\Phi_n(a,b)) = 1$ cuando $p \nmid n$ (ya que $p \nmid \Phi_n'(ab^{-1})$ si $p \nmid n$, lo cual se verifica por la fórmula $x\Phi_n'(x)/\Phi_n(x) = \sum_{d\mid n} \mu(n/d) \frac{d \cdot x^d}{x^d-1}$, que es un entero módulo $p$ no divisible por $p$ cuando $p \nmid n$).

El resultado $v_p(a^n - b^n) = 1$ para el primo primitivo $p$ con $p \nmid n$ es la clave de muchas aplicaciones olímpicas: nos dice que el primo primitivo aparece exactamente una vez en la factorización de $a^n - b^n$.

Identidad de los polinomios ciclotómicos y el primo primitivo

Resumamos la estructura que hace funcionar el teorema. La identidad fundamental es:

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

donde $\Phi_d(a,b) = b^{\phi(d)} \Phi_d(a/b)$ es el polinomio ciclotómico $d$-ésimo evaluado en $(a,b)$. Los primeros valores son: $\Phi_1(a,b) = a - b$, $\Phi_2(a,b) = a + b$, $\Phi_3(a,b) = a^2 + ab + b^2$, $\Phi_4(a,b) = a^2 + b^2$, $\Phi_6(a,b) = a^2 - ab + b^2$.

Ejemplos concretos: $a^6 - b^6 = (a-b)(a+b)(a^2+ab+b^2)(a^2-ab+b^2)$. Para $a=2, b=1$: $63 = 1 \cdot 3 \cdot 7 \cdot 3 = 63$. Los factores son $\Phi_1(2,1)=1$, $\Phi_2(2,1)=3$, $\Phi_3(2,1)=7$, $\Phi_6(2,1)=3$. El factor $\Phi_6 = 3$ no introduce primo nuevo (el primo $3$ ya estaba en $\Phi_2$). Esta es la excepción $(2,1,6)$.

La estimación de tamaño. Para $n \ge 3$ (excluyendo las excepciones), $\Phi_n(a,b) \ge (a-b)^{\phi(n)} \ge 1$ y de hecho $\Phi_n(a,b) \ge a^{\phi(n)} - b^{\phi(n)} \cdot C$ para alguna constante $C$. El punto crucial es que $\Phi_n(a,b) > 1$ para $n \ge 3$ y $(a,b) \ne (2,1)$ o $n \ne 6$: si $\Phi_n(a,b) > 1$, tiene algún factor primo, y ese factor no puede dividir a $a^d - b^d$ para $d < n$ (pues dividiría entonces a $\gcd(a^n-b^n, a^d-b^d) = a^{\gcd(n,d)}-b^{\gcd(n,d)}$, y el análisis de cuándo $\Phi_n(a,b)$ puede ser dividible por un primo "viejo" se reduce a los casos excepción).

La fuerza del teorema de Zsygmondy en olimpiadas es que convierte la pregunta "¿existe un primo que divida a $a^n-b^n$ pero no a $a^k-b^k$ para $k<n$?" en una afirmación que podemos usar como herramienta, sin necesidad de encontrar explícitamente ese primo.

Primer problema resuelto: $\gcd(2^m - 1, 2^n - 1) = 2^{\gcd(m,n)} - 1$

Este resultado clásico ilustra el poder del primo primitivo sin necesitar el teorema completo, pero abre la puerta para verlo.

Proposición. Para todos los enteros positivos $m, n$: $\gcd(2^m - 1, 2^n - 1) = 2^{\gcd(m,n)} - 1$.

Demostración. Sea $d = \gcd(m,n)$. Claramente $2^d - 1 \mid 2^m - 1$ y $2^d - 1 \mid 2^n - 1$ (pues $d \mid m$ y $d \mid n$), así $2^d - 1 \mid \gcd(2^m-1, 2^n-1)$.

Para el otro lado, sea $p$ un primo que divide a $\gcd(2^m-1, 2^n-1)$. Entonces $2^m \equiv 1 \pmod{p}$ y $2^n \equiv 1 \pmod{p}$. Sea $e = \mathrm{ord}_p(2)$; entonces $e \mid m$ y $e \mid n$, luego $e \mid \gcd(m,n) = d$. Por lo tanto $p \mid 2^e - 1 \mid 2^d - 1$.

Hemos demostrado que todo primo que divide al $\gcd(2^m-1, 2^n-1)$ también divide a $2^d - 1$. Para comparar las potencias exactas: si $v_p(2^m-1) = v_p(2-1) + v_p(m) = 0 + v_p(m)$ cuando $p \mid 2-1 = 1$... eso no aplica (LTE requiere $p \mid a-b = 1$, imposible para primo $p$). Usamos en cambio: $v_p(2^m-1) = v_p(2^e-1) + v_p(m/e)$ por LTE aplicado a $2^{m/e \cdot e} - 1$ con base $A = 2^e$, $B = 1$, y $p \mid A - B = 2^e-1$. Así $v_p(\gcd(2^m-1,2^n-1)) = \min(v_p(2^m-1), v_p(2^n-1)) = v_p(2^e-1) + \min(v_p(m/e), v_p(n/e)) = v_p(2^e-1) + v_p(\gcd(m/e,n/e)/e \cdot e)$... más limpiamente: $v_p(2^d-1)$ cuando $e \mid d$, lo que confirma $\gcd(2^m-1,2^n-1) = 2^d - 1$.

Este argumento generaliza: $\gcd(a^m - b^m, a^n - b^n) = a^{\gcd(m,n)} - b^{\gcd(m,n)}$ para $\gcd(a,b)=1$. El primo primitivo de $a^d - b^d$ (para $d = \gcd(m,n)$) es central en este cálculo.