Teorema de Euclides

El teorema de Euclides sobre la infinitud de los números primos es el siguiente:

El conjunto formado por los números primos es infinito. Euclides (~325 - 265 a.C)

Demostración de Euclides

Euclides formuló la primera demostración en la proposición 20 del libro IX de su obra Elementos.​ Una adaptación común de esta demostración original sigue así:

Se toma un conjunto arbitrario pero finito de números primos p₁, p₂, ···, p_n, y se considera el producto de todos ellos más uno, q=p₁p₂ ··· p_n+1. Este número es obviamente mayor que 1 y distinto de todos los primos p_i de la lista. El número q puede ser primo o compuesto. Si es primo tendremos un número primo que no está en el conjunto original. Si, por el contrario, es compuesto, entonces existirá algún factor p que divida a q (q=p_n+1). Suponiendo que p es alguno de los p_i, se deduce entonces que p divide a la diferencia q-p₁p₂ ··· p_n=1, pero ningún número primo divide a 1, es decir, se ha llegado a un absurdo por suponer que p está en el conjunto original. La consecuencia es que el conjunto que se escogió no es exhaustivo, ya que existen números primos que no pertenecen a él, y esto es independiente del conjunto finito que se tome.

Considerense los siguientes teoremas:

Teorema 1. Todo entero n > 1 es primo o admite al menos un divisor primo. Demostración: Procedamos por inducción sobre n. Cuando n = 2 el resultado se cumple, pues los únicos divisores de 2 son ±1, ±2 y por lo tanto es primo. Supongamos que para entero k ∈ {2, 3, . . . , n − 1} el resultado se cumple y veamos ahora qué ocurre cuando k = n . Si n es primo no habría nada que probar, así que podemos suponer que n es compuesto y por lo tanto n = rt para ciertos enteros r, t ∈ Z>0. Por propiedades de divisibilidad r < n y t < n por lo que aplica la hipótesis inductiva y entonces n admite un divisor primo.

Teorema 2 (Teorema de Euclides). Existe una infinidad de números primos. Demostración de Euclides. Supongamos que sólo existe un número finito de números primos, digamos p1, p2, . . . , pn. Sea N = $Qni=1pi+1$. Cómo N > 1, entonces es primo o producto de primos. Como N > pi para i ∈ {1, 2, . . . , n} deducimos que N debe ser compuesto, sin embargo, ninguno de los pi divide a N, pues de hacerlo se tendría que Error al representar (error de sintaxis): {\displaystyle pi | N − Yn i=1 pi y por lo tanto pi | 1 } lo que no tiene sentido. Se ha llegado así a una contradicción al teorema 1, la cual se originó al suponer que los números primos son finitos

Existen numerosas demostraciones parecidas a ésta, que se formulan a continuación:

Reformulación de Kummer

Supóngase que existe una cantidad finita de números primos p₁ < p₂ < p₃ < ... < p_r. Sea N = p₁·p₂·p₃·...·p_r > 2. El entero N-1, al ser producto de primos, tiene un divisor p_i que también es divisor de N; así que p_i divide a N - (N-1) = 1. Esto es absurdo, por lo que tiene que haber infinitos números primos.

Demostración de Hermite

Sea n=1, 2, 3, ... y q_n el factor primo más pequeño de n! + 1 para cada n. Como q_n tiene que ser mayor que n, se deduce que esta sucesión contiene infinitos elementos distintos, y que por tanto existen infinitos números primos.

Demostración de Stieltjes

Supóngase que existprimo que no divide a Q: contradicción.

Demostración de Goldbach (1730)

Esta demostración se basa en los números de Fermat, es decir, los números de la forma :$F_{n}=2^{2^{n}}+1$.

Lema: Dos números de Fermat distintos Fm y Fn son primos entre sí. (Goldbach, 1730)

Para cada número de Fermat F_n, escójase un divisor primo p_n. Como los números de Fermat son primos entre sí, sabemos que dos primos cualesquiera p_m y p_n son distintos. Así, hay al menos un número primo p_n por cada número de Fermat F_n, es decir, al menos un número primo por cada número entero n.

Esta demostración también es válida si se toma otra secuencia infinita de números naturales que son primos entre sí, como la secuencia de Sylvester.

Otras demostraciones

Demostración de Euler

