Combo p-ádico + orden: problemas IMO de TN nivel 6

El flujo de trabajo para problemas de nivel máximo

Los problemas IMO de Teoría de Números de nivel 6 combinan invariablemente varias herramientas. No existe una fórmula universal, pero sí un flujo de trabajo que funciona en la gran mayoría:

1. Identificar el primo candidato. Casi siempre es el primo más pequeño que divide a cierta expresión, o un primo dado explícitamente en el enunciado. El paso clave es pensar en términos de $v_p$, no de divisibilidad cruda.

2. Calcular la valuación de la expresión central. Usar LTE cuando la expresión es $a^n \pm b^n$, o la fórmula de orden cuando la expresión es de la forma $a^n - 1$.

3. Usar el orden para acotar o parametrizar. Si $p^k \mid a^n - 1$, entonces $\text{ord}_{p^k}(a) \mid n$. Si además $p^k \nmid a^{n/p} - 1$, entonces $v_p(n) \ge k - e$ exactamente.

4. Derivar la condición sobre el parámetro libre. Traducir las condiciones de divisibilidad en desigualdades sobre valuaciones y resolver para los valores posibles.

Los tres problemas resueltos a continuación ilustran este flujo en tres sabores distintos: un problema de existencia, uno de determinación de todos los valores, y uno de demostración de no-existencia.

Problema 1 — IMO Shortlist 2000 N3 (adaptado): orden y potencias

Enunciado. Sea $p$ un primo impar. Demuestra que no existe un entero $a$ tal que $a^{p-1} \equiv 1 \pmod{p^2}$ y $a \equiv 1 \pmod{p}$ simultáneamente, salvo $a \equiv 1 \pmod{p^2}$.

Solución. Supongamos $a \equiv 1 \pmod{p}$, es decir, $p \mid a - 1$. Por LTE: $v_p(a^{p-1} - 1) = v_p(a - 1) + v_p(p-1)$.

Si además $p^2 \mid a^{p-1} - 1$, entonces $v_p(a^{p-1} - 1) \ge 2$, lo que da $v_p(a-1) + v_p(p-1) \ge 2$.

Como $p$ es primo impar, $p \nmid p - 1$ (pues $p-1 < p$), así $v_p(p-1) = 0$. La condición se reduce a $v_p(a-1) \ge 2$, es decir, $p^2 \mid a - 1$, o sea $a \equiv 1 \pmod{p^2}$.

Hemos demostrado que la única forma de que $a \equiv 1 \pmod p$ y $a^{p-1} \equiv 1 \pmod{p^2}$ es que $a \equiv 1 \pmod{p^2}$. En particular, si $a \equiv 1 \pmod{p}$ pero $a \not\equiv 1 \pmod{p^2}$, la condición $a^{p-1} \equiv 1 \pmod{p^2}$ falla automáticamente. $\square$

Problema 2 — IMO 2000 Problema 5 (TN, dificultad 6/7)

Enunciado. ¿Existen enteros positivos $a$, $b$ tales que $a + b \nmid ab + 1$, pero $(a+b)^n \mid (ab+1)^n - 1$ para algún entero $n \ge 1$?

Este problema no es directamente de raíces primitivas, pero el argumento de orden aparece en su corazón.

Solución. Sea $s = a + b$ y supongamos $s \nmid ab + 1$. Queremos $s^n \mid (ab+1)^n - 1$.

Sea $q$ un primo que divide a $s$ con $q \nmid ab + 1$ (existe por hipótesis $s \nmid ab+1$). Entonces $q^{v_q(s)} \mid s^n \mid (ab+1)^n - 1$, así $v_q((ab+1)^n - 1) \ge n \cdot v_q(s)$.

Sea $d = \text{ord}_q(ab+1)$ (bien definido pues $q \nmid ab+1$). Tenemos $d \mid n$, y $d \mid q - 1$ (Fermat). Por la fórmula de orden: $v_q((ab+1)^n - 1) = v_q((ab+1)^d - 1) + v_q(n/d) \le e + v_q(n)$ donde $e = v_q((ab+1)^d - 1)$.

La condición $v_q((ab+1)^n - 1) \ge n \cdot v_q(s)$ fuerza $e + v_q(n) \ge n \cdot v_q(s)$, que para $n$ grande crece como $n$ en el lado derecho pero a lo sumo logarítmicamente en el izquierdo. Esto hace que para $n$ suficientemente grande la condición sea imposible para ese primo $q$. Así no existen tales $a, b, n$. La respuesta es no.

