teorema de euclid

Hay infinitos números primos.

El teorema de Euclides es una afirmación fundamental en la teoría de números que afirma que hay infinitos números primos . Euclides lo demostró por primera vez en su obra Elementos . Hay varias demostraciones del teorema.

La 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 ₁ ,  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, es decir, el propio q .
• 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 cada número 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 simplemente 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 demuestra que por 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 sólo tres primos y, utilizando el método general descrito anteriormente, demuestra que siempre puede encontrar un primo adicional. Es de suponer que Euclides supone 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 demostró este resultado por contradicción comenzando con el supuesto 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 'Supongamos q ₁ , ... q _n son todos los números primos". Sin embargo, dado que esta suposición ni siquiera se utiliza 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 número entero desde 2 hasta n , ya que es el producto de todos ellos. Por tanto, n ! + 1 no es divisible por ninguno de los números enteros del 2 al n , inclusive (da un resto de 1 cuando se divide entre cada uno). Por lo tanto norte ! + 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 números primos es infinito. ^[8]

La prueba de Euler

Otra prueba, realizada por el matemático suizo Leonhard Euler , se basa en el teorema fundamental de la aritmética : que cada número 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 conjuntos finitos de números enteros) es equivalente a la afirmación de que tenemos ^[9]

${\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 números enteros positivos cuyos factores primos están todos en ${\displaystyle P_{k}}$ ${\displaystyle N_{k}}$ ${\displaystyle P_{k}.}$

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

${\displaystyle {\begin{aligned}\prod _{p\in P_{k}}{\frac {1}{1-{\frac {1}{p}}}}&=\prod _{p\in 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}}}\right)\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{aligned}}}$

