Teorema de euclides

El teorema de Euclides es un elemento fundamental de la teoría de números . Establece que para cualquier lista finita de primos , hay un primo que no está incluido en esta lista (es decir, hay infinitos primos ).

Hay varias demostraciones conocidas de este teorema .

Prueba de Euclides

La prueba más antigua conocida de este hecho la dio Euclides en los Elementos (Libro IX, Proposición 20 [1] ). Al mismo tiempo, Euclides no usa el concepto de infinito, pero prueba esta afirmación en la siguiente formulación: hay más números primos que cualquier conjunto finito elegido de ellos .

Euclides prueba esto de la siguiente manera [2] .

Supongamos que nos dan una lista finita de números primos . Euclides demuestra que hay un número primo que no está incluido en esta lista. ${\ estilo de visualización a, b, \ puntos z}$

Sea el mínimo común múltiplo de estos números, . $PAGS$ $P=a*b*...*z$

Euclides considera el número . Si es primo, entonces se encuentra un número primo que no está incluido en la lista dada (porque es mayor que cada número de la lista). ${\ estilo de visualización Q = P + 1}$ $q$ ${\ estilo de visualización {a, b, .... z}}$

Si no es primo, entonces hay algún número primo por el cual el número es divisible por igual . Pero no puede ser a la vez divisor y elemento de la lista , porque entonces al dividir por , quedaría un resto igual a uno. Esto significa que existe un número primo que no está incluido en ninguna lista (finita) de números primos . $q$ $X$ $q$ $X$ $q$ ${\ estilo de visualización {a, b, .... z}}$ $q$ $X$ $X$ ${\ estilo de visualización {a, b, .... z}}$

A menudo, cuando se presenta la demostración del teorema de Euclides, se comienza considerando el conjunto de TODOS los números primos a la vez (asumiendo que este conjunto contiene un número finito de elementos), y luego se realiza la demostración del teorema por contradicción. Aunque tal prueba también es posible, el razonamiento original de Euclides es más elegante, es decir, para cualquier conjunto finito de primos, y prueba que debe haber algún número primo que no está incluido en este (cualquier) conjunto de primos [3] .

Forma abreviada de la prueba de Euclides:

Tengamos un conjunto finito de números primos. Demostremos que existe un número primo no incluido en este conjunto. Multiplica los números de este conjunto y suma uno. El número resultante no es divisible por ningún número del conjunto dado, porque el resto de dividir por cualquiera de ellos da uno. Esto significa que el número debe ser divisible por algún número primo no incluido en este conjunto.

Una variación de la prueba de Euclides usando el factorial

Otras variaciones de la prueba de Euclides usan el factorial : n ! es divisible por cualquier número entero de 2 an , ya que es su producto. Por lo tanto, n ! + 1 no es divisible por ningún número natural del 2 al n inclusive (al dividir por cualquiera de estos números, el resto es 1). ¡Así que no ! + 1 es primo en sí mismo o divisible por un primo mayor que n . En cualquier caso, tenemos para cualquier número natural n al menos un número primo mayor que n . Por lo tanto, concluimos que hay infinitos números primos [4] .

Números euclidianos

Algunas demostraciones relacionadas de este teorema utilizan los llamados números euclidianos (secuencia A006862 en OEIS ): , donde es el producto de los primeros primos ( primoriales ). Al mismo tiempo, formalmente hablando, la demostración dada por Euclides no usa estos números. Como se mencionó anteriormente, Euclides muestra que para cualquier conjunto finito de primos (no necesariamente los primeros primos), hay un número primo que no está incluido en este conjunto [5] . $E_{n}=p_{n}\#+1$ $p_{n}\#$ $norte$ $norte$

Prueba de Euler

Otra prueba, ofrecida por Leonhard Euler , se basa en el teorema fundamental de la aritmética , que establece que cualquier número entero tiene una descomposición en factores primos única. Si denotamos por P el conjunto de todos los números primos, podemos escribir las igualdades:

