Aplicaciones a IMO Shortlist

El patrón olímpico del orden mínimo

En la mayoría de los problemas olímpicos que involucran orden multiplicativo, el argumento central sigue el mismo esqueleto: (1) sea $p$ el menor primo divisor de $n$; (2) deducir que $\text{ord}_p(a)$ divide a $\gcd(n, p-1)$; (3) como $p$ es el menor primo divisor de $n$, los factores primos de $n$ son todos $\ge p$, mientras que $p-1 < p$ tiene factores primos $< p$; (4) concluir que $\gcd(n, p-1) = 1$, forzando $\text{ord}_p(a) = 1$, es decir $a \equiv 1 \pmod p$.

Este truco —que podríamos llamar el "argumento del primo mínimo"— aparece en problemas de divisibilidad de la forma "$n \mid f(n)$" con frecuencia asombrosa. Reconocerlo es una habilidad de alto valor en competencias de nivel Iberoamericana y Cono Sur.

La fuerza del argumento reside en la tensión entre los factores primos de $n$ (que son $\ge p$) y los factores primos de $p-1$ (que son $< p$). Esta tensión colapsa el orden a 1, lo que da información muy fuerte sobre la base.

Problema modelo: $n \mid 2^n - 1$ (Cono Sur, clásico)

Problema. Encuentra todos los enteros positivos $n$ tales que $n \mid 2^n - 1$.

Solución. Para $n=1$: $1 \mid 1$. Sí. Supongamos $n > 1$ es solución y sea $p$ el menor primo divisor de $n$. Entonces $p \mid n \mid 2^n - 1$, así $2^n \equiv 1 \pmod p$.

Sea $d = \text{ord}_p(2)$. Por el teorema fundamental, $d \mid n$ y $d \mid p-1$. Luego $d \mid \gcd(n, p-1)$. Ahora bien, todo factor primo de $n$ es $\ge p$ (por minimalidad de $p$). Pero $p-1 < p$, así que todos los factores primos de $p-1$ son $< p$. Por tanto $\gcd(n, p-1) = 1$, forzando $d \mid 1$, es decir $d=1$. Esto significa $2 \equiv 1 \pmod p$, o sea $p \mid 1$. Imposible para $p$ primo.

Conclusión: $n = 1$ es la única solución.

IMO Shortlist 2000 N4 (adaptado): orden y divisibilidad

Problema. Encuentra todos los pares de enteros positivos $(a, m)$ con $a > 1$ tales que $\dfrac{a^m - 1}{a - 1}$ es una potencia de $a$.

Reformulación. Pedimos $\frac{a^m-1}{a-1} = a^k$ para algún $k \ge 0$. Observamos $\frac{a^m-1}{a-1} = 1 + a + a^2 + \cdots + a^{m-1}$.

Análisis. Si $k=0$: $1+a+\cdots+a^{m-1}=1$, imposible para $a>1$, $m\ge 1$. Si $k\ge 1$: dividimos por $a^k$: $a^{-k} + a^{1-k} + \cdots + a^{m-1-k} = 1$. Para $m > k+1$ el lado izquierdo es $> a^{m-1-k} \ge a > 1$. Para $m = k+1$: $a^{-k}+\cdots+1 = 1$, imposible. Entonces $m \le k$. Pero $1+a+\cdots+a^{m-1} \ge 1+a \ge a+1 > a = a^1$ para $m \ge 2$... explorando sistemáticamente: para $m=2$, $1+a = a^k$ requiere $a^k - a = 1$, es decir $a(a^{k-1}-1)=1$, imposible para $a > 1$ entero. Para $m \ge 2$ en general, modularmente: sea $p \mid a-1$ primo. Entonces $1 + a + \cdots + a^{m-1} \equiv m \pmod p$ y $a^k \equiv 1 \pmod p$, luego $p \mid m$. Esto genera restricciones fuertes.

Combinando todos los casos, la única solución en enteros positivos es $m=1$ (que da $\frac{a^1-1}{a-1} = 1 = a^0$). Para $m \ge 2$, un argumento por valuación $p$-ádica con $p \mid a-1$ muestra que la suma tiene $v_p = 1$ mientras que $a^k$ tiene $v_p(a^k) = k \cdot v_p(a) = 0$, contradicción. La solución completa es $(a, m) = (a, 1)$ para cualquier $a > 1$.

IMO Shortlist 2003 N2: el orden del 2 módulo un número impar

Problema. Sea $p$ un número primo impar. Demuestra que para todo entero $a$ con $p \nmid a$, el orden $d = \text{ord}_p(a)$ divide a $p-1$, y que $p \mid a^{(p-1)/d} - 1$ si y solo si $d$ no divide a $(p-1)/d \cdot d$... Más precisamente, el problema olímpico real pide: para $b \ge 2$ entero y $n \ge 1$, encontrar todos los enteros $n$ tales que $\frac{b^n - 1}{b - 1}$ sea una potencia de un primo.

Aplicación del orden. Sea $\frac{b^n-1}{b-1} = p^k$. Entonces $b^n - 1 = p^k(b-1)$. Si $p \nmid b-1$: como $p^k \mid b^n-1$, tenemos $\text{ord}_p(b) \mid n$. Pero también $b^n - 1 = (b-1)(1+b+\cdots+b^{n-1})$ y $p \nmid b-1$, así $p^k \mid 1+b+\cdots+b^{n-1}$. Sea $d = \text{ord}_p(b)$; los $n$ términos de la suma se agrupan en $n/d$ bloques de $d$ términos, cada bloque sumando $1+b+\cdots+b^{d-1} \equiv \frac{b^d-1}{b-1} \pmod p$, que es divisible por $p$ pues $p \mid b^d - 1$ y $p \nmid b - 1$. Este análisis acota $k$ y fuerza $n/d$ sea potencia de $p$.

El mensaje pedagógico es que el orden multiplicativo actúa como el "reloj interno" de la expresión: controla qué primos pueden aparecer en $1+b+\cdots+b^{n-1}$ y con qué multiplicidades.

Estrategia general y señales de alerta

Resumimos el protocolo para problemas con orden multiplicativo en IMO Shortlist: (1) Identificar la expresión exponencial y el primo candidato $p$. (2) Calcular o acotar $\text{ord}_p(a)$ usando divisibilidad: $\text{ord}_p(a) \mid p-1$ y $\text{ord}_p(a) \mid$ cualquier exponente que da $1$. (3) Usar el "argumento del primo mínimo" si la condición involucra divisores de $n$. (4) Traducir la condición de divisibilidad en una congruencia sobre el orden.

Las señales de que el orden es la herramienta correcta: la variable aparece en el exponente y en el módulo simultáneamente (como en $n \mid a^n - 1$); se pregunta si algo es primo o potencia de primo; el enunciado pide "todos los $n$" con una condición de divisibilidad exponencial.

Señal de alerta: no confundir $\text{ord}_p(a) \mid p-1$ con igualdad. Muchos errores olímpicos surgen de asumir que el orden es siempre $p-1$. El orden puede ser cualquier divisor de $p-1$, y determinarlo con precisión es lo que distingue una solución correcta de una incorrecta.