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).^[1] É a que contamos a continuación.^[2]

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 ^[3] 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. ^[4]

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. ^[5] 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.^[6]

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^[7] 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 2$ . Por exemplo, $75,600 = 2 4335271 = 21 \cdot 60 2$ .

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 1, ..., 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 2$ pode ser como máximo $N$ , polo que $s \leq \sqrt N$ . Así, como máximo poden escribirse $2 k \sqrt 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. ^[8]
Juan Pablo Pinasco escribiu unha proba baseada no principio de inclusión-exclusión.^[9]
No 2010, Junho Peter Whang publicou unha proba por contradición baseada na fórmula de Legendre.^[10]
Filip Saidak deu unha proba por construción, que non usa redución ao absurdo ^[11] 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^[12] (1822–1900). A súa conxectura foi completamente probada por Chebyshev (1821–1894) en 1852 ^[13], polo que o postulado tamén se chama teorema de Bertrand-Chebyshev ou teorema de Chebyshev.

Notas

↑ James Williamson (translator and commentator), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, page 63.
↑ Ore, Oystein (1988). Number Theory and its History. Dover. p. 65.
↑ ver Divisor.
↑ Bostock, Linda; Chandler, Suzanne; Rourke, C. (2014-11-01). Further Pure Mathematics. Nelson Thornes. p. 168. ISBN 9780859501033.
↑ Theorems 7 and their Corollaries 1 and 2 in: Leonhard Euler. Variae observationes circa series infinitas. Commentarii Academiae scientiarum imperialis Petropolitanae 9, 1744, pp. 160–188. . (Original) . (English translation version)
↑ In his History of the Theory of Numbers (Vol. 1, p. 413) Dickson refers to this proof, as well as to another one by citing page 235 of another work by Euler: Introductio in Analysin Infinitorum. Tomus Primus. Bousquet, Lausanne 1748. . There (§ 279) Euler in fact essentially restates the much stronger Theorem 19 (described below) in the paper of his former proof.
↑ Havil, Julian (2003). Gamma: Exploring Euler's Constant. Princeton University Press. pp. 28–29. ISBN 0-691-09983-9.
↑ Furstenberg, Harry (1955). On the infinitude of primes. American Mathematical Monthly 62. p. 353. JSTOR 2307043. MR 0068566. doi:10.2307/2307043.
↑ Juan Pablo Pinasco, "New Proofs of Euclid's and Euler's theorems", American Mathematical Monthly, volume 116, number 2, February, 2009, pages 172–173.
↑ Junho Peter Whang, "Another Proof of the Infinitude of the Prime Numbers", American Mathematical Monthly, volume 117, number 2, February 2010, page 181.
↑ Saidak, Filip (December 2006). "A New Proof of Euclid's Theorem". American Mathematical Monthly 113 (10): 937–938. JSTOR 27642094. doi:10.2307/27642094.
↑ 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 18. pp. 123–140. .
↑ Tchebychev, P. (1852). Mémoire sur les nombres premiers. (PDF). Journal de mathématiques pures et appliquées. Série 1 (en francés). pp. 366–390. . (Proba do postulado: 371–382). Ver taméns Mémoires de l'Académie Impériale des Sciences de St. Pétersbourg, vol. 7, pp. 15–33, 1854

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)

[1] James Williamson (translator and commentator), The Elements of Euclid, With Dissertations, Clarendon Press, Oxford, 1782, page 63.

[2] Ore, Oystein (1988). Number Theory and its History. Dover. p. 65.

[3] ver Divisor.

[4] Bostock, Linda; Chandler, Suzanne; Rourke, C. (2014-11-01). Further Pure Mathematics. Nelson Thornes. p. 168. ISBN 9780859501033.

[5] Theorems 7 and their Corollaries 1 and 2 in: Leonhard Euler. Variae observationes circa series infinitas. Commentarii Academiae scientiarum imperialis Petropolitanae 9, 1744, pp. 160–188. . (Original) . (English translation version)

[6] In his History of the Theory of Numbers (Vol. 1, p. 413) Dickson refers to this proof, as well as to another one by citing page 235 of another work by Euler: Introductio in Analysin Infinitorum. Tomus Primus. Bousquet, Lausanne 1748. . There (§ 279) Euler in fact essentially restates the much stronger Theorem 19 (described below) in the paper of his former proof.

[Havil-7] Havil, Julian (2003). Gamma: Exploring Euler's Constant. Princeton University Press. pp. 28–29. ISBN 0-691-09983-9.

[8] Furstenberg, Harry (1955). On the infinitude of primes. American Mathematical Monthly 62. p. 353. JSTOR 2307043. MR 0068566. doi:10.2307/2307043.

[9] Juan Pablo Pinasco, "New Proofs of Euclid's and Euler's theorems", American Mathematical Monthly, volume 116, number 2, February, 2009, pages 172–173.

[10] Junho Peter Whang, "Another Proof of the Infinitude of the Prime Numbers", American Mathematical Monthly, volume 117, number 2, February 2010, page 181.

[11] Saidak, Filip (December 2006). "A New Proof of Euclid's Theorem". American Mathematical Monthly 113 (10): 937–938. JSTOR 27642094. doi:10.2307/27642094.

[12] 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 18. pp. 123–140. .

[13] Tchebychev, P. (1852). Mémoire sur les nombres premiers. (PDF). Journal de mathématiques pures et appliquées. Série 1 (en francés). pp. 366–390. . (Proba do postulado: 371–382). Ver taméns Mémoires de l'Académie Impériale des Sciences de St. Pétersbourg, vol. 7, pp. 15–33, 1854

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]