\prod_{p\in P}{\frac {1}{1-1/p}}=\prod_{p\in P}\sum_{k\geqslant 0}{\frac {1 {p^{k))}=\sum_{n}{\frac {1}{n)).

La primera igualdad se obtiene de la fórmula de la serie geométrica en cada multiplicador del producto. La segunda igualdad se obtiene intercambiando el producto y la suma:

{\begin{alineado}\prod_{p\in P}\sum_{k\geqslant 0}{\frac {1}{p^{k))}&=\sum_{k\geqslant 0}{\frac {1}{2^{k))}\cdot \sum_{k\geqslant 0}{\frac {1}{3^{k))}\cdot \sum_{k\geqslant 0}{\frac {1}{5^{k}}}\cdot \sum _{k\geqslant 0}{\frac {1}{7^{k}}}\cdots \\[8pt]&= \sum _{k,\ell ,m,n,\cdots \geqslant 0}{\frac {1}{2^{k}3^{\ell }5^{m}7^{n}\cdots } }=\sum _{n}{\frac {1}{n}}\end{alineado}}

Como resultado, cualquier producto de números primos aparece en la fórmula solo una vez y luego, de acuerdo con el teorema fundamental de la aritmética, la suma es igual a la suma de todos los números naturales [a] .

La suma de la derecha es una serie armónica que diverge, por lo que el producto de la izquierda también debe divergir, lo cual no es posible si el número de elementos en P es finito.

Con la ayuda de esta demostración, Euler obtuvo un enunciado más sólido que el teorema de Euclides, a saber, la divergencia de la suma de los recíprocos de los números primos .

Prueba de Erdős

Pal Erdős dio una tercera prueba, que también se basa en el teorema fundamental de la aritmética. Primero, prestemos atención al hecho de que cualquier número natural n puede representarse como

{\displaystyle rs^{2))

donde r no tiene cuadrados (no es divisible por ningún cuadrado perfecto ). Podemos tomar como s 2 el cuadrado mayor que divide a n , y entonces r = n / s 2 . Ahora suponga que solo hay un número finito de números primos y denote ese número de números primos con k . Dado que cada número primo solo puede aparecer una vez en la descomposición de cualquier número sin cuadrados, de acuerdo con el teorema fundamental de la aritmética, solo hay 2k números sin cuadrados .

Ahora fijamos algún número natural N y consideramos números naturales entre 1 y N. Cada uno de estos números se puede escribir como rs 2 , donde r es un número sin cuadrados y s 2 es un cuadrado:

( 1 1, 2 1, 3 1, 1 4, 5 1, 6 1, 7 1, 2 4, 1 9, 10 1, ...)

Hay N números diferentes en la lista , y cada uno de ellos se obtiene multiplicando un número libre de cuadrados por un cuadrado que no exceda de N. Hay tales cuadrados. Ahora formamos todos los productos posibles de todos los cuadrados que no excedan N por todos los números libres de cuadrados. Existen exactamente esos números, todos son diferentes e incluyen todos los números de nuestra lista, y tal vez más. Así, . Aquí significa la parte entera . $\lpiso {\sqrt {N}}\rpiso$ $2^{k}\lpiso {\sqrt {N}}\rpiso$ $2^{k}\lpiso {\sqrt {N}}\rpiso \geqslant N$ $\lpiso {x}\rpiso$

Dado que la desigualdad falla para N suficientemente grande , debe haber un número infinito de números primos.

Prueba de Furstenberg

En 1955 , Hillel Furstenberg publicó una nueva prueba de la infinidad del número de números primos usando la topología de conjuntos de puntos .

Algunas pruebas recientes

Saidak

En 2006, Phillip Sajdak dio la siguiente prueba constructiva , que no usa la reducción al absurdo [6] o el lema de Euclides (que si un número primo p divide ab , debe dividir a a o b ).

Como todo número natural (> 1) tiene al menos un factor primo, y dos números consecutivos n y ( n + 1) no tienen un divisor común, el producto n ( n + 1) tiene más divisores primos diferentes que el número n mismo Así, la cadena de números rectangulares :
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}, · · ·
da una secuencia de conjuntos de números primos que se expanden infinitamente.

Pinasco

En 2009, Juan Pablo Piasco propuso la siguiente prueba [7] .

Sean los N números primos más pequeños. Entonces, de acuerdo con el principio de inclusión-exclusión , el número de números enteros positivos que no excedan x y que sean divisibles por estos primos es ${\displaystyle p_{1},\puntos ;p_{N))$

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

Dividiendo por x y dejando , obtenemos $x\a\infty$

\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 reescribir como

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

Si no hay otros números primos además de , la expresión en (1) es igual y la expresión (2) es igual a 1, pero está claro que la expresión (3) no es igual a uno. Por lo tanto, debe haber números primos distintos de . $p_{1},\puntos,p_{N}$ $\lpiso x\rpiso$ $p_{1},\puntos,p_{N}$

Wang

En 2010, Jun Ho Peter Wang publicó la siguiente prueba por contradicción [8] . Sea k un número natural. Entonces, según la fórmula de Legendre

{\displaystyle k!=\prod_{p{\text{principal}}}p^{f(p,k)))

(producto de todos los números primos)

dónde

f(p,k)=\left\lpiso {\frac {k}{p}}\right\rpiso +\left\lpiso {\frac {k}{p^{2}}}\right\ rpiso +\cpuntos .

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

Pero si solo hay un número finito de números primos,

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

(el numerador de una fracción crece exponencialmente , mientras que según la fórmula de Stirling el denominador crece más rápido que la simple exponencial), lo que contradice el hecho de que para cada k el numerador es mayor o igual que el denominador.

Prueba usando irracionalidad $\Pi$

Representando la fórmula de Leibniz para $\Pi$ como un producto de Euler da [9] .

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

Los numeradores son números primos impares, y cada denominador es el múltiplo de 4 más cercano al numerador.

Si hubiera un número finito de primos, esta fórmula daría una representación racional en la que el denominador es el producto de todos los números, lo que es contrario a la irracionalidad . $\Pi$ $\Pi$

