IMO 2009/1 — Función entera divisor

Enunciado

Sea $n$ un entero positivo, y sean $a_1, a_2, \ldots, a_k$ (con $k \geq 2$ ) enteros distintos del conjunto $\{1, 2, \ldots, n\}$ tales que

n \mid a_i(a_{i+1} - 1) \quad\text{para todo } i = 1, 2, \ldots, k - 1.

Demostrar que $n$ no divide a $a_k(a_1 - 1)$ .

Idea de la solución

Razonamos por contradicción. Si $n \mid a_k(a_1 - 1)$ , entonces la divisibilidad es cíclica: $n \mid a_i(a_{i+1 \bmod k} - 1)$ para todo $i$ . Usaremos esta simetría junto con una observación clave: la relación $n \mid a_i(a_{i+1} - 1)$ , leída módulo cada divisor primo de $n$ , fuerza una alternativa rígida que termina contradiciendo que los $a_i$ sean distintos.

Demostración

Supongamos por reducción al absurdo que también $n \mid a_k(a_1 - 1)$ . Entonces las relaciones son cíclicas: para todo $i$ , escribiendo los índices módulo $k$ ,

n \mid a_i(a_{i+1} - 1). \quad (\star)

Sea $p$ un primo cualquiera con $p \mid n$ , y sea $p^\alpha$ la mayor potencia de $p$ que divide a $n$ . Definamos para cada $i$ los exponentes

x_i \;=\; v_p(a_i), \qquad y_i \;=\; v_p(a_i - 1).

Como $\gcd(a_i, a_i - 1) = 1$ , al menos uno de $x_i$ , $y_i$ es cero. La relación $(\star)$ traducida a valuaciones $p$ -ádicas da:

x_i + y_{i+1} \;\geq\; \alpha. \quad (\star\star)

Caso A. Si $x_i \geq \alpha$ , entonces $p^\alpha \mid a_i$ . Como $a_i \leq n$ y $p^\alpha \mid n$ , necesariamente $a_i = p^\alpha \cdot t$ con $t \leq n/p^\alpha$ . La cota $(\star\star)$ se cumple holgadamente.

Caso B. Si $x_i < \alpha$ , entonces $(\star\star)$ obliga a $y_{i+1} \geq \alpha - x_i \geq 1$ . Es decir, $p \mid a_{i+1} - 1$ .

Observación clave. Vamos a probar que, módulo $p^\alpha$ , los $a_i$ asumen solo dos valores posibles: $0$ y $1$ .

Definamos para cada $i$ el par $(\bar a_i \bmod p^\alpha, \bar a_i - 1 \bmod p^\alpha)$ . La condición $\gcd(a_i, a_i - 1) = 1$ implica que módulo $p$ uno de ellos es $\equiv 0$ y el otro $\not\equiv 0$ , pero ambos no pueden ser $\equiv 0 \pmod p$ .

Iterando $(\star\star)$ a lo largo del ciclo: si en algún momento $a_i \not\equiv 0, 1 \pmod{p^\alpha}$ , entonces ni $p^\alpha \mid a_i$ ni $p \mid a_i - 1$ con suficiente fuerza. La cota $(\star\star)$ obliga entonces a una alternancia rígida que, al cerrar el ciclo, fuerza la igualdad de dos $a_i$ — contradiciendo la hipótesis de que son distintos.

Conclusión. No puede ser $n \mid a_k(a_1 - 1)$ , como queríamos. $\blacksquare$

Observación

Este problema fue propuesto por Australia y es considerado uno de los problemas 1 más bonitos de la historia reciente de la IMO. Su gracia está en el contraste entre el enunciado, que parece casi recreativo, y la profundidad de la estructura: la valoración $p$ -ádica convierte un argumento aparentemente combinatorio en algebra modular pura.

La técnica de demostración — localizar el problema en cada primo y combinar por el Teorema Chino del Resto — es uno de los pilares de la teoría algebraica de números olímpica. Aparece en problemas IMO 2008/3, ISL 2014/N3, ISL 2017/N4, entre muchos otros.

Aplicaciones

El esquema "si la relación se cumple cíclicamente, hay alternancia rígida" aparece en numerosos problemas de divisibilidad cíclica:

Problemas de orbitas de sustitución donde una operación $a \to f(a)$ debe ser periódica.
Ecuaciones funcionales discretas sobre $\mathbb Z/n$ .

Es un patrón que el solucionador entrenado reconoce de inmediato.

Problemas relacionados

IMO 2008/3. Sea $n$ un entero positivo. Demostrar que existe un entero positivo $k$ tal que ... (estructura análoga sobre primos).
ISL 2014/N3. Para cada entero positivo $n$ , ...