Damos dos pruebas. La primera es probablemente la prevista. La segunda es tal vez más interesante, y ciertamente más informativa. Por un lado, muestra que hay infinitos primos de una manera muy diferente a la prueba estándar que se remonta a la de Euclides Elementos .
Primera prueba: Tenga en cuenta que $p_{k+1}\le (p_1p_2\cdots p_k)+1$ ya que algún primo $p$ divide $(p_1p_2\cdots p_k)+1$ y $p$ no puede ser ninguno de $p_1,p_2,\dots,p_k$ . Ahora usamos la hipótesis de inducción. Tenemos $p_1p_2\cdots p_k\le 2^{e_k}$ donde $$e_k \le 2^0 +2^1+\cdots +2^{k-1}.$$ La serie de la derecha es una serie geométrica con suma $2^k-1$ . Así que $p_1p_2\cdots p_k <2^{2^k}$ y por lo tanto $(p_1p_2\cdots p_k)+1 \le 2^{2^k}$ .
Segunda prueba: Dejemos que $n \ge 1$ . Demostraremos que $2^{2^n}-1$ tiene al menos $n$ factores primos distintos. Ninguno de estos factores primos es igual a $2$ . Así que hay al menos $n+1$ primos que son $\le 2^{2^n}$ .
Demostramos que $2^{2^n}-1$ tiene al menos $n$ factores primos por inducción en $n$ . Supongamos que sabemos que para un determinado $k\ge 1$ Hay por lo menos $k$ primos que dividen $2^{2^k}-1$ . Queremos demostrar que hay al menos $k+1$ primos que dividen $2^{2^{k+1}}-1$ .
Utilizamos la conocida factorización (diferencia de dos cuadrados) $$2^{2^{k+1}}-1=(2^{2^k} -1)(2^{2^k} +1).$$ Por la hipótesis de la inducción, $2^{2^k} -1$ tiene al menos $k$ factores primos. Sea $p$ sea un factor primo de $2^{2^k}+1$ . Entonces $p$ no puede dividir $2^{2^k} -1$ ya que si lo hiciera, dividiría la diferencia $(2^{2^k} +1)-(2^{2^k} -1)$ que es $2$ . Pero como $2^{2^k}+1$ es impar, $p$ debe ser impar. Por lo tanto, además de la $k$ factores primos de $2^{2^k} -1$ el número $2^{2^{k+1}} -1$ tiene al menos un factor primo adicional $p$ para un total de al menos $k+1$ .
Comentario: La inducción formal oculta la simplicidad de la idea. Todo se reduce al hecho de que, por ejemplo, $$2^{2^5}-1=(2^{2^1}-1)(2^{2^1}+1)(2^{2^2}+1)(2^{2^3}+1)(2^{2^4}+1).$$
