Teorema de Euclides

Hay infinitos números primos

El teorema de Euclides es una afirmación fundamental de la teoría de números que afirma que existen infinitos números primos . Fue demostrado por primera vez por Euclides en su obra Elementos . Existen varias demostraciones 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]

Consideremos cualquier lista finita de números primos p ₁ ,  p ₂ , ...,  p _n . Se demostrará que existe al menos un número primo adicional no incluido 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, q mismo.
• Si q no es primo, entonces algún factor primo p divide  a q . Si este factor p estuviera en nuestra lista, 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 decir. 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 que están en la lista.

Esto demuestra que para cada lista finita de números primos existe 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 primos y, utilizando el método general descrito anteriormente, demuestra que siempre puede encontrar un primo adicional. Euclides presumiblemente asume que sus lectores están convencidos de que una prueba similar funcionará, sin importar cuántos primos se elijan originalmente. ^[5]

A menudo se afirma erróneamente que Euclides demostró este resultado por contradicción partiendo de la suposición de que el conjunto finito considerado inicialmente contiene todos los números primos, ^[6] aunque en realidad se trata de 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 primos no es una prueba indirecta [...] El argumento a veces se formula como una prueba indirecta reemplazándolo por la suposición 'Supongamos que q ₁ , ... q _n son todos los primos'. Sin embargo, dado que esta suposición ni siquiera se utiliza en la prueba, la reformulación es inútil". ^[7]

Variaciones

Existen varias variaciones de la prueba de Euclides, entre las que se incluyen las siguientes:

