Hay infinitos primos

La pregunta milenaria: ¿hay un primo más grande?

¿Existe un primo $P$ tal que todos los primos son $\le P$? La respuesta es no, y la demostración que daremos tiene más de dos mil años. Aparece en los *Elementos* de Euclides (Libro IX, Proposición 20) y sigue siendo uno de los argumentos más elegantes de toda la matemática.

Lo notable no es solo el resultado, sino la técnica: se asume lo contrario y se construye un número que produce una contradicción. Esa técnica —reducción al absurdo combinada con construcción explícita— es una de las herramientas más poderosas en olimpiadas.

La prueba de Euclides

Teorema: hay infinitos números primos.

Demostración: supongamos por contradicción que hay solo finitos primos $p_1, p_2, \ldots, p_k$. Define el número $N = p_1 p_2 \cdots p_k + 1$.

Por el TFA, $N \ge 2$ tiene algún divisor primo $p$. Ese $p$ debe ser uno de los $p_i$ (pues por hipótesis esos son todos los primos). Pero si $p = p_i$ para algún $i$, entonces $p \mid p_1 p_2 \cdots p_k$, y como también $p \mid N = p_1 \cdots p_k + 1$, se deduce $p \mid 1$. Contradicción, pues ningún primo divide a $1$.

Por lo tanto la suposición de finitud es falsa: hay infinitos primos. $\square$

Atención: el argumento no dice que $N = p_1 \cdots p_k + 1$ sea primo. Dice que $N$ tiene un factor primo que no está en la lista. Por ejemplo, $2 \cdot 3 \cdot 5 \cdot 7 \cdot 11 \cdot 13 + 1 = 30031 = 59 \cdot 509$, que es compuesto.

El argumento de Euler: los primos no son "raros"

La prueba de Euclides confirma que hay infinitos primos, pero no dice cuán "densos" son. Euler demostró algo mucho más fuerte: la serie $\sum_{p \text{ primo}} \frac{1}{p}$ diverge.

La idea (simplificada) parte de la identidad de Euler: $\sum_{n=1}^{\infty} \frac{1}{n^s} = \prod_{p} \frac{1}{1-p^{-s}}$ para $s > 1$. Si hubiera finitos primos, el producto de la derecha sería finito, pero el lado izquierdo diverge cuando $s \to 1^+$. Contradicción.

El resultado $\sum 1/p = \infty$ contrasta con $\sum 1/n^2 < \infty$: los primos son más abundantes que los cuadrados perfectos. En olimpiadas de nivel avanzado este argumento aparece como motivación, pero la versión rigurosa usa análisis; a nivel ONEM basta conocer el enunciado.

Comparación intuitiva: los cuadrados crecen como $n^2$, así que hay $\sqrt{N}$ cuadrados hasta $N$. Los primos crecen mucho más lentamente —hay $\approx N/\ln N$ primos hasta $N$— y esa mayor densidad es exactamente lo que hace la serie diverger.

El Teorema de Dirichlet: primos en progresiones aritméticas

¿Hay infinitos primos de la forma $4k+1$? ¿De la forma $4k+3$? ¿De la forma $100k+7$? La respuesta en todos los casos es sí, y el resultado general se llama Teorema de Dirichlet (1837).

Enunciado: si $\gcd(a, m) = 1$, entonces hay infinitos primos de la forma $a + mk$ (es decir, infinitos primos en la progresión aritmética $a, a+m, a+2m, \ldots$).

La demostración usa funciones $L$ de Dirichlet (análisis complejo) y está fuera del alcance olímpico elemental. Pero el enunciado se usa frecuentemente en argumentos de imposibilidad: si $\gcd(a,m)=1$, la clase $a \pmod{m}$ contiene primos.

Para nivel ONEM lo importante es poder demostrar casos especiales sin Dirichlet, usando argumentos ad hoc. El ejemplo siguiente ilustra la técnica.

Ejemplo olímpico: infinitos primos de la forma $4k+3$

Problema: demuestra que hay infinitos primos de la forma $4k+3$ (es decir, primos $\equiv 3 \pmod 4$).

Demostración: supongamos que los únicos primos de esta forma son $p_1, \ldots, p_r$ (todos $\equiv 3 \pmod 4$). Define $N = 4 p_1 p_2 \cdots p_r - 1$.

Nota que $N \equiv -1 \equiv 3 \pmod 4$. Sea $p$ cualquier factor primo de $N$. Como $N$ es impar, $p \ne 2$, luego $p$ es impar y $p \equiv 1$ o $p \equiv 3 \pmod 4$.

Si todos los factores primos de $N$ fueran $\equiv 1 \pmod 4$, entonces $N \equiv 1 \pmod 4$ (producto de números $\equiv 1$). Pero $N \equiv 3 \pmod 4$. Contradicción. Por tanto, $N$ tiene al menos un factor primo $q \equiv 3 \pmod 4$.

Ese $q$ debe ser uno de los $p_i$. Pero $q \mid N = 4p_1\cdots p_r - 1$ y $q \mid p_1 \cdots p_r$, así $q \mid 1$. Contradicción. Hay infinitos primos $\equiv 3 \pmod 4$. $\square$

Técnica general: para mostrar infinitos primos en una clase $a \pmod m$, construir $N = m \cdot (\text{producto de candidatos}) \pm 1$ de modo que $N \equiv a \pmod m$ pero $N$ no es divisible por ningún candidato. No siempre funciona la misma construcción; el caso $4k+1$ requiere polinomios ciclotómicos.