Introducción
Había una vez un hotel con infinitas habitaciones y un conserje que les asignaba estancia a los huéspedes que iban llegando. Un día que el hotel estaba lleno, una persona nueva llegó y le pidió al conserje dormir en el hotel esa noche.
Para ello, el conserje le pidió a cada huésped que se trasladase a la habitación consiguiente; de modo que quien estaba en el cuarto $1$ se mudaría al cuarto $2$, y quien estaba en el cuarto $2$, se mudaría al cuarto $3$. Sucesivamente, el huésped de la habitación $n$ se mudaría a la habitación $n +1$, y como los números naturales son infinitos, eso siempre sería posible. Finalmente, el cuarto $1$ quedaría libre para ser ocupado por el recién llegado.
Hasta aquí todo marchó bien, pero llegó el momento esa misma noche, en que una infinidad de personas, tantas como números naturales, llegaron al hotel infinito y quisieron realizar su registro. Este fue un nuevo problema para el conserje, pero ya que el hotel tenía infinitas habitaciones, debía haber una manera de incluir a infinitas personas más. En efecto, esto fue lo que se hizo:
Todos los actuales huéspedes ahora se trasladarían de la habitación $n$ a la habitación $2n$, seguido de lo cual los números de cuarto impares quedarían vacíos. Como existen infinitos números impares, el conjunto infinito numerable de personas que ahora solicitaban habitación, podrían distibuirse a lo largo de todos los cuartos impares.
Sin embargo, la felicidad no reinó por mucho tiempo, cuando pasada la media noche arrivaron a la entrada del hotel una infinidad de autobuses con infinitos pasajeros cada uno. ¡Casa pasajero quería una habitación propia! El conserje quiso negarse a hacerlo, pero el dueño del hotel lo despediría si no, así que terminó solucionando el problema:
A los actuales huéspedes del hotel les asignó el número primo $2$ y les pidió elevar $2$ a la potencia su número de habitación. La del número de cuarto $4$ se mudaría al cuarto $2^4$, la del cuarto $5$ se movería a la habitación $2^5$, la familia del cuarto $10$ se trasladaría a la habitación $2^{10}$, etc.
Luego, al camión $1$ lo etiquetó con el siguiente primo, el $3$, y a cada uno de sus pasajeros les pidió elevar $3$ a la potencia su número de asiento. Así, el pasajero en el asiento $1$ del camión $1$, se hospedaría en la habitación $3^1$, el pasajero del asiento $2$ del camión $1$ tomaría la habitación $3^2$ y el pasajero del asiento $n$ del camión $1$, se quedaría con la habitación $3^n$.
Y sucesivamente hizo lo mismo con el resto de los autobuses. A cada autobús le fue asignado un número primo distinto. Era un conjunto infinito numerable de autobuses, pero ya que sabemos desde tiempos de Euclides que el conjunto de primos es infinito, siempre será posible dar una asignación. Además, el teorema fundamental de la aritmética asegura que la factorización de un entero es única, por lo que las asignaciones de cuartos serán siempre diferentes (no sucederá el caso que dos personas coincidan en una misma habitación).
Luego entonces, cada pasajero en el camión etiquedado por el primo $p$, se encargaría de elevar $p$ a la potencia su número de asiento, para determinar la habitación en la que se hospedaría.
A la historia que acabo de relatar se le conoce como la paradoja del hotel infinito de Hilbert. ¿Le entendiste?
El conjunto de primos es infinito
Ahora demostraremos, por el método de contradicción, que “el conjunto de primos es infinito” ; es decir, partiremos de que el conjunto de primos no es finito y, eventualmente se disparatará el asunto.
Para una prueba así, sería difícil usar inducción dado que, si bien el conjunto de primos puede indexarse por $p_1, p_2, p_3, \ldots$ según el orden en que van apareciendo los primos, no es fácil determinar cuál es el primo que sigue en la lista, a diferencia de los naturales (en los naturales, si $n$ es el último número en la lista, entonces quien le sigue a $n$ es $n+1$). Y resultaria igualmente ambiguo intentar la demostración por algún otro método directo.
Entonces, suponer que hay finitos primos significa que se puede crear una lista finita con ellos: ${p_1, p_2, \ldots , p_k}\text{.}$ Se demostrará que siempre hay un primo distinto de los de la lista, lo que conlleva una contradicción con la hipótesis de que sólo existían $k$ primos.
Veamos primero un caso particular.
Supongamos que sólo existieran $2$ primos, el $2$ y el $3$. Consideremos el número $z = 2\cdot 3 + 1\text{.}$
$2 \nmid 2\cdot 3 + 1$ (pues, siendo $2\cdot 3$ y $2\cdot 3 + 1$ números consecutivos donde $2 \enspace \vert \enspace 3$, entonces $2$ ya no divirá a $2\cdot 3 + 1$ pues deja residuo $1$).
Asímismo, $3 \nmid 2\cdot 3 + 1$, pues, para que fuera divisible entre $3$ el residuo tendría que ser $0$ en vez de $1$.
Luego, $2\cdot 3 + 1 = 7$, quien no es divisible entre $2$ ni $3$, pero sí entre $7$. Así, hemos exhibido un nuevo primo, el $7$, lo que contradice el supuesto de que sólo habían dos primos.
Supongamos entonces que hay únicamente 4 primos: ${2,3,5,7}\text{.}$ Consideremos el número $2 \cdot 3 \cdot 5 \cdot 7 + 1 = 211\text{.}$
Ya que $211 = 105 \cdot 2 + 1$, entonces $2 \nmid 211\text{.}$
Ya que $211 = 70 \cdot 3 + 1$, entonces $3 \nmid 211\text{.}$
Ya que $211 = 42 \cdot 5 + 1$, entonces $5 \nmid 211\text{.}$
Ya que $211 = 30 \cdot 7 + 1$, entonces $7 \nmid 211\text{.}$
La conclusión es: Aunque $211$ no es divisible por $2,3,5$ ó $7$, debe existir algún otro primo que sí lo divida, pues cualquier entero es factorizable como producto de primos. Y de hecho, $211$ es primo.
¿Qué si ahora enlistáramos los primeros 211 primos, luego los multiplicáramos y construyéramos $ q = 2\cdot 3 \cdot \cdots \cdot 211 + 1$?
Con un poco de observación, nos damos cuenta que $q$ no es divisible entre ninguno de los primos que se usaron para construirlo, por lo que necesariamente debe existir otro primo fuera de la lista, lo que nuevamente rompe con la suposición de que sólo existían $211$ primos.
Y lo mismo ocurrirá sin importar la cantidad de primos $p_1, p_2, \ldots , p_k$ inicial.
La demostración del teorema en general es así:
Teorema. El conjunto de primos es infinito.
Dem.- Sean $p_1. p_2, \ldots , p_k$ los primeros $k$ primos y consideremos el número $$p_1\cdot p_2 \cdot \ldots \cdot p_k +1\text{.}$$
El anterior número no es divisible por ninguno de los primos $$p_1, p_2, \ldots , p_k\text{.}$$
Esto muesta que $$p_i \nmid p_1\cdot p_2 \cdot \ldots \cdot p_k + 1 \text{.}$$ Por el teorema fundamental de la aritmética, $$p_1\cdot p_2 \cdot \ldots \cdot p_k + 1$$ tiene un divisor primo diferente de $$p_1. p_2, \ldots , p_k \text{,}$$ lo que muestra que hay más de $k$ primos (cualquiera que sea $k$). Por lo tanto, el número de primos es infinito.
$\square$
Selección de ejercicios
En la sección de números primos del libro de Rincón, Bravo, Rincón, se sugieren unos ejercicios, de los cuáles hoy hacemos una selección.
Proposición 1. Si $n$ es un entero mayor que $1$ no es primo, entonces existe un primo positivo $p$ tal que $p^2 \leq n \text{.}$
Dem.- El primer entero $n$ tal que $n>1$ no es primo, es $n=4$. Ya que $2$ es primo y $2^2 \leq 4 \text{,}$ el enunciado es válido para el menor número no primo mayor que $1$. Sea $n > 4$ no primo. Se tiene que $$2^2 \leq 4 < n \quad \forall n>4\text{.}$$
Así que por transitividad, $2^2 < n$. Por lo que, no importa quién sea $n$, siempre existe un primo que elevado al cuadrado es menor o igual a $n$.
$\square$
Proposición 2. El único conjunto de $3$ impares positivos consecutivos primos es $\{3,5,7\}\text{.}$
Dem.- Notamos que en el conjunto $\{3,5,7\}$ hay un número que es divisible entre $3$. $3$ es primo, sin embargo, todos los múltiplos de $3$ distintos de $3$ ya no lo son.
Ahora supongamos que existen otros primos consecutivos ${p, \enspace p + 2, \enspace p + 4}\text{.}$ Siempre ocurre que alguno de ellos es divisible entre $3\text{,}$ veamos esto:
Sean $p, \enspace p+1, \enspace p+2, \enspace p+3, \enspace p+4$ números consecutivos. Fijémonos en la primera tercia $\{p, \enspace p+1, \enspace p+2\} \text{.}$ Alguno de estos números es divisible entre $3$, ya que los múltiplos de tres aparecen cada tres números en la recta numérica.
Caso 1. Si $3 \enspace \vert \enspace p$ hay una contradicción con el hecho de que $p$ es primo mayor que $3$. Por lo que este caso es imposible.
Caso 2. Si $3 \enspace \vert \enspace p + 2$ sería nuevamente una contradicción con la suposición de que $p + 2$ es primo mayor que $3$, por lo que este caso también es imposible.
Caso 3. Supongamos que $3 \enspace \vert \enspace p + 1.$ Esto sí podría suceder, dado que $p + 1$ es compuesto. Luego, ya que $3 \enspace \vert \enspace p + 1\text{,}$ entonces $3 \enspace \vert \enspace p+4$, pero esto contradice la suposición de que $p + 4$ es primo mayor que $3$.
Ya que todos los casos son imposibles, se concluye que la única terna de primos consecutivos es $\{3,5,7\}\text{.}$
$\square$
Proposición 3. Si $2^n – 1$ es primo, con $n \in \mathbb{N} \text{,}$ entonces $n$ es impar o $n$ es $2\text{.}$
Dem.- Por contrapuesta, veremos que si $n \in \mathbb{N}$ es un número par mayor que $2$, entonces $2^n -1 $ no es primo.
Si $n$ es un número par mayor que $2$ entonces $n = 2k$ para alguna $k\in \mathbb{N}\text{,}$ con $k>1\text{.}$ Así, $$2^n – 1 = 2^{2k} – 1 = (2^k + 1) (2^k -1)\text{.}$$
La descomposición es no trivial, es decir, $(2^k + 1) \neq 1$ y $(2^k + 1) \neq 2^n – 1.$ Del mismo modo, $(2^k – 1) \neq 1$ y $(2^k – 1) \neq 2^n – 1.$
$\square$
Proposición 4. Si $2^n -1$ es primo, con $n\in \mathbb{N}$, entonces $n$ es primo.
Dem.- Por el método de la contrapositiva, probemos que si $n$ no es primo, entonces $2^n -1$ no es primo.
Sea $n$ no primo. Entonces existen $a,b \in \mathbb{N}$ tales que $n =a\cdot b\text{,}$ con $a\neq \{1, n\}$ y $b\neq \{1,n\}\text{.}$
Luego, usando que $$x^n-1 = (x-1)(1 + x + x^2 + \ldots + x^{n-1})$$ y eligiendo $x = 2^a$ y $n=b$, obtenemos:
$$ 2^{ab} -1 = (2^a -1)(2^{a(b-1)} + 2^{a(b-2)} + \cdots + 2^a + 1)\text{,}$$
la cual es una descomposición no trivial, pues si lo fuera tendríamos que:
Caso 1. $ \quad \quad 2^a -1 = 1 \quad \quad$ ó $ \quad \quad 2^a -1 = 2^n -1\text{.}$
Caso 2. $ \quad \quad 2^{a(b-1)} + 2^{a(b-2)} + \cdots + 2^a + 1 = 1 \quad \quad$ ó $ \quad \quad 2^{a(b-1)} + 2^{a(b-2)} + \cdots + 2^a + 1 = 2^n -1\text{.} $
Pero basta ver que uno de los factores no es trivial, así que mostrémoslo para el caso más fácil:
Si $2^a -1 = 1$, entonces $2^a = 2\text{,}$ por lo que $a =1\text{.}$ Lo que sería una contradicción, pues se había supuesto $a\neq 1\text{.}$ De este modo, sólo podría ocurrir que $2^a -1 = 2^n -1\text{.}$ Pero
$2^a -1 = 2^n -1$ implica que $2^a = 2^n \text{;}$ así, $a = n,$ lo que tampoco puede suceder.
Se concluye por tanto, que $2^a -1 \neq 1$ y $2^a -1 \neq 2^n -1\text{.}$ Ya con esto se verifica que, si $n$ no es primo, entonces $2^n – 1$ es compuesto.
$\square$
Proposición 5. Si $n$ es un número natural y $2^n + 1$ es un número primo, entonces $n$ tiene que ser una potencia de $2$.
Dem.- Sea $2^n + 1$ un número primo.
Primero tomemos el caso en que $n$ es impar. Entonces $n = 2k + 1$ para alguna $k \in \mathbb{N}$, y luego
$$2^{2k+1}+1 = (2 + 1)(2^{2k}- 2^{2k-1} + \cdots – 2^1 + 1)\text{.} $$ Ya que $3$ es un número distinto de $1$ y de $2^{2k+1}+1$, la descomposición anterior es no trivial. De lo que se concluye que, si $n$ es impar, entonces $2^n + 1$ es un número compuesto, pero como ello contradice la hipótesis de que $2^n + 1$ era primo, el caso en que $n$ es impar y primo, es imposible.
Ahora consideremos el caso en que $n$ es par. Entonces $n = 2k$ para alguna $k\in \mathbb{N}$. Tendríamos: $$2^{2k} + 1 = 4^{k_1} + 1 \text{.}$$
Luego entonces $k_1$ puede ser par o impar. Pero de estas opciones, la única que es viable es que $k_1$ sea par (pues si fuera impar, existiría una factorización no trivial para $4^{k_1} + 1$). Así, como $k_1$ es par, $k_1 = 2k_2$ para alguna $k_2 \in \mathbb{N}$. De forma que $$4^{k_1} + 1 = 4^{2k_2} + 1 = 2^{2^{2k_2}} + 1\text{.}$$
Por lo tanto, $k_1$ es una potencia de dos con $4^{k_1} + 1$ un número primo. Ahora, $$4^{2k_2} + 1 = 8^{k_2} + 1\text{,}$$
donde $k_2$ pudiera ser par o impar. Pero como $8^{k_2} + 1$ tiene una descomposición no trivial cuando $k_2$ es impar, sólo puede ocurrir que $k_2$ sea par. Así, $k_2 = 2k_3$ para alguna $k_3\in \mathbb{N}$ y $$8^{2k_3} + 1 = 4^{2^{2k_3}}\text{,}$$ por lo que $k_2$ es una potencia de 2.
Por otro lado, $$8^{2k_3} + 1 = 16^{k_3} + 1\text{.}$$
Nuevamente, $k_3$ pudiera ser par o impar, pero se descarta que sea impar. Así, $k_3 = 2k_4$ para algún $k_4 \in \mathbb{N}.$ Luego, $$ 16^{2k_4} + 1 = 8^{2^{2k_4}},$$ de donde se obtiene que $k_3$ es una potencia de $2$.
Este proceso infinito demuestra que $k_n$ será potencia de $2$. De tal modo que si $2^n + 1$ es primo, $n$ será par, y más aún, $n$ será potencia de $2$.
Finalmente, notemos que no todas las potencias de $2$ llevarán a que $2^n + 1$ sea primo.
$\square$
Proposición 6. Si $n\geq 2$, existe $p$ primo tal que $n < p < n!\text{.}$
Dem.- Ya que $n! = n \cdot (n-1) \cdot (n-2) \cdot \cdots \cdot 3 \cdot 2 \cdot 1\text{,}$ entonces todos los $x\in \mathbb{N}$ tales que $1\leq x \leq n$ dividen a $n!$: $x \enspace \vert \enspace n!\text{.}$
Por lo que $x \nmid n! – 1 \quad \forall 1\leq x \leq n\text{.}$
- Si $n! – 1$ es primo, $n < n! – 1 < n!$.
- Si $n! – 1$ no es primo, por el teorema fundamental de la aritmética existe su descomposición en primos; sin embargo, ya que $x \nmid n! – 1 \quad \forall 1\leq x \leq n\text{,}$ necesariamente hay un primo $p$ distinto de $x$ y mayor que $n$ que sí divida a $n! -1.$ Así, $n < p < n!.$
$\square$