Teorema de Euclides - Euclid's theorem

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), que se parafrasea aquí.

Considere cualquier lista finita de números primos p ₁ ,  p ₂ , ...,  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 ₁ p ₂ ... 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, a saber, q mismo.
• 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 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 aparte 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. 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.

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, aunque en realidad es una prueba por casos , un método de prueba directa . El filósofo Torkel Franzén , en un libro de 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 ₁ , ... q _n son todos los números primos '. Sin embargo, dado que esta suposición ni siquiera se usa en la demostración, la reformulación no tiene sentido ".

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.

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. Lo que escribió Euler (no con esta notación moderna y, a diferencia de los estándares modernos, sin restringir los argumentos en sumas y productos a ningún conjunto finito de enteros) es equivalente a la afirmación de que tenemos

${\ Displaystyle \ prod _ {p \ in P_ {k}} {\ frac {1} {1 - {\ frac {1} {p}}}} = \ sum _ {n \ in N_ {k}} { \ frac {1} {n}},}$

donde denota el conjunto de los k primeros números primos, y es el conjunto de los enteros positivos cuyos factores primos están todos en${\ Displaystyle P_ {k}}$${\ Displaystyle N_ {k}}$${\ Displaystyle P_ {k}.}$

Para mostrar esto, uno se expande cada factor en el producto como una serie geométrica , y distribuye el producto sobre la suma (este es un caso especial de la producto Euler fórmula para la función zeta de Riemann ).

${\ Displaystyle {\ begin {alineado} \ prod _ {p \ in P_ {k}} {\ frac {1} {1 - {\ frac {1} {p}}}} & = \ prod _ {p \ en P_ {k}} \ sum _ {i \ geq 0} {\ frac {1} {p ^ {i}}} \\ & = \ left (\ sum _ {i \ geq 0} {\ frac {1 } {2 ^ {i}}} \ right) \ cdot \ left (\ sum _ {i \ geq 0} {\ frac {1} {3 ^ {i}}} \ right) \ cdot \ left (\ sum _ {i \ geq 0} {\ frac {1} {5 ^ {i}}} \ right) \ cdot \ left (\ sum _ {i \ geq 0} {\ frac {1} {7 ^ {i} }} \ derecha) \ cdots \\ & = \ sum _ {\ ell, m, n, p, \ ldots \ geq 0} {\ frac {1} {2 ^ {\ ell} 3 ^ {m} 5 ^ {n} 7 ^ {p} \ cdots}} \\ & = \ sum _ {n \ in N_ {k}} {\ frac {1} {n}}. \ end {alineado}}}$

En la penúltima suma, cada producto de los números primos aparece exactamente una vez, por lo que la última igualdad es verdadera según el teorema fundamental de la aritmética. En su primer corolario de este resultado, Euler denota mediante un símbolo similar al «infinito absoluto» y escribe que la suma infinita en el enunciado es igual al «valor» , al que el producto infinito es, por tanto, también igual (en terminología moderna esto es equivalente decir que la suma parcial de la serie armónica diverge asintóticamente como ). Luego, en su segundo corolario, Euler señala que el producto ${\ Displaystyle \ infty}$${\ Displaystyle \ log \ infty}$${\ Displaystyle x}$${\ Displaystyle \ log x}$

${\ Displaystyle \ prod _ {n \ geq 2} {\ frac {1} {1 - {\ frac {1} {n ^ {2}}}}}}$

converge al valor finito 2, y que en consecuencia hay más números primos que cuadrados («sequitur infinities plures esse numeros primos»). Esto prueba el Teorema de Euclides.

Símbolo utilizado por Euler para denotar el infinito

En el mismo artículo (Teorema 19) Euler de hecho usó la igualdad anterior para probar un teorema mucho más fuerte que era desconocido antes que él, a saber, que la serie

${\ Displaystyle \ sum _ {p \ in P} {\ frac {1} {p}}}$

es divergente , donde P denota el conjunto de todos los números primos (Euler escribe que la suma infinita , que en terminología moderna equivale a decir que la suma parcial hasta de esta serie se comporta asintóticamente como ). ${\ Displaystyle = \ log \ log \ infty}$${\ Displaystyle x}$${\ Displaystyle \ log \ log x}$

La prueba de Erdős

Paul Erdős dio una demostración 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 ² . Por ejemplo, 75,600 = 2 ⁴ 3 ³ 5 ² 7 ¹ = 21 ⋅ 60 ² .

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 ₁ , ..., p _k . Cualquier entero positivo que sea menor o igual que N se puede escribir en la forma

${\ Displaystyle \ left (p_ {1} ^ {e_ {1}} p_ {2} ^ {e_ {2}} \ cdots p_ {k} ^ {e_ {k}} \ right) s ^ {2}, }$

donde cada e _i es 0 o 1 . Hay 2 ^k formas de formar la parte libre de cuadrados de a . Y s ² 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,

${\ Displaystyle N \ leq 2 ^ {k} {\ sqrt {N}}.}$

O, reordenando, k , el número de primos menores o iguales que N , es mayor o igual que 1/2log ₂ 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 .

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

${\ Displaystyle S (a, b) = \ {an + b \ mid n \ in \ mathbb {Z} \} = a \ mathbb {Z} + b.}$

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

${\ Displaystyle \ mathbb {Z} \ setminus \ {- 1, + 1 \} = \ bigcup _ {p \ mathrm {\, prime}} S (p, 0)}$

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.

Sean p ₁ , ...,  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

