Revisión integral: problemas selectivos IMO de TdN

Cómo afrontar un problema de TdN de nivel IMO

Antes de entrar en los problemas, vale la pena articular la estrategia general para problemas de TdN de nivel selectivo:

Paso 1: Identificar la estructura. ¿El problema habla de divisibilidad de una expresión? → Pensar en valuaciones $v_p$. ¿Hay potencias y módulos? → LTE. ¿Se pregunta si algo es un cuadrado perfecto o residuo cuadrático? → Símbolo de Legendre y reciprocidad. ¿Se buscan soluciones de ecuaciones modulares para potencias de primo crecientes? → Hensel.

Paso 2: Explorar casos pequeños. Antes de buscar la demostración general, verificar $n = 1, 2, 3, 4, 5$ o $p = 2, 3, 5, 7$. Esto frecuentemente revela el patrón y orienta la herramienta correcta.

Paso 3: Reducir. En TdN olímpica, casi siempre conviene reducir al caso de un primo $p$ y trabajar localmente. La condición "para todo $n$" o "para todo primo" a menudo permite fijar el primo y usar sus propiedades.

Paso 4: Verificar hipótesis de los teoremas. Antes de aplicar LTE, Hensel, Zsygmondy, etc., comprobar explícitamente que todas las hipótesis se cumplen. Los casos donde fallan son frecuentemente las excepciones que da el problema.

Con esta metodología abordamos los dos problemas que siguen.

Problema 1 (valuación p-ádica y LTE): $v_p$ de sumas de factoriales

Problema (IMO Shortlist N estilo). Sea $p$ un primo impar. Encuentra todos los enteros positivos $n$ tales que $p^2 \mid n! + (n+1)! + (n+2)!$.

Exploración. Para $p = 3$, $n = 1$: $1! + 2! + 3! = 1 + 2 + 6 = 9 = 3^2$. ✓ Para $n = 2$: $2! + 3! + 4! = 2 + 6 + 24 = 32$, $9 \nmid 32$. Para $n = 5$: $5! + 6! + 7! = 120 + 720 + 5040 = 5880 = 8 \cdot 735 = 8 \cdot 3 \cdot 5 \cdot 49$, $9 \nmid 5880$.

Simplificación algebraica. $n! + (n+1)! + (n+2)! = n!(1 + (n+1) + (n+1)(n+2)) = n!(1 + n + 1 + n^2 + 3n + 2) = n!(n^2 + 4n + 4) = n!(n+2)^2.$

Entonces la condición es $p^2 \mid n! \cdot (n+2)^2$.

**Análisis caso $p \le n+2$.** Si $p \le n$, entonces $p \mid n!$ y de hecho $v_p(n!) \ge 1$ (incluso $\ge 2$ si $p \le n/2$, etc. por la fórmula de Legendre $v_p(n!) = \sum_{k=1}^\infty \lfloor n/p^k \rfloor$). La condición $p^2 \mid n!(n+2)^2$ requiere $v_p(n!) + 2v_p(n+2) \ge 2$.

Si $p \nmid (n+2)$: necesitamos $v_p(n!) \ge 2$, que ocurre cuando $2p \le n$, i.e., $n \ge 2p$. Para $p \le n < 2p$: $v_p(n!) = 1$ (pues solo el término $k=1$ contribuye y $\lfloor n/p \rfloor = 1$), entonces $v_p(n!(n+2)^2) = 1 < 2$. No funciona.

Si $p \mid (n+2)$: entonces $v_p(n!) + 2v_p(n+2) \ge 0 + 2 = 2$. La condición se cumple siempre que $p \mid n+2$.

**Caso $p > n + 2$.** Entonces $p \nmid n!$ y $p \nmid (n+2)$, así $v_p(n!(n+2)^2) = 0 < 2$. No funciona.

Resumen. Los $n$ tales que $p^2 \mid n!(n+2)^2$ son: (a) $n \ge 2p$ con $p \nmid (n+2)$ (pues $v_p(n!) \ge 2$), (b) $p \mid (n+2)$ (cualquier $n$), (c) $n \ge p$ y $2v_p(n+2) + v_p(n!) \ge 2$. En definitiva: $p^2 \mid n!(n+2)^2$ si y solo si $n \ge 2p$ o $p \mid n+2$ (en el rango $n < 2p$). $\square$

Problema 2 (Hensel y residuos cuadráticos): ecuación de Pell modular

