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₁ , p₂, ... , 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₁p₂ ... 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, n! + 1 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 n! + 1 é primo ou divisible por un primo maior que n. En ambos os dous casos, para cada enteiro positivo n, hai polo menos un primo maior que 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 k 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{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}}$

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\geq 2}{\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.

Símbolo usado por 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 {1}{p}}$

é diverxente, onde P 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 r e un número cadrado s². Por exemplo, 75,600 = 2⁴ 3³ 5² 7¹ = 21 ⋅ 60².

Sexa N un número enteiro positivo, e k o número de primos menores ou iguais a N. Chame a eses números primos p₁, ..., p_k . Calquera número enteiro positivo a que sexa menor ou igual a N 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 e_i é 0 ou 1. Hai 2^k formas de formar a parte sen cadrados a. E s² pode ser como máximo N, polo que s ≤ √N. Así, como máximo poden escribirse 2^k √N números desta forma. Noutras palabras,

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

Ou, despexando k e tomando logaritmos en base 2, temos $k\geq {\frac {1}{2}}\log _{2}{N}$, e por tanto como N pode ser arbitrariamente grande tamén k (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 d, hai infinitos números primos da forma a + 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

Artigo principal: Teorema_do_número_primo.

Sexa π(x) a función de contaxe de números primos que dá o número de primos menores ou iguais a x, para calquera número real x. Daquela o teorema dos números primos indicaque x / log x é unha boa aproximación a π(x), no sentido de que o límite do cociente das dúas funcións π(x) e x / log x é 1 a medida que x 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<p<2n.$

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.

Véxase tamén

Outros artigos

• Lema de Euclides.

Ligazóns externas

• Weisstein, Eric W. "Euclid's Theorem". MathWorld. 
• Euclid's Elements, Book IX, Prop. 20 (Euclid's proof, on David Joyce's website at Clark University)