Cómo mostrar $p_n$ $\leq$ $2^{2^n}$?

Question

Deje $p_n$ $n_{th}$ prime (por ejemplo,$p_1 = 2$; $p_2 = 3$; $p_3 = 5$). Mostrar que $p_n \leq 2^{2^n}$ todos los $n$.

No veo cómo puedo aproximar el valor de $p_n$. Necesito algo como el teorema de los números primos? Pero el curso no enseñar todavía.

Answer 1

La idea es que el uso de la inducción, y que se puede expandir en Euclid el argumento de que existen infinitos números primos para mostrar que $p_n$ está acotada arriba por $2^{2^n}$.

Supongamos $p_i \leq 2^{2^i}$ todos los $i \leq n$. Ahora $p_1 \cdot p_2 \cdot \ldots \cdot p_n + 1$ no es divisible por ninguno de los números primos $p_1, \ldots, p_n$, por lo que

$$p_{n+1} \leq \prod_{i=1}^n \ p_i + 1$$

En sustitución de los anteriores límites en $p_i$ y el uso de $\sum_{i=1}^n 2^i = 2^{n+1} - 2$, obtenemos

$$p_{n+1} \leq \left(\prod_{i=1}^n \ 2^{2^i}\right) + 1 = \left(2^{\sum_{i=1}^n 2^i}\right) + 1 = 2^{2^{n+1} - 2} + 1 \leq 2^{2^{n+1}}$$

Answer 2

Es suficiente para demostrar que para cualquier entero positivo $n$, hay, al menos, $n$ de los números primos que se $\le 2^{2^n}$. Vamos a mostrar que, de hecho, $2^{2^n}-1$ siempre tiene al menos $n$ distintos primer divisores. (Todos estos son, necesariamente,$<2^{2^n}$.)

Supongamos que sabemos que $2^{2^k}-1$ tiene al menos $k$ distintos primer divisores. A continuación, debemos mostrar ese $2^{2^{k+1}}-1$ tiene al menos $k+1$ distintos primer divisores.

Tenga en cuenta que $$2^{2^{k+1}}-1=(2^{2^k}-1)(2^{2^k}+1).$$ Los números de $2^{2^k}-1$ $2^{2^k}+1$ son relativamente primos. Esto es porque cualquier número que divide ambos deben dividir su diferencia, que es $2$. Pero cada uno de $2^{2^k}-1$ $2^{2^k}+1$ es impar, por lo que el mayor entero que divide a ambos de ellos no puede ser $2$, y por lo tanto debe ser $1$.

Así, el primer divisores de $2^{2^{k+1}}-1$ son los primos divisores de $2^{2^k}-1$ (de los cuales hay al menos $k$), junto con el primer divisores de $2^{2^k}+1$ (de los cuales hay al menos $1$), para un total de, al menos,$k+1$.

Comentario: El argumento anterior también nos dice que para cualquier entero positivo $n$, hay, al menos, $n$ números primos. Esto nos da una prueba de la infinitud de los números primos que es un poco diferente de la habitual "Euclides" de la prueba.

Answer 3

Aquí nos fijamos en una más pequeña, y como me siento, más conveniente obligado:

Asumir cada uno de los prime sería el doble de la anterior, que hemos tenido, empezando con el primer primer p=2 la secuencia de $ \small q, 2q, 4q, 8q, \ldots 2^n q , \ldots...$ y el n'th prime fueron delimitadas por $ \small q2^n $, que es mucho menor que el determinado $ \small 2^{2^n} $ . Ahora bien, si recordamos que entre n y 2n siempre hay un primo, por lo tanto la distancia a la siguiente es incluso menor que n , entonces esto es suficiente para la prueba en general y sólo hay que mirar en los casos iniciales de posibles excepciones.