${\ Displaystyle {\ begin {alineado} 1+ \ sum _ {i} \ left \ lfloor {\ frac {x} {p_ {i}}} \ right \ rfloor - \ sum _ {i <j} \ left \ lfloor {\ frac {x} {p_ {i} p_ {j}}} \ right \ rfloor & + \ sum _ {i <j <k} \ left \ lfloor {\ frac {x} {p_ {i} p_ {j} p_ {k}}} \ right \ rfloor - \ cdots \\ & \ cdots \ pm (-1) ^ {N + 1} \ left \ lfloor {\ frac {x} {p_ {1} \ cdots p_ {N}}} \ right \ rfloor. \ qquad (1) \ end {alineado}}}$

Dividiendo por x y dejando x  → ∞ da

${\ Displaystyle \ sum _ {i} {\ frac {1} {p_ {i}}} - \ sum _ {i <j} {\ frac {1} {p_ {i} p_ {j}}} + \ suma _ {i <j <k} {\ frac {1} {p_ {i} p_ {j} p_ {k}}} - \ cdots \ pm (-1) ^ {N + 1} {\ frac {1 } {p_ {1} \ cdots p_ {N}}}. \ qquad (2)}$

Esto se puede escribir como

${\ Displaystyle 1- \ prod _ {i = 1} ^ {N} \ left (1 - {\ frac {1} {p_ {i}}} \ right). \ qquad (3)}$

Si no existen otros primos distintos de p ₁ , ...,  p _N , entonces la expresión en (1) es igual a  y la expresión en (2) es igual a 1, pero claramente la expresión en (3) no es igual a 1. Por lo tanto, tiene que haber más números primos que   p ₁ , ...,  p _N . ${\ Displaystyle \ lfloor x \ rfloor}$

Prueba con la fórmula de de Polignac

En 2010, Junho Peter Whang publicó la siguiente prueba por contradicción. Sea k cualquier número entero positivo. Luego, de acuerdo con la fórmula de de Polignac (en realidad debido a Legendre )

${\ Displaystyle k! = \ prod _ {p {\ text {prime}}} p ^ {f (p, k)}}$

dónde

${\ Displaystyle f (p, k) = \ left \ lfloor {\ frac {k} {p}} \ right \ rfloor + \ left \ lfloor {\ frac {k} {p ^ {2}}} \ right \ rfloor + \ cdots.}$

${\ Displaystyle f (p, k) <{\ frac {k} {p}} + {\ frac {k} {p ^ {2}}} + \ cdots = {\ frac {k} {p-1} } \ leq k.}$

Pero si solo existen un número finito de primos, entonces

${\ Displaystyle \ lim _ {k \ to \ infty} {\ frac {\ left (\ prod _ {p} p \ right) ^ {k}} {k!}} = 0,}$

(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 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

${\ Displaystyle {\ frac {\ pi} {4}} = {\ frac {3} {4}} \ times {\ frac {5} {4}} \ times {\ frac {7} {8}} \ veces {\ frac {11} {12}} \ veces {\ frac {13} {12}} \ veces {\ frac {17} {16}} \ veces {\ frac {19} {20}} \ veces { \ frac {23} {24}} \ times {\ frac {29} {28}} \ times {\ frac {31} {32}} \ times \ cdots}$

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 números primos, esta fórmula mostraría que π es un número racional, lo que contradice el hecho de que π es irracional .

Prueba usando la teoría de la información

Alexander Shen ha presentado una prueba que usa la incompresibilidad :

Supongamos que solo hay k primos ( p ₁ ...  p _k ). Por el teorema fundamental de la aritmética , cualquier entero positivo n podría representarse como:

${\ Displaystyle n = {p_ {1}} ^ {e_ {1}} {p_ {2}} ^ {e_ {2}} \ cdots {p_ {k}} ^ {e_ {k}},}$

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. Dado que para todo i , se sigue que todo (donde denota el logaritmo en base 2). ${\ Displaystyle p_ {i} \ geq 2}$${\ Displaystyle e_ {i} \ leq \ lg n}$${\ Displaystyle \ lg}$

Esto produce una codificación para n del siguiente tamaño (usando la notación O grande ):

${\ Displaystyle O ({\ text {tamaño de lista principal}} + k \ lg \ lg n) = O (\ lg \ lg n)}$ bits.

Esta es una codificación mucho más eficiente que representar n directamente en binario, que toma bits. 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 desde . ${\ Displaystyle N = O (\ lg n)}$${\ Displaystyle \ lg \ lg n = o (\ lg n)}$

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 :

${\ Displaystyle \ lim _ {x \ rightarrow \ infty} {\ frac {\ pi (x)} {x / \ ln (x)}} = 1.}$

Usando la notación asintótica, este resultado se puede reformular como

${\ Displaystyle \ pi (x) \ sim {\ frac {x} {\ log x}}.}$

Esto produce el teorema de Euclides, ya que ${\ Displaystyle \ lim _ {x \ rightarrow \ infty} {\ frac {x} {\ log x}} = \ infty.}$

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 ${\ Displaystyle n> 1}$

${\ Displaystyle n <p <2n.}$

El teorema de Bertrand-Chebyshev también se puede establecer como una relación con , donde es la función de conteo de primos (número de primos menor o igual que ): ${\ Displaystyle \ pi (x)}$${\ Displaystyle \ pi (x)}$${\ Displaystyle x \,}$

${\ Displaystyle \ pi (x) - \ pi ({\ tfrac {x} {2}}) \ geq 1,}$ para todos ${\ Displaystyle x \ geq 2.}$

Esta afirmación fue conjeturada por primera vez en 1845 por Joseph Bertrand (1822-1900). El mismo Bertrand verificó su declaración para todos los números en el intervalo [2, 3 × 10 ⁶ ]. Su conjetura fue completamente probado por Chebyshev (1821-1894) en 1852 y así el postulado es también llamado el teorema de Bertrand-Chebyshev o el teorema de Chebyshev .

notas y referencias

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)