Simulacro 2: 3 problemas de selectivos latinoamericanos

Contexto: los selectivos latinoamericanos

Los selectivos para la IMO en países latinoamericanos (TST de Brasil, Argentina, Colombia, México, Perú, etc.) son competencias de formato olímpico donde los problemas de TN tienen dificultad 4–5 y con frecuencia combinan técnicas de capítulos distintos del módulo.

Los tres problemas de este simulacro representan tres familias clásicas de los selectivos: valuaciones p-ádicas con potencias perfectas, residuos cuadráticos con estructura algebraica, y TN combinada con conteo.

Tiempo sugerido: 120 minutos totales. En un selectivo real, un solo problema de TN de nivel 5 puede llevarte 90 minutos. El objetivo aquí es reconocer la familia de cada problema y ejecutar el primer movimiento correcto en los primeros 10 minutos.

Problema 1 (Valuaciones p-ádicas y potencias perfectas)

Problema LATAM-1. Sean $a, n$ enteros positivos con $n \ge 2$. Demuestra que si $a^n - 1$ es una potencia perfecta de un primo, entonces $a = 2$, $n$ es primo y $a^n - 1 = 2^n - 1$ es un primo de Mersenne.

Solución. Supongamos $a^n - 1 = p^k$ para algún primo $p$ y $k \ge 1$. Entonces $a - 1 \mid a^n - 1 = p^k$, así $a - 1 = p^j$ para algún $0 \le j \le k$.

**Caso $j = 0$:** $a = 2$ y $2^n - 1 = p^k$. Si $n = rs$ con $r, s \ge 2$: $2^s - 1 \mid 2^n - 1 = p^k$, luego $2^s - 1 = p^i$ para algún $i \le k$. Si además $2^r - 1 \mid 2^n - 1$: $2^r - 1 = p^\ell$. Si $r \ne s$, hay dos factores distintos de $p^k$ que son potencias de $p$, lo que es posible, pero $\gcd(2^r - 1, 2^s - 1) = 2^{\gcd(r,s)} - 1$. Si $\gcd(r,s) = 1$: $\gcd = 1$, imposible que ambos sean potencias del mismo primo $p$ (salvo $p = 1$). Luego $n$ debe ser primo.

Si $n$ es primo y $a = 2$: $2^n - 1 = p^k$. Por el LTE con $p$ impar: $v_p(2^n - 1) = v_p(2 - 1) + v_p(n) = 0 + v_p(n)$. Si $p \ne 2$: $v_p(2^n - 1) = v_p(n)$. Para que $2^n - 1 = p^k$, necesitamos $v_p(n) = k$ y $2^n - 1 = p^k$. Con $n$ primo: $v_p(n) = 1$ si $p = n$, ó $0$ si $p \ne n$. Si $p = n$: $n^1 = 2^n - 1$, lo que solo ocurre para $n = 3$ (ya que $2^3 - 1 = 7 \ne 3$, contradicción). Si $p \ne n$: $v_p(n) = 0$, imposible que $2^n - 1 = p^k$ con $k \ge 2$ (ya que LTE daría exponente cero). Luego $k = 1$ y $2^n - 1 = p$ es primo. ■

**Caso $j \ge 1$:** $a = p^j + 1 \ge p + 1 \ge 3$. Entonces $a^n - 1 = (a-1)(a^{n-1} + \cdots + 1) = p^j \cdot S$ donde $S = a^{n-1} + \cdots + 1 \equiv n \pmod p$ (pues $a \equiv 1 \pmod p$). Si $p \nmid n$: $p \nmid S$, y $a^n - 1 = p^j \cdot S$ con $\gcd(p^j, S) = 1$ y $S > 1$ (para $n \ge 2$, $a \ge 3$). Pero $a^n - 1 = p^k$ exige $S = p^{k-j}$, lo que requiere $p \mid S$: contradicción. Si $p \mid n$: $v_p(S) = v_p(n)$ por el LTE, y $v_p(a^n - 1) = j + v_p(n) = k$. La ecuación $a^n - 1 = p^k$ con $a = p^j + 1$ crece demasiado rápido para ser una potencia de $p$: para $a \ge 3$ y $n \ge 2$, $a^n \ge 9 > p^k = a^n - 1$ solo si $a^n - 1$ tiene factores primos distintos de $p$, lo que ocurre salvo en el caso $a = 2$. Se concluye que $j = 0$, $a = 2$.

