Zsygmondy y el orden multiplicativo: la conexión profunda

Reformulación: Zsygmondy es un teorema sobre órdenes multiplicativos

El teorema de Zsygmondy afirma que $a^n - b^n$ tiene un primo primitivo $p$ con $\mathrm{ord}_p(ab^{-1}) = n$. Vista así, la afirmación es:

**Para todo $n \ge 3$ (con las excepciones conocidas), existe un primo $p \equiv 1 \pmod{n}$ tal que el orden de $ab^{-1}$ módulo $p$ es exactamente $n$.**

Esta reformulación conecta Zsygmondy con la teoría de órdenes multiplicativos (Capítulo 4 de este módulo) y con los polinomios ciclotómicos. En particular:

- $p \equiv 1 \pmod{n}$ es la condición de Fermat.

- $\mathrm{ord}_p(ab^{-1}) = n$ dice que $ab^{-1}$ es una raíz primitiva del orden $n$ módulo $p$.

- La existencia de $p$ es equivalente a que el polinomio ciclotómico $\Phi_n(x)$ tenga una raíz módulo $p$, lo que ocurre cuando $p \mid \Phi_n(a,b)$.

Esta perspectiva une tres capítulos del módulo: los métodos p-ádicos del Capítulo 1 (para calcular $v_p(a^n-b^n)$), el teorema de Zsygmondy del Capítulo 2 (para garantizar existencia), y la teoría de órdenes del Capítulo 4 (para clasificar los primos con orden dado).

Los polinomios ciclotómicos como detectores de primos con orden prescrito

Recordemos que $a^n - b^n = \prod_{d \mid n} \Phi_d(a,b)$, donde $\Phi_d$ es el polinomio ciclotómico $d$-ésimo. Un primo $p$ divide a $\Phi_n(a,b)$ si y solo si $\mathrm{ord}_p(ab^{-1})$ es "related to $n$" de una manera precisa.

Lema. Sea $p$ primo con $p \nmid ab$ y $p \nmid n$. Entonces $p \mid \Phi_n(a,b)$ si y solo si $\mathrm{ord}_p(ab^{-1}) = n$.

Demostración. $p \mid \Phi_n(a,b)$ implica $p \mid a^n - b^n$ (pues $\Phi_n \mid a^n-b^n$). Sea $d = \mathrm{ord}_p(ab^{-1})$; entonces $d \mid n$. Si $d < n$, entonces $p \mid a^d - b^d \mid \Phi_d(a,b) \cdot \prod_{e \mid d, e < d} \Phi_e(a,b)$. Como $a^n - b^n = \prod_{e \mid n} \Phi_e(a,b)$ y $p \mid \Phi_n(a,b)$, para que $d < n$ sea posible necesitamos que $p \mid \Phi_n(a,b)$ y $p \mid \Phi_d(a,b)$ simultáneamente. Un resultado estándar (ver abajo) dice que $\gcd(\Phi_n(a,b), \Phi_d(a,b)) \mid n$ cuando $d \mid n$, $d < n$. Entonces si $p \nmid n$, no puede ocurrir $p \mid \Phi_n(a,b)$ y $p \mid \Phi_d(a,b)$ a la vez. Luego $d = n$.

El resultado estándar. Para el polinomio ciclotómico $\Phi_n(x) \in \mathbb{Z}[x]$: si $p \mid \Phi_n(x_0)$ y $p \mid \Phi_d(x_0)$ con $d \mid n$, $d < n$, entonces $p \mid n/d$ (o más precisamente, $p \mid n$). Demostración: $\Phi_n(x) \equiv 0 \pmod{p}$ y $\Phi_d(x) \equiv 0 \pmod{p}$; como $\Phi_d(x) \mid x^d - 1$ y $x^d \equiv 1 \pmod{p}$ (de $\Phi_d(x) \equiv 0$), y también $\Phi_n(x) \mid x^n - 1$; pero $\Phi_n(x)$ y $x^d - 1$ son coprimos módulo $p$ si $p \nmid n/d$... el argumento completo usa que $\Phi_n$ y $x^d-1$ son coprimos en $\mathbb{F}_p[x]$ cuando $p \nmid n$.

Este lema justifica usar los polinomios ciclotómicos para "detectar" primos con orden multiplicativo específico, lo que es la esencia del uso de Zsygmondy en olimpiadas.

Primos con orden dado: consecuencias para las sucesiones $a^n - 1$

La conexión entre Zsygmondy y órdenes multiplicativos tiene consecuencias inmediatas para la sucesión $S_n = a^n - 1$.

