La intuición detrás de la prueba de Erdős de la infinitud de los números primos

Question

Supongamos por contradicción que hay un número finito de primos, a saber $p_1, p_2,...,p_k$ , donde $k$ es un número natural. Consideremos ahora otro número natural $n$ y todos los números naturales $m \leq n$ . Podemos escribir cada $m$ como producto $m_1^2m_2$ , donde $m_1 \in \mathbb{N}$ y $m_2 \in \mathbb{N}$ es un entero libre de cuadrados. Ahora, utilizando algunos argumentos combinatorios simples y el TLC es fácil ver que hay como máximo $2^k\left \lfloor \sqrt{n} \right \rfloor$ formas de escribir el producto $m_1^2m_2$ por lo que podemos concluir que $$n \leq 2^k\sqrt{n}$$ lo cual es absurdo, ya que la desigualdad no se cumple para grandes $n$ .

Esta es una versión de la prueba dada por P. Erdos de la infinitud de los números primos. (según recuerdo).

No tengo problemas para entender la prueba en sí. Lo que me molesta es que, aunque tanto ésta como la prueba de Euclides (creo que todos conocemos esa) son muy bonitas, ésta me parece un poco misteriosa, mientras que la de Euclides, aunque muy ingeniosa, era bastante natural.

Sé que parte de su belleza se debe al hecho mismo de que es inesperado y esquivo. Pero si uno está tratando de demostrar la infinitud de los números primos, ¿por qué pensar en el producto $m_1^2m_2$ ? ¿Por qué iba a servir esto? ¿Acaso Erdos se limitó a probar un montón de ideas diferentes al azar hasta que consiguió una que funcionara (lo que me parece muy poco probable), o hay una motivación para considerar la factorización $m_1^2m_2$ ?

Siento si no me he explicado bien, o si esta pregunta no es adecuada para este sitio web.

Answer 1

La intuición que veo es mostrar que tener un número finito de primos simplemente no es suficiente para generar todos los números. Más concretamente, esto da una cota inferior al número de primos por debajo de un determinado tamaño (una cota inferior a $\pi(n)$ en función de $n$ ), que es más informativo que decir simplemente $\pi(n) \to \infty$ como $n \to \infty$ . Obtener este límite inferior es una buena motivación para ir más allá de la prueba de Euclides.

Supongamos que tenemos un número finito de primos $p_1, p_2, \dots, p_k$ entonces todo número puede expresarse como $p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ para algún vector de exponentes $(e_1, \dots, e_k)$ con todos los componentes enteros no negativos. Desgraciadamente hay infinitas posibilidades para cada $e_i$ así que esto no nos permite controlar nada.

Por otro lado, si cada $e_i$ fueron $0$ o $1$ (es decir, sólo miramos los productos de primos distintos), entonces sólo hay $2^k$ productos posibles. Los números que son productos de primos distintos (nunca hay un $i$ con $e_i \ge 2$ ) se llaman enteros sin cuadrado . Para cualquier número podemos sacar los cuadrados de él y dejar una parte sin cuadrados. Esto es bien conocido en la teoría elemental de números, y no fue introducido por Erdős; incluso hay una entrada en MathWorld sobre pieza cuadrada .

Para cualquier número entero $n$ y cualquier número entero $m \le n$ si escribimos $m$ como una parte libre de cuadrados $r$ por un cuadrado $s^2$ (es decir $m = s^2 r$ ) entonces como $s^2 \le N,$ tenemos $s \le \sqrt{N}$ . Al mismo tiempo, como sólo hay $2^k$ posibles vectores de exponentes $(e_1, \dots, e_k)$ Sólo hay $2^k$ valores posibles para $r$ . Esto da $$n \le 2^k \sqrt{n}.$$

En la pregunta ha utilizado esto para concluir que $k$ no puede ser finito (demostrando así que hay infinitos primos), pero la consecuencia más útil es que el número de primos disponibles $k$ debe satisfacer $2^k\sqrt{n} \ge n$ es decir $$\pi(n) \ge \lg\sqrt{n}.$$

(El límite real es mucho mejor; el teorema del número primo dice $\pi(n)$ crece como $n/\log n$ .)

No sé si te he dado alguna intuición o sólo he replanteado la prueba. :-)