Sea Q el producto de todos los primos. Sea φ(n) la función φ de Euler definida como el número de enteros menores que n y coprimos con él. Entonces φ(Q) es igual al producto de los números que resultan de restarle 1 a cada uno de los números primos, es decir,

φ(Q) = (2-1)·(3-1)·(5-1)·(7-1)·(11-1)·... = 1·2·4·6·10·...

Uno de los números enteros coprimos con Q es 1. Aun así, hay al menos otro entero en el intervalo [2,Q] que no tiene factor común con Q. Ese entero no puede tener ningún factor primo, porque están todos en Q, así que debe ser igual a 1, con lo que se llega a una contradicción.

Demostración topológica de Furstenberg (1955)

Defínase una topología en el conjunto de los números enteros empleando progresiones aritméticas (de −∞ a +∞). Esto genera un espacio topológico. Para cada número p, sea A_p el conjunto de todos los múltiplos de p. A_p es cerrado, porque su complementario es la unión de todas las demás progresiones aritméticas con diferencia p. Ahora, sea A la unión de las progresiones A_p. Si hay un número finito de números primos, entonces A es una unión finita de conjuntos cerrados, y por tanto A es cerrado. Sin embargo, todos los números enteros, salvo -1 y 1, son múltiplos de algún número primo, así que el complementario de A es {-1, 1} que no es abierto. Esto muestra que A no es una unión finita y que existen infinitos primos.

Primera demostración

Supongamos que sólo hay una cantidad finita de números primos, digamos p1, p2, . . . , pn. Sea N = Qn i=1 pi . Ahora, sea q = mín{pi : pi | (N! + 1).} Tal q existe, por el teorema fundamental de la aritmética. Si q < N entonces q - (N! + 1), pues q | N! por lo tanto q > N y as´ı q > pi para i = 1, . . . , n por lo tanto, existe una cantidad infinita de números primos. Con una idea derivada de la prueba anterior se tiene la siguiente.

Segunda demostración

Se hará uso del lema siguiente: si n > 2, entonces existe un primo p tal que n < p < n! En efecto, sea z = n! − 1, entonces z > 1, por el teorema fundamental de la aritmética existe un divisor primo p tal que p ≤ z. Si p ≤ n entonces p debe dividir a 1, lo que es un absurdo, por lo tanto n < p ≤ n! − 1 < n!. Ya probado el lema, el teorema queda demostrado al ser N un conjunto no acotado. A continuación se presenta otra demostración, en la cual se hace uso nuevamente del 1, en conjunto con propiedades elementales de la divisibilidad en Z, la demostración es por contradicción.

Tercera demostración

Supongamos que existe sólo una cantidad finita de números primos, digamos p1, . . . , pn. Ahora sea N = Qn i=1 pi y definamos a = Pn i=1 1 pi , entonces aN = (Xn i=1 1 pi )N = Xn i=1 N pi ∈ Z Por lo tanto, existe pk en el conjunto de los números primos tal que pk | aN, de donde en particular pk | N pi , i 6= k Lo que implica que N pk = aN − Xn i=1, i6=k N pi De donde pk | N pk lo que es una contradicción. Así, los números primos son infinitos.

Cuarta demostración

es llevada a cabo con la ayuda de la famosa función indicatriz de Euler. Cuarta demostración. Suponga que existe sólo una cantidad finita de números primos, digamos p1, . . . , pn y sea N = Yn i=1 pi Entonces, para todo 1 < n < N se tiene que mcd(n, N) 6= 1, es decir, n y N no son primos relativos, dada la definici´on de N. Aplicando ahora la definición de la función φ (el número de enteros menores o iguales a N y primos relativos con ´el) se tiene que φ(N) = 1. Por otra parte, φ es una función aritmética multiplicativa, entonces φ(N) = φ( Yn i=1 pi) = Yn i=1 (pi − 1) > 1 Es decir, 1 > 1, lo que es una contradicción. De la anterior tenemos una variante; de propiedades del máximo común divisor tenemos:

Quinta demostración

Supongamos que existe s´olo una cantidad finita de números primos, digamos p1, . . . , pn y sea N = Yn i=1 pi , entonces para todo 1 < n < N se tiene que mcd(n, N) 6= 1, es decir, n y N no son primos relativos dada la definición de N. En particular ello implica que mcd(N, N − 1) 6= 1 lo que es una contradicción, pues para cualquier n ∈ Z se tiene que mcd(n, n − 1) = 1.