Proposición. Sea $a \ge 2$ y sea $p$ un primo impar con $p \nmid a$. Sea $e = \mathrm{ord}_p(a)$. Entonces $p \mid a^n - 1$ si y solo si $e \mid n$. Además, $v_p(a^n - 1) = v_p(a^e - 1) + v_p(n/e)$ para $e \mid n$.

Demostración. La primera parte es la definición del orden. Para la segunda: escribe $n = e \cdot m$. Entonces $a^n - 1 = (a^e)^m - 1^m$. Aplica LTE con $A = a^e$, $B = 1$: $p \mid A - B = a^e - 1$ (pues $e = \mathrm{ord}_p(a)$), $p \nmid A$ y $p \nmid B = 1$. Entonces $v_p(A^m - 1) = v_p(A-1) + v_p(m) = v_p(a^e-1) + v_p(m) = v_p(a^e-1) + v_p(n/e)$.

Interpretación. La "contribución" de $p$ a la sucesión $a^n-1$ está concentrada en los múltiplos de $e = \mathrm{ord}_p(a)$. El primo primitivo de $a^n-1$ es justamente el primo $p$ cuya primera aparición en la sucesión es exactamente en el índice $n$ (es decir, $e = n$).

Consecuencia clave. Si $a^n - 1 = \prod_p p^{v_p(a^n-1)}$, entonces el factor $p^{v_p(a^n-1)}$ es $p^{v_p(a^e-1) + v_p(n/e)}$ donde $e = \mathrm{ord}_p(a)$. La "novedad" de cada $n$ —los primos con $e = n$— es garantizada por Zsygmondy.

Aplicación: IMO Shortlist 2002 N1

Problema (IMO Shortlist 2002 N1). Sea $p$ un primo mayor que $5$. Prueba que existen enteros $a, b$ con $0 \le a, b < p$ tales que $p \mid a^2 - b^2 + 1$.

Solución (conexión con Zsygmondy). Este problema no usa Zsygmondy directamente, pero ilustra la mentalidad de "buscar primos con propiedades de orden" que Zsygmondy formaliza.

Por el teorema de Wilson, $(p-1)! \equiv -1 \pmod{p}$. Podemos escribir $(p-1)! = 1 \cdot 2 \cdots \frac{p-1}{2} \cdot \frac{p+1}{2} \cdots (p-1)$. El producto $1 \cdot 2 \cdots \frac{p-1}{2} = \left(\frac{p-1}{2}\right)!$. Y los términos $\frac{p+1}{2}, \ldots, p-1$ son $\equiv -(\frac{p-1}{2}), \ldots, -1 \pmod{p}$, cuyo producto es $(-1)^{(p-1)/2} \left(\frac{p-1}{2}\right)!$. Así $(p-1)! = (-1)^{(p-1)/2} \left[\left(\frac{p-1}{2}\right)!\right]^2 \equiv -1 \pmod{p}$, de donde $\left[\left(\frac{p-1}{2}\right)!\right]^2 \equiv (-1)^{(p-1)/2+1} \cdot (-1) \equiv (-1)^{(p+1)/2} \pmod{p}$.

Si $p \equiv 1 \pmod{4}$: $(-1)^{(p+1)/2} = (-1)^{(p+1)/2}$. Para $p \equiv 1 \pmod 4$, $(p+1)/2$ es impar, así $(-1)^{(p+1)/2} = -1$. Entonces $\left[\left(\frac{p-1}{2}\right)!\right]^2 \equiv -1 \pmod{p}$, es decir $a = \left(\frac{p-1}{2}\right)!$, $b = 0$ da $a^2 - b^2 + 1 \equiv 0 \pmod{p}$. ✓

La conexión con Zsygmondy: estamos buscando un $a$ con $a^2 \equiv -1 \pmod{p}$, es decir $a^4 \equiv 1 \pmod{p}$ y $a^2 \ne 1$. Esto significa $\mathrm{ord}_p(a) = 4$. La existencia de tal $a$ está garantizada cuando $4 \mid p-1$, i.e., $p \equiv 1 \pmod{4}$. El argumento de Wilson provee explícitamente un tal $a$. Zsygmondy (y la teoría ciclotómica) dan la perspectiva de por qué: el polinomio $\Phi_4(x) = x^2+1$ tiene una raíz módulo $p$ exactamente cuando $p \equiv 1 \pmod{4}$.

Aplicación avanzada: $\text{ord}_p(a) = n$ para infinitos primos $p$

Teorema (consecuencia de Dirichlet y Zsygmondy). Para todo $a \ge 2$ y $n \ge 1$, existen infinitos primos $p$ con $\mathrm{ord}_p(a) = n$.