El factorial n ! de un entero positivo n es divisible por todo entero de 2 a n , ya que es el producto de todos ellos. Por lo tanto, n ! + 1 no es divisible por ninguno de los enteros de 2 a n , ambos 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, para todo 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 número entero tiene una única factorización prima. Lo que Euler escribió (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 demostrar esto, se desarrolla cada factor del producto como una serie geométrica y se distribuye el producto sobre 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 primos aparece exactamente una vez, por lo que la última igualdad es verdadera por el teorema fundamental de la aritmética. En su primer corolario a 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 que el producto infinito es por tanto también igual (en terminología moderna esto es equivalente a 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 por consiguiente hay más primos que cuadrados. Esto demuestra el teorema de Euclides. ^[10]

Símbolo utilizado por Euler para denotar el infinito

En el mismo artículo (Teorema 19), Euler de hecho utilizó la igualdad anterior para demostrar un teorema mucho más fuerte 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 es igual a , 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}$

Prueba de Erdös

Paul Erdős dio una prueba ^[11] que también se basa en el teorema fundamental de la aritmética. Todo 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 entero positivo y sea k el número de primos menores o iguales a N. Llamemos a esos primos p ₁ , ... , p _k . Cualquier entero positivo a que sea menor o igual a N puede entonces escribirse 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 , por lo que s ≤ √ N. Por lo tanto, como máximo 2 ^k √ N números pueden escribirse en 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 a ⁠1/2⁠ log ₂ N. Dado que N es 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 la topología de conjuntos de puntos . ^[12]

Defina una topología de los números enteros , llamada topología de números enteros uniformemente espaciados , declarando que un subconjunto es un conjunto abierto si y solo si es el conjunto vacío , o es una unión de secuencias aritméticas (para ), donde ${\textstyle \mathbb {Z} }$ ${\textstyle U\subseteq \mathbb {Z} }$ ${\textstyle \emptyset }$ ${\textstyle S(a,b)}$ ${\textstyle a\neq 0}$

$${\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 la propiedad de que los conjuntos base son a la vez abiertos y cerrados , ya que ${\textstyle S(a,b)}$

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

no puede ser cerrado porque su complemento es finito, pero es cerrado porque es una unión finita de conjuntos cerrados.

Pruebas recientes

Demostración mediante 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, por el principio de inclusión-exclusión , la cantidad 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 que 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 primos que   p ₁ , ...,  p _N . ${\displaystyle \lfloor x\rfloor }$

Demostración mediante la fórmula de Legendre

En 2010, Junho Peter Whang publicó la siguiente prueba por contradicción. ^[14] Sea k cualquier entero positivo. Entonces, 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 exponencialmente mientras que por la aproximación de Stirling el denominador crece más rápidamente que 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 reductio ad absurdum ^[15] ni el lema de Euclides (que si un primo p divide a ab entonces debe dividir a o  b ).

Como 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 . Por tanto, 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 primos en crecimiento ilimitado.

Demostración mediante el método de incompresibilidad

Supongamos que sólo hubiera k primos ( p ₁ , ..., p _k ). Por el teorema fundamental de la aritmética , cualquier entero positivo n podría entonces 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 finita de primos son suficientes para reconstruir el número. Dado que para todo i , se deduce que para todo i (donde denota el logaritmo en base 2). Esto produce una codificación para n del siguiente tamaño (usando la notación O mayúscula ): 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érdida establece que, en general, no se pueden comprimir N bits de información en menos de N bits. La representación anterior viola esto con creces cuando n es lo suficientemente grande ya que . Por lo tanto, el número de primos no debe ser finito. ^[16] ${\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)}$ ${\displaystyle N=O(\lg n)}$ ${\displaystyle \lg \lg n=o(\lg n)}$

Demostración utilizando un argumento par-impar

Romeo Meštrović utilizó un argumento par-impar para demostrar que si el número de primos no es infinito, entonces 3 es el primo más grande, una contradicción. ^[17]

Supongamos que son todos los números primos. Consideremos y observemos que, por supuesto, todos los números enteros positivos que son primos entre sí están en el conjunto . En particular, es primo entre sí y, por lo tanto, es . Sin embargo, esto significa que es un número impar en el conjunto , por lo tanto , o . Esto significa que debe ser el número primo más grande, lo cual es una contradicción. ${\displaystyle p_{1}=2<p_{2}=3<p_{3}<\cdots <p_{k}}$ ${\displaystyle P=3p_{3}p_{4}\cdots p_{k}}$ ${\displaystyle S=\{1,2,2^{2},2^{3},\dots \}}$ ${\displaystyle 2}$ ${\displaystyle P}$ ${\displaystyle P-2}$ ${\displaystyle P-2}$ ${\displaystyle S}$ ${\displaystyle P-2=1}$ ${\displaystyle P=3}$ ${\displaystyle 3}$

La prueba anterior sigue funcionando si se reemplaza por cualquier primo con , el producto se convierte en y el argumento par contra impar se reemplaza por un argumento divisible contra uno no divisible por . La contradicción resultante es que debe, simultáneamente, ser igual y mayor que , ^[a] lo cual es imposible. ${\displaystyle 2}$ ${\displaystyle p_{j}}$ ${\displaystyle j\in \{1,2,\dots ,k-1\}}$ ${\displaystyle P}$ ${\displaystyle p_{1}p_{2}\cdots p_{j-1}\cdot p_{j+1}\cdots p_{k}}$ ${\displaystyle p_{j}}$ ${\displaystyle P-p_{j}}$ ${\displaystyle 1}$ ${\displaystyle 1}$

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 números enteros coprimos positivos a y  d , hay una cantidad infinita de primos de la forma a  +  nd , donde n también es un número entero positivo. En otras palabras, hay una cantidad infinita de primos que son congruentes con a 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 cuando 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 puede reformularse 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 puede enunciarse como una relación con , donde es la función de conteo de primos (número de primos menores o iguales a ): ${\displaystyle \pi (x)}$ ${\displaystyle \pi (x)}$ ${\displaystyle x\,}$

$${\displaystyle \forall x\geq 2.\pi (x)-\pi ({\tfrac {x}{2}})\geq 1}$$

Esta afirmación fue formulada por primera vez en 1845 por Joseph Bertrand ^[18] (1822-1900). El propio Bertrand verificó su afirmación para todos los números en el intervalo [2, 3 × 10 ⁶ ]. Su conjetura fue demostrada completamente por Chebyshev (1821-1894) en 1852 ^[19] y, por ello, el postulado también se denomina teorema de Bertrand-Chebyshev o teorema de Chebyshev .

Notas

1. En la prueba anterior (con ), esta contradicción se vería así: . En la prueba más general, la contradicción sería: ; es decir, reemplaza y el coeficiente de es el primo más pequeño en . ${\displaystyle j=1,p_{j}=2}$ ${\displaystyle 1=P-2>3p_{k}-2>2>1}$ ${\displaystyle 1=P-p_{j}>2p_{k}-p_{j}>p_{j}>1}$ ${\displaystyle p_{j}}$ ${\displaystyle 2}$ ${\displaystyle p_{k}}$ ${\displaystyle P}$

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], Teoría de números y su historia , Dover, pág. 65
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 propuesta de números primos".
5. Katz, Victor J. (1998), Una historia de las matemáticas/una introducción (2.ª ed.), Addison Wesley Longman, pág. 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ág. 101
8. Bostock, Linda; Chandler, Suzanne; Rourke, C. (1 de noviembre de 2014). Más matemáticas puras . Nelson Thornes. pág. 168. ISBN 9780859501033.
9. Teoremas 7 y sus Corolarios 1 y 2 en: Leonhard Euler. "Variae observaciones alrededor de series infinitas" . Commentarii Academiae scientiarum imperialis Petropolitanae 9, 1744, págs. 160–188. traducción al inglés
10. En su Historia de la teoría de los números (vol. 1, p. 413) Dickson hace referencia 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. [1]. Allí (§ 279) Euler, de hecho, esencialmente replantea el mucho más fuerte Teorema 19 (descrito más abajo) en el artículo de su prueba anterior.
11. Havil, Julian (2003). Gamma: exploración de la constante de Euler . Princeton University Press. pp. 28-29. ISBN 0-691-09983-9.
12. Furstenberg, Harry (1955). "Sobre la infinitud de los números primos". American Mathematical Monthly . 62 (5): 353. doi :10.2307/2307043. JSTOR  2307043. MR  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 infinitud 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". American Mathematical Monthly . 113 (10): 937–938. doi :10.2307/27642094. JSTOR  27642094.
16. Shen, Alexander (2016), Complejidad de Kolmogorov y aleatoriedad algorítmica (PDF) , AMS, pág. 245
17. Meštrović, Romeo (13 de diciembre de 2017). «Una prueba muy breve de la infinitud de los números primos». The American Mathematical Monthly . 124 (6): 562. doi :10.4169/amer.math.monthly.124.6.562 . Consultado el 30 de junio de 2024 .
18. 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.
19. 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". MathWorld .
• Elementos de Euclides, Libro IX, Proposición 20 (Prueba de Euclides, en el sitio web de David Joyce en la Universidad Clark)