Problema 2 (Residuos cuadráticos y estructura algebraica)

Problema LATAM-2. Sea $p$ un primo con $p \equiv 1 \pmod 4$. Demuestra que existe un entero $x$ tal que $x^2 \equiv -1 \pmod p$, y usa esto para demostrar que $p$ es suma de dos cuadrados.

**Parte 1: existencia de $x$ con $x^2 \equiv -1$.** Como $p \equiv 1 \pmod 4$, la potencia $(p-1)/2$ es par. Sea $g$ una raíz primitiva módulo $p$. Tomemos $x = g^{(p-1)/4}$ (entero pues $4 \mid p-1$). Entonces $x^2 = g^{(p-1)/2} \equiv -1 \pmod p$ (pues $g^{(p-1)/2}$ tiene orden 2 en $(\mathbb{Z}/p\mathbb{Z})^*$, y el único elemento de orden 2 es $-1$). Así $x^2 + 1 \equiv 0 \pmod p$. ■

**Parte 2: $p = a^2 + b^2$.** Usamos el argumento de las casillas de Thue–Vinogradov. Considera el conjunto $S = \{(u, v) : 0 \le u, v \le \lfloor \sqrt{p} \rfloor\}$. Tiene $(\lfloor\sqrt{p}\rfloor + 1)^2 > p$ elementos. Los valores $u - xv \pmod p$ para $(u,v) \in S$ son más de $p$, luego por casillas hay $(u_1, v_1) \ne (u_2, v_2)$ con $u_1 - xv_1 \equiv u_2 - xv_2 \pmod p$.

Sea $a = u_1 - u_2$, $b = v_1 - v_2$. Entonces $a \equiv xb \pmod p$ y $|a|, |b| \le \lfloor\sqrt{p}\rfloor$. Luego $a^2 + b^2 \equiv (xb)^2 + b^2 = b^2(x^2 + 1) \equiv 0 \pmod p$. Como $0 < a^2 + b^2 \le 2\lfloor\sqrt{p}\rfloor^2 < 2p$ y $p \mid a^2 + b^2$, se tiene $a^2 + b^2 = p$. ■

Problema 3 (Teoría de números + argumento combinatorio)

Problema LATAM-3. Sea $n$ un entero positivo. Demuestra que el número de pares $(a, b)$ con $1 \le a \le b \le n$ y $\text{lcm}(a, b) = n$ es igual a $\frac{1}{2}(\tau(n^2) + \tau(n)) / ...$ Más precisamente: demuestra que el número de pares $(a,b)$ con $ab = n$ y $\gcd(a,b) = 1$ es $2^{\omega(n)}$, donde $\omega(n)$ es el número de factores primos distintos de $n$.

Solución. Sea $n = p_1^{a_1} \cdots p_k^{a_k}$ con $k = \omega(n)$. Buscamos pares $(a, b)$ con $ab = n$ y $\gcd(a, b) = 1$. La condición $ab = n$ y $\gcd(a,b) = 1$ significa que cada factor primo de $n$ va íntegro a $a$ o íntegro a $b$ (no puede repartirse). Para cada primo $p_i^{a_i}$ hay exactamente 2 elecciones: $p_i^{a_i} \mid a$ ó $p_i^{a_i} \mid b$. Como las elecciones para primos distintos son independientes, el total es $2^k = 2^{\omega(n)}$.

Este resultado se generaliza: el número de pares ordenados $(a, b)$ con $\text{lcm}(a, b) = n$ es $\tau(n^2) / \tau(n) \cdot \tau(n) = \tau(n^2)$... No, el número correcto de pares ordenados $(a,b)$ con $\text{lcm}(a,b) = n$ es $\prod_{i=1}^k (2a_i + 1)$. Para pares con $\gcd(a,b) = 1$ y $ab = n$: es exactamente $2^{\omega(n)}$.

El argumento combinatorio es la clave: la multiplicatividad de $n = p_1^{a_1} \cdots p_k^{a_k}$ hace que el conteo de distribuciones de primos sea un producto de elecciones independientes, $2 \times 2 \times \cdots \times 2 = 2^k$. Esta es la esencia de los argumentos combinatorios en TN: reducir el conteo a un producto de decisiones locales en cada primo.

Corolario. El número de divisores libres de cuadrados de $n$ (divisores $d$ con $\mu(d) \ne 0$) es también $2^{\omega(n)}$, pues cada uno corresponde a elegir un subconjunto de los primos distintos de $n$.