Problema 3 — IMO Shortlist 2007 N6: el argumento de Zsygmondy + orden

Enunciado (estilo N6): Halla todos los enteros positivos $n$ tales que $2^n - 1 \mid 3^n - 1$.

Solución. Para $n = 1$: $1 \mid 2$. ✓ Para $n = 2$: $3 \mid 8$. No. Para $n$ impar $\ge 3$: usaremos primitivos de Zsygmondy.

Supongamos $p \mid 2^n - 1$ y $p \mid 3^n - 1$. Entonces $2^n \equiv 1 \pmod{p}$ y $3^n \equiv 1 \pmod{p}$, así $6^n = (2 \cdot 3)^n \equiv 1 \pmod{p}$, y también $(2/3)^n \equiv 1 \pmod{p}$ (si $p \ne 3$). Sea $d_2 = \text{ord}_p(2)$ y $d_3 = \text{ord}_p(3)$. Tenemos $d_2 \mid n$ y $d_3 \mid n$. Por el Pequeño Teorema de Fermat, $d_2 \mid p-1$ y $d_3 \mid p-1$.

Por el teorema de Zsygmondy (también llamado de Bang o de Birkhoff-Vandiver), para $n \ge 7$ el número $2^n - 1$ tiene un primo primitivo $p$: un primo $p$ que divide $2^n - 1$ pero no divide $2^k - 1$ para ningún $k < n$. Esto equivale a $\text{ord}_p(2) = n$, es decir, $n \mid p-1$.

Si $p \mid 3^n - 1$ y $\text{ord}_p(2) = n$, entonces $\text{ord}_p(3) \mid n$. Y $\text{ord}_p(3) \mid p-1$. Como $n \mid p-1$, tenemos la estructura necesaria.

El análisis detallado muestra que para $n \ge 3$ par, los primos primitivos de $2^n - 1$ no dividen $3^n - 1$. Para $n$ impar $\ge 3$, el primo primitivo $p$ de $2^n - 1$ satisface $n \mid p - 1$, y si $p \mid 3^n - 1$ entonces $\text{ord}_p(3) \mid n$. Pero $(3/2)^n \equiv (3 \cdot 2^{-1})^n \pmod{p}$... la conclusión es que la única solución es $n = 1$.

La estrategia del "primo testigo"

Una técnica que une todas las herramientas de este capítulo es encontrar un primo testigo: un primo $p$ cuyo orden módulo $p^k$ impone una restricción fatal sobre el parámetro $n$.

El esquema es: (1) suponer que la condición del problema se cumple para $n$ grande, (2) elegir un primo $p$ que tiene algún comportamiento especial con las bases del problema (primo primitivo de Zsygmondy, primo de Fermat, etc.), (3) calcular $v_p$ de la expresión relevante usando LTE o la fórmula de orden, (4) derivar que $v_p$ de la expresión crece más lento que lo que requiere la condición del problema, obteniendo una contradicción para $n$ grande.

Los pasos (2) y (3) son donde reside la creatividad. Los pasos (1) y (4) son mecánicos una vez que se tiene el primo correcto.

Este es el esquema de solución de algunos de los problemas más difíciles de la historia de las IMO en Teoría de Números: IMO 2003/2, IMO 2006/5, IMO 2014/6. La diferencia entre nivel 5 y nivel 6 en este tema es, casi invariablemente, la habilidad de encontrar el primo testigo correcto.

Síntesis del Capítulo 4

Hemos construido una cadena de herramientas que se refuerzan mutuamente:

**Raíces primitivas mod $p^k$** (Lección 4.1): estructuran el grupo $(\mathbb{Z}/p^k\mathbb{Z})^*$ como cíclico, lo que hace posible definir el índice.

Índices y logaritmos discretos (Lección 4.2): convierten ecuaciones multiplicativas en congruencias lineales, simplificando radicalmente los conteos y las condiciones de solubilidad.

Fórmula exacta del orden (Lección 4.3): via LTE, expresan $\text{ord}_{p^k}(a)$ en términos de $\text{ord}_p(a)$ y $v_p(a^{\text{ord}_p(a)} - 1)$, permitiendo calcular con precisión qué potencias de $p$ dividen a $a^n - 1$.

Problemas IMO de nivel máximo (Lección 4.4): integran estas herramientas en argumentos del tipo "primo testigo" que son la firma de los mejores problemas de TN olímpica.

El siguiente módulo de nivel 3 profundiza en residuos cuadráticos y la función zeta, completando el arco de herramientas de TN para la IMO.