En la penúltima suma, cada producto de 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 con un símbolo similar al «infinito absoluto» y escribe que la suma infinita en el enunciado es igual al «valor» , al cual el producto infinito también es igual (en la terminología moderna esto es equivalente decir que la suma parcial hasta 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. ^[10]

Símbolo utilizado por Euler para indicar el infinito.

En el mismo artículo (Teorema 19), Euler de hecho usó la igualdad anterior para demostrar un teorema mucho más sólido que era desconocido antes de é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 , lo 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 ^[11] 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 r y un número cuadrado s ² . Por ejemplo, 75,600 = 2 ⁴ 3 ³ 5 ² 7 ¹ = 21 ⋅ 60 ² .

Sea N un número entero positivo y sea k el número de primos menores o iguales que N. Llame a esos primos p ₁ , ... , p _k . Cualquier número entero positivo a que sea menor o igual que N se puede escribir en la forma

${\displaystyle a=\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 ser como máximo N , entonces s ≤ √ N . Por tanto, como máximo se pueden escribir 2 ^k √ N números de esta forma. En otras palabras,

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

O, reordenando, k , el número de primos menores o iguales a N , es mayor o igual a1/2iniciar sesión ₂ norte . Como N era arbitrario, k puede ser tan grande como se desee eligiendo N apropiadamente.

La prueba de Furstenberg

En la década de 1950, Hillel Furstenberg introdujo una prueba por contradicción utilizando una topología de conjuntos de puntos . ^[12]

Defina una topología de los números enteros Z , llamada topología de enteros uniformemente espaciados , declarando que un subconjunto U  ⊆  Z es un conjunto abierto si y sólo 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 números 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 puede ser cerrado porque su complemento es finito, pero sí cerrado porque es una unión finita de conjuntos cerrados.

Pruebas recientes

Prueba utilizando el principio de inclusión-exclusión

Juan Pablo Pinasco ha escrito la siguiente prueba. ^[13]

Sean p ₁ , ...,  p _N los N primos más pequeños. Entonces, según el principio de inclusión-exclusión , el número de números enteros positivos menores o iguales a x que son divisibles por uno de esos primos es

${\displaystyle {\begin{aligned}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{aligned}}}$

Dividiendo por x y dejando x  → ∞ se obtiene

${\displaystyle \sum _{i}{\frac {1}{p_{i}}}-\sum _{i<j}{\frac {1}{p_{i}p_{j}}}+\sum _{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 además 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, debe haber más números primos que   p ₁ , ...,  p _N . ${\displaystyle \lfloor x\rfloor }$

Prueba usando la fórmula de Legendre

En 2010, Junho Peter Whang publicó la siguiente prueba por contradicción. ^[14] Sea k cualquier número entero positivo. Luego según la fórmula de Legendre (a veces atribuida a de Polignac )

${\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 sólo existen un número finito de números primos, entonces

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

(el numerador de la fracción crecería individualmente exponencialmente mientras que según la aproximación de Stirling el denominador crece más rápidamente que individualmente exponencialmente), 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 utiliza la reductio ad absurdum ^[15] o el lema de Euclides (que si un primo p divide a ab entonces debe dividir a o  b ).

Dado que cada número natural mayor que 1 tiene al menos un factor primo , 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 factores primos diferentes que el propio número n . 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 mediante el método de incompresibilidad.

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

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

e _iiinnotación O grande ${\displaystyle p_{i}\geq 2}$ ${\displaystyle e_{i}\leq \lg n}$ ${\displaystyle \lg }$

${\displaystyle O({\text{prime list size}}+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 requiere bits. Un resultado establecido en la compresión de datos sin pérdidas establece que generalmente 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 . Por tanto, el número de números primos no debe ser finito. ^[dieciséis] ${\displaystyle N=O(\lg n)}$ ${\displaystyle \lg \lg n=o(\lg n)}$

Resultados más sólidos

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 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 a x , para cualquier número real  x . El teorema de los números primos establece entonces que x /log x es una buena aproximación a π ( x ) , en el sentido de que el límite del cociente de las dos funciones π ( x ) y x /log x a medida que x aumenta sin límite es 1 :

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

Usando 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 expresar como una relación con , donde está 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 ^[17] (1822-1900). El propio Bertrand verificó su afirmación para todos los números en el intervalo [2, 3 × 10 ⁶ ]. Su conjetura fue completamente demostrada por Chebyshev (1821-1894) en 1852 ^[18] , por lo que el postulado también se denomina teorema de Bertrand-Chebyshev o teorema de Chebyshev .

notas y referencias

1. James Williamson (traductor y comentarista), Los elementos de Euclides, con disertaciones , Clarendon Press , Oxford, 1782, página 63.
2. Ore, Oystein (1988) [1948], La teoría de números y su historia , Dover, p. sesenta y cinco
3. En general, para cualquier número entero a , b , c si y , entonces . Para obtener más información, consulte Divisibilidad . ${\displaystyle a\mid b}$ ${\displaystyle a\mid c}$ ${\displaystyle a\mid (b-c)}$
4. La formulación exacta de la afirmación de Euclides es: "Los números primos son más numerosos que cualquier multitud de números primos propuesta".
5. Katz, Victor J. (1998), Una historia de las matemáticas/una introducción (2ª ed.), Addison Wesley Longman, p. 87
6. Michael Hardy y Catherine Woodgold, "Prime Simplicity", Mathematical Intelligencer , volumen 31, número 4, otoño de 2009, páginas 44–52.
7. Franzén, Torkel (2004), Inagotabilidad: un tratamiento no exhaustivo , AK Peters, Ltd, p. 101
8. Bostock, Linda; Chandler, Susana; Rourke, C. (1 de noviembre de 2014). Más matemáticas puras . Nelson Thornes. pag. 168.ISBN​ 9780859501033.
9. Teoremas 7 y sus Corolarios 1 y 2 en: Leonhard Euler. Varias observaciones alrededor de series infinitas. Commentarii academiae scientiarum Petropolitanae 9, 1744, págs. 160–188. [1]. (Original) [2]. (Versión traducida al inglés)
10. En su Historia de la teoría de los números (Vol. 1, p. 413) Dickson se refiere a esta prueba, así como a otra, citando la página 235 de otra obra de Euler: Introductio in Analysin Infinitorum. Tomus Primus. Bousquet, Lausana 1748. [3]. Allí (§ 279), Euler, de hecho, esencialmente reafirma el Teorema 19, mucho más sólido (descrito más adelante) en el artículo de su prueba anterior.
11. Havil, Julián (2003). Gamma: explorando la constante de Euler . Prensa de la Universidad de Princeton. págs. 28 y 29. ISBN 0-691-09983-9.
12. Furstenberg, Harry (1955). "Sobre la infinidad de números primos". Mensual Matemático Estadounidense . 62 (5): 353. doi : 10.2307/2307043. JSTOR  2307043. SEÑOR  0068566.
13. 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.
14. Junho Peter Whang, "Otra prueba de la infinidad de los números primos", American Mathematical Monthly , volumen 117, número 2, febrero de 2010, página 181.
15. Saidak, Filip (diciembre de 2006). "Una nueva prueba del teorema de Euclides". Mensual Matemático Estadounidense . 113 (10): 937–938. doi :10.2307/27642094. JSTOR  27642094.
16. Shen, Alexander (2016), Complejidad de Kolmogorov y aleatoriedad algorítmica (PDF) , AMS, p. 245
17. 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.
18. 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 a 33, 1854

enlaces externos

• Weisstein, Eric W. "Teorema de Euclides". MundoMatemático .
• Elementos de Euclides, Libro IX, Prop. 20 (prueba de Euclides, en el sitio web de David Joyce en la Universidad Clark)