Problemas con primos en olimpiadas

La estrategia general: probar primos pequeños primero

En la mayoría de problemas olímpicos con primos, la clave es no actuar en general de inmediato. El flujo correcto es: (1) probar $p=2$ y $p=3$ explícitamente —con frecuencia son casos especiales o la única solución—; (2) para $p \ge 5$ usar congruencias módulo $2, 3, 4, 6$ para restringir la forma de $p$; (3) si la restricción es suficiente, concluir; si no, probar un argumento de divisibilidad.

Este procedimiento de "pequeños casos + argumento modular" resuelve el 90% de los problemas de primos en ONEM regional.

Problema clásico: si $p$ y $p^2+2$ son ambos primos, entonces $p=3$

Enunciado: sea $p$ un número primo tal que $p^2+2$ también es primo. Demuestra que $p=3$.

Solución: verificamos $p=2$: $p^2+2 = 6 = 2\cdot3$, compuesto. Así $p=2$ no funciona.

Para $p=3$: $p^2+2 = 11$, primo. ¡Funciona!

Para $p \ge 5$: todo primo mayor que $3$ satisface $p \equiv 1$ o $p \equiv 2 \pmod 3$. Si $p \equiv 1 \pmod 3$, entonces $p^2 \equiv 1 \pmod 3$, luego $p^2+2 \equiv 3 \equiv 0 \pmod 3$. Así $3 \mid p^2+2$. Como $p^2+2 \ge 27 > 3$, no puede ser primo.

Si $p \equiv 2 \pmod 3$, entonces $p^2 \equiv 4 \equiv 1 \pmod 3$, luego $p^2+2 \equiv 0 \pmod 3$. Misma conclusión.

En todos los casos $p \ge 5$ hace que $p^2+2$ sea divisible por $3$ y mayor que $3$, luego compuesto. Por lo tanto, la única solución es $\boxed{p=3}$.

Argumento modular: si $p \mid n^2+1$ entonces $p \equiv 1 \pmod 4$

Enunciado: sea $p$ primo impar con $p \mid n^2+1$ para algún entero $n$. Demuestra que $p \equiv 1 \pmod 4$.

Solución: de $p \mid n^2+1$ se sigue $n^2 \equiv -1 \pmod p$. Elevando al cuadrado: $n^4 \equiv 1 \pmod p$. El orden multiplicativo de $n$ módulo $p$ divide a $4$ pero no a $2$ (pues $n^2 \equiv -1 \not\equiv 1 \pmod p$). Por lo tanto el orden de $n$ es exactamente $4$.

Por el Pequeño Teorema de Fermat (que veremos en el capítulo 4), el orden de cualquier elemento módulo $p$ divide a $p-1$. Así $4 \mid p-1$, es decir, $p \equiv 1 \pmod 4$.

Aplicación directa: $p = 5$ divide a $1^2+1=2$? No. $5 \mid 2^2+1=5$? Sí. Y efectivamente $5 \equiv 1 \pmod 4$. El primo $p=3$ cumple $3 \equiv 3 \pmod 4$: nunca puede dividir $n^2+1$. Verificar: $n^2 \equiv 0$ o $1 \pmod 3$, nunca $\equiv -1 \equiv 2 \pmod 3$. Correcto.

El Postulado de Bertrand

Postulado de Bertrand: para todo entero $n \ge 1$, existe un primo $p$ con $n < p \le 2n$.

Equivalentemente: entre $n$ y $2n$ siempre hay al menos un primo. En términos de la función $\pi$: $\pi(2n) > \pi(n)$ para todo $n \ge 1$.

Fue conjeturado por Bertrand en 1845 y demostrado por Chebychev en 1850. Existe una prueba elemental elegante dada por Erdős (1932) que usa la factorización del coeficiente binomial $\binom{2n}{n}$.

Ejemplo de aplicación olímpica: demuestra que para todo $n \ge 2$ existe un primo $p$ con $n < p < 2n$ tal que $p \nmid (n-1)!$. Solución: por Bertrand hay un primo $p$ con $n < p \le 2n$. Si $p \le 2n$ y $p > n$, entonces $p$ no aparece entre $1, 2, \ldots, n-1$, así $p \nmid (n-1)!$.

Corolario útil: el $(k+1)$-ésimo primo es menor que $2^{k+1}$. (Por inducción: $p_1=2<2^1$. Si $p_k < 2^k$, por Bertrand existe primo entre $2^k$ y $2^{k+1}$, así $p_{k+1} < 2^{k+1}$.)

Recetario de argumentos con primos para ONEM

Argumento 1 — Solo hay un primo par: $p=2$. Si un problema dice "sea $p$ un primo par", la respuesta es $p=2$. Verificar $p=2$ explícitamente suele dar la solución o mostrar que no hay solución par.

Argumento 2 — Divisibilidad por 3: todo primo $p \ge 5$ satisface $p \equiv 1$ o $2 \pmod 3$, así $p^2 \equiv 1 \pmod 3$. Si la expresión evaluada en $p^2$ resulta divisible por $3$ y mayor que $3$, no puede ser prima. Úsalo para eliminar $p \ge 5$.

Argumento 3 — Factorización forzada: si una expresión de la forma $f(p)$ factoriza como producto de dos factores $> 1$ para $p$ grande, $f(p)$ no puede ser primo para $p$ grande. Ejemplo: $p^2-1 = (p-1)(p+1)$ tiene ambos factores $\ge 2$ cuando $p \ge 3$.

**Argumento 4 — Módulo $4$ y residuos cuadráticos:** los cuadrados módulo $4$ son $0$ o $1$. Así si $p \equiv 3 \pmod 4$, entonces $p \nmid n^2+1$ para ningún $n$ (como vimos arriba).

Argumento 5 — TFA para contar: si un problema pide "$n$ tiene exactamente $k$ divisores", usar $\tau(n) = k$ con la fórmula $\tau = \prod(a_i+1)$ para restringir la forma de la factorización de $n$.