Problema (selectivo olímpico). Sea $p$ un primo impar con $p \equiv 1 \pmod{4}$. Prueba que para todo $k \ge 1$, la ecuación $x^2 \equiv -1 \pmod{p^k}$ tiene solución.

Proceso de pensamiento. El caso $k = 1$: como $p \equiv 1 \pmod 4$, por el primer suplemento $\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2} = (-1)^{\text{par}} = 1$, así existe $a$ con $a^2 \equiv -1 \pmod p$.

Para $k \ge 2$: queremos levantar esta solución. Aplicamos Hensel con $f(x) = x^2 + 1$, $f'(x) = 2x$.

Aplicación de Hensel. Tenemos $f(a) = a^2 + 1 \equiv 0 \pmod p$ y $f'(a) = 2a$. Para que Hensel aplique necesitamos $f'(a) \not\equiv 0 \pmod p$, es decir $p \nmid 2a$. Como $p$ es impar, $p \nmid 2$. ¿Puede $p \mid a$? Si $p \mid a$, entonces $a^2 \equiv 0 \pmod p$ pero necesitamos $a^2 \equiv -1 \pmod p$, así $p \mid 1$, imposible. Luego $p \nmid a$, y en consecuencia $p \nmid f'(a) = 2a$.

Conclusión por Hensel. Como $f(a) \equiv 0 \pmod p$ y $f'(a) \not\equiv 0 \pmod p$, el lema de Hensel garantiza la existencia de $a_k$ con $f(a_k) \equiv 0 \pmod{p^k}$ y $a_k \equiv a \pmod p$, para todo $k \ge 1$. Es decir, $a_k^2 \equiv -1 \pmod{p^k}$. $\square$

Observación adicional. La condición $p \equiv 1 \pmod 4$ es necesaria y suficiente para $k = 1$ y, por Hensel, también para todo $k \ge 1$. Si $p \equiv 3 \pmod 4$, entonces $-1$ no es residuo cuadrático módulo $p$ y, por lo tanto, tampoco módulo $p^k$ para ningún $k$ (si $x^2 \equiv -1 \pmod{p^k}$, reduciendo módulo $p$ daría $x^2 \equiv -1 \pmod p$, contradicción).

**Extensión: $x^2 \equiv -1 \pmod{n}$ para $n$ compuesto.** La ecuación tiene solución si y solo si en la factorización $n = 2^{e_0} p_1^{e_1} \cdots p_r^{e_r}$: (i) $e_0 \le 1$, (ii) todo primo $p_i \mid n$ con $p_i$ impar satisface $p_i \equiv 1 \pmod 4$. Esto combina el Teorema Chino del Resto con el resultado anterior.

Síntesis del Capítulo 7: mapa de herramientas

El Capítulo 7 ha cubierto tres grandes pilares de la TdN analítica olímpica. Aquí presentamos un mapa mental para elegir la herramienta correcta:

Sumas de Gauss (Lección 7.1). Usar cuando: (a) el problema involucra contar soluciones de ecuaciones cuadráticas módulo $p$, (b) aparece la reciprocidad cuadrática y conviene entender "por qué", (c) se busca demostrar que cierta suma trigonométrica de enteros vale exactamente $\sqrt{p}$.

LTE y métodos p-ádicos (Lección 7.2). Usar cuando: (a) hay expresiones de la forma $a^n \pm b^n$ y se pide $v_p$ de dicha expresión, (b) el problema involucra divisibilidad de factoriales o potencias con módulos crecientes, (c) la condición $p \mid a \pm b$ está presente o puede forzarse.

**Raíces primitivas y estructura de $(\mathbb{Z}/p^k\mathbb{Z})^*$ (Lección 7.3).** Usar cuando: (a) el problema pregunta sobre el orden multiplicativo de un elemento, (b) se busca cuántos residuos cuadráticos hay o si cierto elemento es cuadrado, (c) la factorización del grupo (ciclicidad) simplifica el argumento.

Lema de Hensel (Lecciones 7.2 y 7.4). Usar cuando: (a) se sabe que $f(a) \equiv 0 \pmod p$ y se quiere extender a $p^k$, (b) el problema pregunta "¿para cuáles $k$ tiene solución módulo $p^k$?", (c) la derivada $f'(a) \not\equiv 0 \pmod p$.

La clave de las olimpiadas de nivel selectivo es reconocer qué estructura subyace al problema y traducirlo al lenguaje correcto. Con las herramientas de este capítulo, los problemas de TdN que eran opacos se vuelven manejables —y a menudo elegantes.