Demostración usando Zsygmondy. La idea es considerar la sucesión $\Phi_n(a, a^{n-1}k)$ para distintos $k$... no exactamente. Mejor: sea $q_1 < q_2 < \ldots$ los primos que dividen a $\Phi_n(a,1) = \Phi_n(a)$. Queremos mostrar que hay infinitos. Si fueran finitos, $q_1, \ldots, q_r$ serían todos. Considera $N = a \cdot q_1 q_2 \cdots q_r$ y evalúa $\Phi_n(Nm + 1)$ para $m \to \infty$... este argumento es el de Euclides adaptado a ciclotómicos.

Versión directa. Si los únicos primos $p$ con $\mathrm{ord}_p(a) = n$ fueran $p_1, \ldots, p_r$, considera $M = n \cdot p_1 \cdots p_r$ y el número $a^M - 1$. El primo primitivo de $a^M - 1$ (que existe por Zsygmondy para $M \ge 3$) tiene orden $M$ módulo $a$... no orden $n$ en general. El argumento correcto usa la infinitud de primos en progresiones aritméticas (Dirichlet: hay infinitos primos $p \equiv 1 \pmod{n}$) y la existencia de raíces primitivas módulo primos (que permiten construir elementos con cualquier orden divisor de $p-1$).

El rol de Zsygmondy. Aunque la infinitud de primos con $\mathrm{ord}_p(a) = n$ requiere Dirichlet para una demostración completa, Zsygmondy provee la existencia de al menos un primo (para $n \ge 3$, $(a,1,n) \ne$ excepciones). En olimpiadas, esto suele ser suficiente: no necesitamos infinitos primos primitivos, sino la existencia de uno.

Resumen de la conexión. El teorema de Zsygmondy dice esencialmente: "el polinomio ciclotómico $\Phi_n(a,b)$ tiene un factor primo $p$ que no divide a ningún factor ciclotómico anterior." Este primo $p$ tiene exactamente $\mathrm{ord}_p(ab^{-1}) = n$, y $v_p(a^n-b^n) = v_p(\Phi_n(a,b)) = 1$ cuando $p \nmid n$. La integración de Zsygmondy con el LTE y los órdenes multiplicativos constituye la trinidad de herramientas para ecuaciones con potencias en olimpiadas de nivel IMO.

Problema de cierre: combinando todo el capítulo

Problema. Sea $a \ge 2$ un entero. Prueba que para todo $n \ge 1$ se tiene $\gcd(a^n-1, a^{n+1}-1) = a - 1$.

Solución. Usamos la identidad $\gcd(a^m-1, a^n-1) = a^{\gcd(m,n)}-1$ (demostrada en la Lección 2.1). Con $m = n$ y $n+1$: $\gcd(a^n-1, a^{n+1}-1) = a^{\gcd(n,n+1)}-1 = a^1 - 1 = a-1$, pues $\gcd(n,n+1)=1$ para todo entero $n$.

Demostración alternativa directa. Sea $d = \gcd(a^n-1, a^{n+1}-1)$. Entonces $d \mid (a^{n+1}-1) - a(a^n-1) = a^{n+1} - 1 - a^{n+1} + a = a - 1$. Por otro lado, $a-1 \mid a^n - 1$ (factorización: $a^n-1 = (a-1)(a^{n-1}+\cdots+1)$) y $a-1 \mid a^{n+1}-1$. Luego $a-1 \mid d$. Combinando: $d = a-1$.

Conexión con Zsygmondy. Los primos primitivos de $a^n-1$ (los que tienen $\mathrm{ord}_p(a) = n$) no dividen a $a^{n+1}-1$ (pues $\mathrm{ord}_p(a) = n \nmid n+1$, ya que $n \nmid n+1$ para $n \ge 2$). Esto confirma que los factores "nuevos" de $a^n-1$ no perturban el $\gcd$ con $a^{n+1}-1$. Los únicos factores comunes son los que dividen a $a^{\gcd(n,n+1)}-1 = a-1$.

Mensaje de cierre del capítulo. Zsygmondy, el orden multiplicativo y las valuaciones p-ádicas son tres lenguajes para la misma realidad aritmética. Cuando un problema involucra potencias, la pregunta "¿qué primos dividen a $a^n - b^n$ y con qué multiplicidad?" tiene respuesta completa mediante: (1) Zsygmondy para los primos primitivos (existencia y cota inferior $p \ge n+1$), (2) LTE para las multiplicidades ($v_p = v_p(a-b) + v_p(n)$ cuando $p \mid a-b$, y $v_p = v_p(\Phi_n(a,b))$ para primos primitivos), y (3) la fórmula $v_p(a^n-1) = v_p(a^e-1) + v_p(n/e)$ con $e = \mathrm{ord}_p(a)$ para todos los demás primos. Con estas tres herramientas, ningún problema de potencias en olimpiadas de nivel IMO debería ser opaco.