Teorema de Euclides

O **teorema de Euclides** é un teorema fundamental na teoría de números que afirma que hai infinitos números primos. Foi probado por primeira vez por Euclides na súa obra *Elementos*. Hai varias demostracións do teorema.

## Proba de Euclides 
Euclides ofreceu unha proba publicada na súa obra *Elementos* (Libro IX, Proposición 20). É a que contamos a continuación.

Considere calquera lista finita de números primos *p*1 , *p*2, ... , *p**n*. Imos mostrar que existe polo menos un número primo adicional que non figura nesta lista. Sexa *P* o produto de todos os números primos da lista: *P* = *p*1*p*2 ... *p**n*. Sexa *q* = *P* + 1. Entón *q* pode ser primo ou non:

* Se *q* é primo, é un primo máis que non está na lista.
* Se *q* non é primo, entón algún factor primo *p* divide *q*. Se este factor *p* estivese na nosa lista, entón dividiría *P* (xa que *P* é o produto de todos os números da lista); pero *p* tamén divide *a P* + 1 = *q*, como acabamos de dicir. Se *p* divide *a P* e tamén *a q,* entón *p* tamén debe dividir a diferenza  dos dous números, que é (*P* + 1) − *P* = 1. Como ningún número primo divide a 1, *p* non pode estar na lista. Isto significa que hai polo menos un número primo máis que non é dos da lista.

### Variación co factorial 
O factorial *n* dun número enteiro positivo *n* é divisible por cada número enteiro de 2 a *n*, xa que é o produto de todos eles. Polo tanto,  non é divisible por ningún dos enteiros de 2 a *n*, inclusive (dá un resto de 1 cando se divide entre cada un). De aí que   é primo ou divisible por un primo maior que&nbsp;*n*. En ambos os dous casos, para cada enteiro positivo *n*, hai polo menos un primo maior que&nbsp;*n*. 

## Proba de Euler 
Outra proba, do matemático suízo Leonhard Euler, baséase no teorema fundamental da aritmética: cada número enteiro ten unha factorización prima única.  Euler deduciu que 

: \prod_{p\in P_k} \frac{1}{1-\frac{1}{p}}=\sum_{n\in N_k}\frac{1}{n},

onde P_k denota o conxunto dos  primeiros números primos, e N_k é o conxunto dos enteiros positivos cuxos factores primos están todos en P_k.

Esta fórmula pode verse como un produto dunha serie xeométrica e aplicamos a distributiva do produto sobre a suma:

: 
\begin{align}
\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{align}

No seu primeiro corolario a este resultado Euler escribe que a suma infinita no enunciado é igual ao «valor» \log\infty, ao que o produto infinito tamén é igual (na terminoloxía moderna isto equivale a dicir que a suma parcial ata x da serie harmónica diverxe asintóticamente como \log x). Despois, no seu segundo corolario, Euler sinala que o produto

: \prod_{n\ge2} \frac{1}{1-\frac{1}{n^2}}

converxe ao valor finito 2 e, en consecuencia, hai máis números primos que cadrados o que demostra o teorema de Euclides.
[miniatura|100x100px| Símbolo usado por [Leonhard Euler|Euler para denotar o infinito]]

No mesmo artigo (Teorema 19) Euler utilizou de feito a igualdade anterior para demostrar un teorema moito máis forte que era descoñecido anteriormente, a saber, que a serie

: \sum_{p\in P}\frac 1p

é diverxente, onde  denota o conxunto de todos os números primos.

## Proba de Erdős 
Paul Erdős deu unha demostración que tamén se basea no teorema fundamental da aritmética. Todo número enteiro positivo ten unha factorización única nun número libre de cadrados  e un número cadrado . Por exemplo, .

Sexa  un número enteiro positivo, e  o número de primos menores ou iguais a . Chame a eses números primos  . Calquera número enteiro positivo  que sexa menor ou igual a  pódese escribir na forma

: a = \left( p_1^{e_1} p_2^{e_2} \cdots p_k^{e_k} \right) s^2,

onde cada  é  ou . Hai  formas de formar a parte sen cadrados . E  pode ser como máximo , polo que . Así, como máximo poden escribirse  números desta forma. Noutras palabras,

: N \leq 2^k \sqrt{N}.

Ou, despexando  e tomando logaritmos en base 2, temos k \ge \frac{1}{2} \log_{2}{N}, e por tanto como  pode ser arbitrariamente grande tamén ''* (número de primos) tamén o é.

## Outras probas 
* Na década de 1950, Hillel Furstenberg introduciu unha demostración por contradición usando topoloxía de conxunto de puntos. 
* Juan Pablo Pinasco escribiu unha proba baseada no principio de inclusión-exclusión.
* No 2010, Junho Peter Whang publicou unha  proba por contradición baseada na fórmula de Legendre. 
* Filip Saidak deu unha proba por construción, que non usa redución ao absurdo  nin o lema de Euclides (que se un primo *p* divide *ab* entón debe dividir *a* ou *b*).

## Resultados máis fortes 
Os teoremas desta sección implican simultaneamente o teorema de Euclides e outros resultados a maiores.

### Teorema de Dirichlet sobre progresións aritméticas 
O teorema de Dirichlet afirma que para dous enteiros primos positivos calquera *a* e&nbsp;*d*, hai infinitos números primos da forma *a*&nbsp;+&nbsp;*nd*, onde *n* tamén é un número enteiro positivo. Noutras palabras, hai infinitos números primos que son congruentes módulo *d.*

### Teorema dos números primos 
Sexa  a función de contaxe de números primos que dá o número de primos menores ou iguais a , para calquera número real&nbsp;. Daquela o teorema dos números primos indicaque  é unha boa aproximación a , no sentido de que o límite do *cociente'' das dúas funcións  e  é 1 a medida que  vai para o infinito:

: \pi(x)\sim \frac{x}{\log x}.

Isto dá o teorema de Euclides, xa que \lim_{x\rightarrow\infty} \frac{x}{\log x}=\infty. 

### Teorema de Bertrand-Chebyshev 
En teoría de números, o postulado de Bertrand é un teorema que indica que para calquera número enteiro n > 1, sempre existe polo menos un número primo tal que

: n 

Esta afirmación foi conxecturada por primeira vez en 1845 por Joseph Bertrand (1822–1900). A súa conxectura foi completamente probada por Chebyshev (1821–1894) en 1852 , polo que o postulado tamén se chama **teorema de Bertrand-Chebyshev** ou **teorema de Chebyshev**.

## Notas 
## Véxase tamén 
### Outros artigos 
* Lema de Euclides.
### Ligazóns externas 
* 
* Euclid's Elements, Book IX, Prop. 20 (Euclid's proof, on David Joyce's website at Clark University)