Demostración utilizando la teoría de la información

Alexander Shen y otros dieron una prueba usando el método de incompresibilidad [10] y la complejidad de Kolmogorov :

Supongamos que solo hay k primos ( ). Según el teorema fundamental de la aritmética , cualquier número natural n se puede representar como $p_{1},\puntos,p_{k}$

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

donde los enteros no negativos e i junto con una lista de números primos de tamaño finito son suficientes para reconstruir el número. Ya que para todo i , se sigue que todo (donde significa logaritmo en base 2). ${\ Displaystyle p_ {i} \ geqslant 2}$ $e_{i}\leqslant\log n$ $\Iniciar sesión$

Esto proporciona un método de codificación para n del siguiente tamaño (usando la notación "O grande" ):

O({\text{tamaño de lista principal}}+k\log \log n)=O(\log \log n)

un poco.

Esta es una codificación mucho más eficiente que representar n directamente en binario, lo que requiere bits. El resultado de la compresión sin pérdidas establecido establece que no existe ningún algoritmo para comprimir sin pérdidas N bits de información en menos de N bits. La representación anterior viola esta declaración, porque para n suficientemente grande . $N=O(\log n)$ ${\ estilo de visualización \ log \ log n = o (\ log n)}$

Por lo tanto, hay infinitos números primos.

Distribución asintótica de números primos

El teorema de distribución de números primos establece que el número de números primos menores que n , denotados por , crece a medida que [11] . $\alfiler)$ $n/\ln(n)$

Véase también

Comentarios

↑ Esta igualdad es un caso especial de la fórmula del producto de Euler por la función zeta de Riemann .

Notas

↑ Los comienzos de Euclides, 1949-1951 , Libro IX, Proposición 20, p. 89.
↑ James Williamson (traductor y comentarista), The Elements of Euclid, With Dissertations , Clarendon Press , Oxford, 1782, página 63, traducción al inglés de la prueba de Euclid. Archivado el 23 de enero de 2011 en Wayback Machine .
↑ Hardy, Michael; Woodgold, Catalina. Prime Simplicity (inglés) // The Mathematical Intelligencer . - 2009. - Vol. 31 , núm. 4 . - Pág. 44-52 . -doi : 10.1007/ s00283-009-9064-8 . (Inglés)
↑ Bostock, Chandler, Rourke, 2014 , pág. 168.
↑ Romeo Mestrovic. El teorema de Euclides sobre la infinitud de los números primos: un repaso histórico de sus demostraciones (300 a. C.--2012) y otra nueva demostración // arXiv:1202.3670 [matemáticas]. — 2012-02-16. Archivado desde el original el 12 de junio de 2018.
↑ Saidak, 2006 .
↑ Pinasco, 2009 , p. 172–173.
↑ Wang, 2010 , pág. 181.
↑ Debnath, 2010 , pág. 214.
↑ Vereshchagin, Uspensky, Shen, 2013 , pág. 267.
↑ Diamond G. Métodos elementales en el estudio de la distribución de números primos // Uspekhi Mat . - 1990. Archivado el 7 de julio de 2018.

Literatura

Comienzos de Euclides / Traducción del griego y comentarios de D. D. Mordukhai-Boltovsky con participación editorial de M. Ya. Vygodsky e I. N. Veselovsky. - M. - L .: GTTI, 1949-1951. - (Clásicos de las ciencias naturales).
Michael Hardy, Catherine Woodgold. Prime Simplicity (inglés) // The Mathematical Intelligencer . - 2009. - Vol. 31 , núm. 4 . - Pág. 44-52. .
The Elements of Euclid, With Dissertations // Clarendon Press / James Williamson (traducción y comentario). - Oxford, 1782. - S. 63 .
Junho Peter Whang. Otra prueba de la infinitud de los números primos // American Mathematical Monthly . - 2010. - febrero ( vol. 117 , núm. 2 ). - S. 181 .
Felipe Saidak. Una nueva prueba del teorema de Euclides // American Mathematical Monthly . - 2006. - diciembre ( vol. 113 , número 10 ). -doi : 10.2307/ 27642094 .
Lokenath Debnath. El legado de Leonhard Euler: un tributo del tricentenario . - World Scientific, 2010. - Pág. 214 . — ISBN 9781848165267 .
Nikolai Konstantinovich Vereshchagin , Vladimir Andreevich Uspensky , Alexander Shen . Complejidad de Kolmogorov y aleatoriedad algorítmica . — Editorial del Centro de Moscú para la Educación Matemática Continua, 2013.
Juan Pablo Pinasco. Nuevas pruebas de los teoremas de Euclides y Euler // American Mathematical Monthly . - 2009. - febrero ( vol. 116 , núm. 2 ).

Enlaces

Weisstein, Eric W. Euclid's Theorem (inglés) en el sitio web de Wolfram MathWorld .
Elementos de Euclides, Libro IX, Prop. 20 (prueba de Euclides, en el sitio web de David Joyce en la Universidad de Clark)
125 demostraciones del teorema de Euclides