Teorema de Euclides es una declaración fundamental en la teoría de números que afirma que hay infinitamente muchos primeros números. Fue probado por primera vez por Euclides en su obra Elements . Hay varias pruebas del teorema.
Prueba de Euclides
Euclides ofreció una prueba publicada en su obra Elementos (Libro IX, Proposición 20), [1] que se parafrasea aquí. [2]
Considere cualquier lista finita de números primos p 1 , p 2 , ..., p n . Se mostrará que existe al menos un número primo adicional que no está en esta lista. Sea P el producto de todos los números primos de la lista: P = p 1 p 2 ... p n . Sea q = P + 1. Entonces q es primo o no:
- Si q es primo, entonces hay al menos un primo más que no está en la lista.
- Si q no es primo, entonces algún factor primo p divide a q . Si este factor p estuviera en nuestra lista, entonces dividiría a P (ya que P es el producto de todos los números de la lista); pero p también divide a P + 1 = q , como se acaba de indicar. Si p divide a P y también a q, entonces p también debe dividir la diferencia [3] de los dos números, que es ( P + 1) - P o solo 1. Como ningún número primo divide a 1, p no puede estar en la lista. Esto significa que existe al menos un número primo más además de los de la lista.
Esto prueba que para cada lista finita de números primos hay un número primo que no está en la lista. [4] En la obra original, como Euclides no tenía forma de escribir una lista arbitraria de números primos, utilizó un método que aplicaba con frecuencia, es decir, el método del ejemplo generalizable. Es decir, elige solo tres números primos y, utilizando el método general descrito anteriormente, demuestra que siempre puede encontrar un número primo adicional. Euclides presumiblemente asume que sus lectores están convencidos de que una prueba similar funcionará, sin importar cuántos números primos se escojan originalmente. [5]
A menudo se informa erróneamente que Euclides ha demostrado este resultado por contradicción comenzando con la suposición de que el conjunto finito inicialmente considerado contiene todos los números primos, [6] aunque en realidad es una prueba por casos , un método de prueba directa . El filósofo Torkel Franzén , en un libro sobre lógica, afirma: "La prueba de Euclides de que hay infinitos números primos no es una prueba indirecta [...] El argumento a veces se formula como una prueba indirecta reemplazándolo con el supuesto 'Suponga q 1 , ... q n son todos los números primos '. Sin embargo, dado que esta suposición ni siquiera se usa en la prueba, la reformulación no tiene sentido ". [7]
Variaciones
Existen varias variaciones de la prueba de Euclides, incluidas las siguientes:
El factorial n ! de un entero positivo n es divisible por todo entero de 2 an , ya que es el producto de todos ellos. Por lo tanto, n ! + 1 no es divisible por ninguno de los números enteros de 2 an , inclusive (da un resto de 1 cuando se divide por cada uno). ¡Por lo tanto, n ! + 1 es primo o divisible por un primo mayor que n . En cualquier caso, por cada entero positivo n , hay al menos un primo mayor que n . La conclusión es que el número de primos es infinito. [8]
Prueba de Euler
Otra prueba, del matemático suizo Leonhard Euler , se basa en el teorema fundamental de la aritmética : que cada entero tiene una factorización prima única. Si P es el conjunto de todos los números primos, Euler escribió que:
La primera igualdad viene dada por la fórmula de una serie geométrica en cada término del producto. La segunda igualdad es un caso especial de la producto Euler fórmula para la función zeta de Riemann . Para mostrar esto, distribuya el producto sobre la suma:
En el resultado, cada producto de los números primos aparece exactamente una vez y, por lo tanto, según el teorema fundamental de la aritmética, la suma es igual a la suma de todos los números enteros.
La suma de la derecha es la serie armónica , que diverge. Por tanto, el producto de la izquierda también debe divergir. Dado que cada término del producto es finito, el número de términos debe ser infinito; por lo tanto, hay un número infinito de números primos.
La prueba de Erdős
Paul Erdős dio una demostración [9] que también se basa en el teorema fundamental de la aritmética. Cada entero positivo tiene una factorización única en un número libre de cuadrados y un número cuadrado rs 2 . Por ejemplo, 75,600 = 2 4 3 3 5 2 7 1 = 21 ⋅ 60 2 .
Deje que N sea un número entero positivo, y dejar que k es el número de números primos menos de o igual a N . Llame a esos primos p 1 , ..., p k . Cualquier entero positivo que sea menor o igual que N se puede escribir en la forma
donde cada e i es 0 o 1 . Hay 2 k formas de formar la parte libre de cuadrados de a . Y s 2 puede haber como máximo N , por lo que s ≤ √ N . Por lo tanto, como máximo 2 k √ N números se pueden escribir en esta forma. En otras palabras,
O, reordenando, k , el número de primos menores o iguales que N , es mayor o igual que1/2log 2 N . Dado que N era arbitrario, k puede ser tan grande como se desee eligiendo N apropiadamente.
Prueba de Furstenberg
En la década de 1950, Hillel Furstenberg introdujo una prueba por contradicción utilizando topología de conjuntos de puntos . [10]
Defina una topología en los enteros Z , denominada topología de enteros uniformemente espaciados , declarando que un subconjunto U ⊆ Z es un conjunto abierto si y solo si es el conjunto vacío , ∅, o es una unión de secuencias aritméticas S ( a , b ) (para a ≠ 0), donde
Entonces se sigue una contradicción de la propiedad de que un conjunto finito de enteros no puede ser abierto y de la propiedad de que los conjuntos de bases S ( a , b ) son abiertos y cerrados , ya que
no se puede cerrar porque su complemento es finito, pero es cerrado porque es una unión finita de conjuntos cerrados.
Algunas pruebas recientes
Prueba utilizando el principio de inclusión-exclusión
Juan Pablo Pinasco ha escrito la siguiente prueba. [11]
Sean p 1 , ..., p N los N primos más pequeños . Luego, por el principio de inclusión-exclusión , el número de enteros positivos menores o iguales ax que son divisibles por uno de esos números primos es
Dividiendo por x y dejando x → ∞ da
Esto se puede escribir como
Si no existen otros primos distintos de p 1 , ..., p N , entonces la expresión en (1) es igual a y la expresión en (2) es igual a 1, pero es evidente que la expresión en (3) no es igual a 1. Por lo tanto, debe haber más números primos que p 1 , ..., p N .
Prueba con la fórmula de de Polignac
En 2010, Junho Peter Whang publicó la siguiente prueba por contradicción. [12] Sea k cualquier número entero positivo. Luego, de acuerdo con la fórmula de de Polignac (en realidad debido a Legendre )
dónde
Pero si solo existen un número finito de primos, entonces
(el numerador de la fracción aumentaría exponencialmente individualmente mientras que según la aproximación de Stirling el denominador crece más rápidamente que exponencialmente individualmente), contradiciendo el hecho de que para cada k el numerador es mayor o igual que el denominador.
Prueba por construcción
Filip Saidak dio la siguiente prueba por construcción , que no usa reductio ad absurdum [13] o el Lema de Euclides (que si un primo p divide ab, entonces debe dividir a o b ).
Puesto que cada número natural (> 1) tiene al menos un factor primordial , y dos números sucesivos n y ( n + 1) no tienen ningún factor en común, el producto n ( n + 1) tiene más diferentes factores primos que el número n en sí . Entonces, la cadena de números pronicos :
1 × 2 = 2 {2}, 2 × 3 = 6 {2, 3}, 6 × 7 = 42 {2, 3, 7}, 42 × 43 = 1806 {2, 3, 7, 43}, 1806 × 1807 = 3263442 {2, 3, 7, 43, 13, 139}, · · ·
proporciona una secuencia de conjuntos de números primos crecientes ilimitados.
Prueba usando la irracionalidad de π
Al representar la fórmula de Leibniz para π como un producto de Euler se obtiene [14]
Los numeradores de este producto son los números primos impares y cada denominador es el múltiplo de cuatro más cercano al numerador.
Si hubiera un número finito de primos, esta fórmula mostraría que π es un número racional cuyo denominador es el producto de todos los múltiplos de 4 que son uno más o menos que un número primo, contradiciendo el hecho de que π es irracional .
Prueba usando la teoría de la información
Alexander Shen y otros [ ¿quién? ] han presentado una prueba que utiliza la incompresibilidad : [15]
Suponga que solo hay k primos ( p 1 ... p k ). Por el teorema fundamental de la aritmética , cualquier entero positivo n podría representarse como:
donde los exponentes enteros no negativos e i junto con la lista de números primos de tamaño finito son suficientes para reconstruir el número. Desdepara todo yo , se sigue que todo (dónde denota el logaritmo en base 2).
Esto produce una codificación para n del siguiente tamaño (usando la notación O grande ):
- bits.
Esta es una codificación mucho más eficiente que representar n directamente en binario, lo que requierebits. Un resultado establecido en la compresión de datos sin pérdidas establece que, en general, no se pueden comprimir N bits de información en menos de N bits. La representación anterior viola esto por mucho cuando n es lo suficientemente grande ya que.
Por tanto, el número de primos no debe ser finito.
Resultados más fuertes
Los teoremas de esta sección implican simultáneamente el teorema de Euclides y otros resultados.
Teorema de Dirichlet sobre progresiones aritméticas
El teorema de Dirichlet establece que para dos enteros coprimos positivos cualesquiera a y d , hay infinitos números primos de la forma a + nd , donde n también es un entero positivo. En otras palabras, hay infinitos números primos que son congruentes con un módulo d .
Teorema de los números primos
Sea π ( x ) la función de conteo de primos que da el número de primos menores o iguales ax , para cualquier número real x . El teorema del número primo a continuación que x / log x es una buena aproximación a π ( x ) , en el sentido de que el límite de la cociente de las dos funciones pi ( x ) y x / log x como x aumenta sin límite es 1 :
Usando la notación asintótica, este resultado se puede reformular como
Esto produce el teorema de Euclides, ya que
Teorema de Bertrand-Chebyshev
En teoría de números , el postulado de Bertrand es un teorema que establece que para cualquier número entero , siempre existe al menos un número primo tal que
El teorema de Bertrand-Chebyshev también se puede establecer como una relación con , dónde es la función de conteo de primos (número de primos menores o iguales que):
- , para todos .
Esta afirmación fue conjeturada por primera vez en 1845 por Joseph Bertrand [16] (1822-1900). El mismo Bertrand verificó su declaración para todos los números en el intervalo [2, 3 × 10 6 ]. Su conjetura fue completamente demostró por Chebyshev (1821-1894) en 1852 [17] y por lo tanto el postulado también se llama el teorema de Bertrand-Chebyshev o el teorema de Chebyshev .
notas y referencias
- ^ James Williamson (traductor y comentarista), Los elementos de Euclides, con disertaciones , Clarendon Press , Oxford, 1782, página 63.
- ^ Ore, Oystein (1988) [1948], Teoría de números y su historia , Dover, p. sesenta y cinco
- ^ En general, para cualquier número entero a , b , c si y , luego . Para obtener más información, consulte Divisibilidad .
- ^ La formulación exacta de la afirmación de Euclides es: "Los números primos son más numerosos que cualquier multitud propuesta de números primos".
- ^ Katz, Victor J. (1998), A History of Mathematics / an Introduction (2ª ed.), Addison Wesley Longman, p. 87
- ^ Michael Hardy y Catherine Woodgold, "Prime Simplicity", Mathematical Intelligencer , volumen 31, número 4, otoño de 2009, páginas 44–52.
- ^ Franzén, Torkel (2004), Inexhaustibility: A Non-exhaustive Treatment , AK Peters, Ltd, p. 101
- ^ Bostock, Linda; Chandler, Suzanne; Rourke, C. (1 de noviembre de 2014). Más matemáticas puras . Nelson Thornes. pag. 168. ISBN 9780859501033.
- ^ Havil, Julian (2003). Gamma: Explorando la constante de Euler . Prensa de la Universidad de Princeton. pp. 28 -29. ISBN 0-691-09983-9.
- ^ Furstenberg, Harry (1955). "Sobre la infinitud de los números primos". American Mathematical Monthly . 62 (5): 353. doi : 10.2307 / 2307043 . JSTOR 2307043 . Señor 0068566 .
- ^ Juan Pablo Pinasco, "Nuevas pruebas de los teoremas de Euclides y Euler", American Mathematical Monthly , volumen 116, número 2, febrero de 2009, páginas 172-173.
- ^ Junho Peter Whang, "Otra prueba de la infinitud de los números primos", American Mathematical Monthly , volumen 117, número 2, febrero de 2010, página 181.
- ^ Saidak, Filip (diciembre de 2006). "Una nueva prueba del teorema de Euclides" . American Mathematical Monthly . 113 (10). doi : 10.2307 / 27642094 .
- ^ Debnath, Lokenath (2010), El legado de Leonhard Euler: Un tributo tricentenario , World Scientific, p. 214, ISBN 9781848165267.
- ^ Shen, Alexander (2016), complejidad de Kolmogorov y aleatoriedad algorítmica (PDF) , AMS, p. 245
- ^ Bertrand, Joseph (1845), "Mémoire sur le nombre de valeurs que peut prendre une fonction quand on y permute les lettres qu'elle renferme". , Journal de l'École Royale Polytechnique (en francés), 18 (Cahier 30): 123–140.
- ^ Tchebychev, P. (1852), "Mémoire sur les nombres premiers". (PDF) , Journal de mathématiques pures et appliquées , Série 1 (en francés): 366–390. (Prueba del postulado: 371-382). Véase también Mémoires de l'Académie Impériale des Sciences de St. Pétersbourg, vol. 7, págs. 15-33, 1854
enlaces externos
- Weisstein, Eric W. "Teorema de Euclides" . MathWorld .
- Elementos de Euclides, Libro IX, Prop.20 (prueba de Euclides, en el sitio web de David Joyce en la Universidad de Clark)