Teorema lui Euclid

Teorema lui Euclid este un element fundamental al teoriei numerelor . Afirmă că pentru orice listă finită de numere prime, există un prim care nu este inclus în această listă (adică există infinit de numere prime ).

Există mai multe dovezi cunoscute ale acestei teoreme .

Dovada lui Euclid

Cea mai veche dovadă cunoscută a acestui fapt a fost dată de Euclid în Elementele (Cartea a IX-a, Propunerea 20 [1] ). În același timp, Euclid nu folosește conceptul de infinit, dar demonstrează această afirmație în următoarea formulare: există mai multe numere prime decât orice mulțime finită aleasă a acestora .

Euclid demonstrează acest lucru după cum urmează [2] .

Să presupunem că ni se oferă o listă finită de numere prime . Euclid demonstrează că există un număr prim care nu este inclus în această listă. $a,b,\dots z$

Fie cel mai mic multiplu comun al acestor numere, . $P$ $P=a*b*...*z$

Euclid consideră numărul . Dacă este prim, atunci se găsește un număr prim care nu este inclus în lista dată (deoarece este mai mare decât fiecare număr din listă). $Q=P+1$ $Q$ ${a,b,....z)$

Dacă nu este prim, atunci există un număr prim cu care numărul este divizibil egal . Dar nu poate fi atât un divizor , cât și un element al listei , pentru că atunci la împărțirea cu , ar fi un rest egal cu unu. Aceasta înseamnă că există un număr prim care nu este inclus în nicio listă (finită) de numere prime . $Q$ $X$ $Q$ $X$ $Q$ ${a,b,....z)$ $Q$ $X$ $X$ ${a,b,....z)$

Adesea, când se prezintă demonstrația teoremei lui Euclid, se începe prin a lua în considerare mulțimea TOATE numerelor prime deodată (presupunând că această mulțime conține un număr finit de elemente), iar apoi demonstrarea teoremei se realizează prin contradicție. Deși o astfel de demonstrație este și posibilă, raționamentul original al lui Euclid este mai elegant - și anume pentru orice mulțime finită de numere prime și demonstrează că trebuie să existe un număr prim care nu este inclus în acest (orice) set de numere prime [3] .

Forma scurtă a demonstrației lui Euclid:

Să ni se dea un set finit de numere prime. Să arătăm că există un număr prim care nu este inclus în această mulțime. Înmulțiți numerele din acest set și adăugați unul. Numărul rezultat nu este divizibil cu niciun număr din mulțimea dată, deoarece restul împărțirii la oricare dintre ele dă unul. Aceasta înseamnă că numărul trebuie să fie divizibil cu un număr prim care nu este inclus în acest set.

O variație a demonstrației lui Euclid folosind factorialul

Alte variații ale demonstrației lui Euclid folosesc factorialul : n ! este divizibil cu orice număr întreg de la 2 la n , deoarece este produsul lor. Prin urmare, n ! + 1 nu este divizibil cu niciun număr natural de la 2 la n inclusiv (când se împarte la oricare dintre aceste numere, restul este 1). Deci n ! + 1 este fie prim în sine, fie divizibil cu un prim mai mare decât n . În orice caz, avem pentru orice număr natural n cel puțin un număr prim mai mare decât n . De aici concluzionăm că există infinit de numere prime [4] .

Numerele euclidiene

Unele dovezi înrudite ale acestei teoreme folosesc așa-numitele numere euclidiene (secvența A006862 în OEIS ): , unde este produsul primelor prime ( primorial ). În același timp, formal vorbind, demonstrația dată de Euclid nu folosește aceste numere. După cum am menționat mai sus, Euclid arată că pentru orice mulțime finită de numere prime (nu neapărat primele prime), există un număr prim care nu este inclus în această mulțime [5] . $E_{n}=p_{n}\#+1$ $p_{n}\#$ $n$ $n$

Dovada lui Euler

O altă dovadă, oferită de Leonhard Euler , se bazează pe teorema fundamentală a aritmeticii , afirmând că orice număr întreg are o factorizare prime unică. Dacă notăm cu P mulțimea tuturor numerelor prime, putem scrie egalitățile:

\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)).

Prima egalitate se obține din formula seriei geometrice din fiecare multiplicator al produsului. A doua egalitate se obține prin interschimbarea produsului și a sumei:

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

Ca urmare, orice produs al numerelor prime apare în formulă o singură dată, iar apoi, conform teoremei fundamentale a aritmeticii, suma este egală cu suma tuturor numerelor naturale [a] .

Suma din dreapta este o serie armonică care diverge, deci și produsul din stânga trebuie să diverge, ceea ce nu este posibil dacă numărul de elemente din P este finit.

Cu ajutorul acestei demonstrații, Euler a obținut o afirmație mai puternică decât teorema lui Euclid, și anume divergența sumei reciprocelor numerelor prime .

Dovada lui Erdős

Pal Erdős a dat o a treia demonstrație, care se bazează și pe teorema fundamentală a aritmeticii. În primul rând, să acordăm atenție faptului că orice număr natural n poate fi reprezentat ca

{\displaystyle rs^{2))

unde r este fără pătrat (nu este divizibil cu niciun pătrat perfect ). Putem lua ca s 2 cel mai mare pătrat care împarte n , iar apoi r = n / s 2 . Acum să presupunem că există doar un număr finit de numere prime și notăm acel număr de prime cu k . Deoarece fiecare număr prim poate apărea o singură dată în descompunerea oricărui număr fără pătrat, conform teoremei fundamentale a aritmeticii, există doar 2k numere fără pătrat .

Acum fixăm un număr natural N și luăm în considerare numerele naturale între 1 și N . Fiecare dintre aceste numere poate fi scris ca rs 2 , unde r este un număr fără pătrat și s 2 este un pătrat:

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

Există N numere diferite în listă și fiecare dintre ele se obține prin înmulțirea unui număr fără pătrat cu un pătrat care nu depășește N . Există astfel de pătrate. Acum formăm toate produsele posibile ale tuturor pătratelor care nu depășesc N cu toate numerele fără pătrate. Există exact astfel de numere, toate sunt diferite și includ toate numerele de pe lista noastră și poate mai multe. Astfel, . Aici înseamnă toată partea . $\lfloor {\sqrt {N}}\rfloor$ $2^{k}\lfloor {\sqrt {N}}\rfloor$ $2^{k}\lfloor {\sqrt {N}}\rfloor \geqslant N$ $\lfloor {x}\rfloor$

Deoarece inegalitatea eșuează pentru N suficient de mare , trebuie să existe infinit de numere prime.

Dovada lui Furstenberg

În 1955 Hillel Furstenberg a publicat o nouă demonstrație a infinitității numărului de numere prime folosind topologia mulțimilor de puncte .

Câteva dovezi recente

Saidak

În 2006, Phillip Sajdak a dat următoarea dovadă constructivă , care nu folosește reducerea la absurd [6] sau lema lui Euclid (că dacă un număr prim p împarte ab , el trebuie să împartă fie a , fie b ).

Deoarece fiecare număr natural (> 1) are cel puțin un factor prim și două numere consecutive n și ( n + 1) nu au un divizor comun, produsul n ( n + 1) are mai mulți divizori primi diferiți decât numărul n în sine . Astfel, lanțul de numere dreptunghiulare :
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}, · · ·
oferă o succesiune de seturi de numere prime care se extind infinit.

Pinasco

În 2009, Juan Pablo Piasco a propus următoarea dovadă [7] .

Fie cele mai mici N numere prime. Apoi, conform principiului includerii-excluderii , numărul de numere întregi pozitive care nu depășesc x și divizibile cu aceste numere prime este $p_{1},\dots;p_{N)$

{\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}}

Împărțind cu x și lăsând , obținem $x\la \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)

Acesta poate fi rescris ca

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

Dacă nu există alte numere prime decât , expresia din (1) este egală și expresia (2) este egală cu 1, dar este clar că expresia (3) nu este egală cu unu. Astfel, trebuie să existe alte numere prime decât . $p_{1},\dots ,p_{N}$ $\lfloor x\rfloor$ $p_{1},\dots ,p_{N}$

Wang

În 2010 Jun Ho Peter Wang a publicat următoarea dovadă prin contradicție [8] . Fie k un număr natural. Apoi, conform formulei Legendre

k!=\prod _{p{\text{prim}}}p^{f(p,k))

(produs peste toate numerele prime)

Unde

f(p,k)=\left\lfloor {\frac {k}{p}}\right\rfloor +\left\lfloor {\frac {k}{p^{2}}}\right\ rfloor +\cdots .

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

Dar dacă există doar un număr finit de numere prime,

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

(numărătorul unei fracții crește exponențial , în timp ce conform formulei lui Stirling numitorul crește mai repede decât exponențialitatea simplă), ceea ce contrazice faptul că pentru fiecare k numărătorul este mai mare sau egal cu numitorul.

Dovada folosind iraționalitatea $\pi$

Reprezentând formula lui Leibniz $\pi$ ca produs al lui Euler dă [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

Număratorii sunt numere prime impare, iar fiecare numitor este cel mai apropiat multiplu de 4 de numărător.

Dacă ar exista un număr finit de numere prime, această formulă ar da o reprezentare rațională pentru care numitorul este produsul tuturor numerelor, ceea ce este contrar iraționalității . $\pi$ $\pi$

Dovada folosind teoria informației

Alexander Shen și colab. au dat o dovadă folosind metoda incompresibilității [10] și complexitatea Kolmogorov :

Să presupunem că există doar k numere prime ( ). Conform teoremei fundamentale a aritmeticii , orice număr natural n poate fi reprezentat ca $p_{1},\dots ,p_{k}$

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

unde numerele întregi nenegative e i împreună cu o listă de dimensiuni finite de numere prime sunt suficiente pentru a reconstrui numărul. Deoarece pentru tot i , rezultă că all (unde înseamnă logaritm la baza 2). $p_{i}\geqslant 2$ $e_{i}\leqslant \log n$ $\Buturuga$

Aceasta oferă o metodă de codificare pentru n de dimensiunea următoare (folosind notația „O mare” ):

O({\text{mărimea listei principale}}+k\log \log n)=O(\log \log n)

pic.

Aceasta este o codificare mult mai eficientă decât reprezentarea n direct în binar, care necesită biți. Rezultatul stabilit de compresie fără pierderi afirmă că nu există un algoritm pentru comprimarea fără pierderi a N biți de informații în mai puțin de N biți. Reprezentarea de mai sus încalcă această afirmație, deoarece pentru n suficient de mare . $N=O(\log n)$ $\log \log n=o(\log n)$

Astfel, există infinit de numere prime.

Distribuția asimptotică a numerelor prime

Teorema distribuției numerelor prime afirmă că numărul de numere prime mai mici decât n , notat cu , crește cu [11] . $\pi(n)$ $n/\ln(n)$

Vezi și

Comentarii

↑ Această egalitate este un caz special al formulei pentru produsul Euler pentru funcția zeta Riemann .

Note

↑ Începuturile lui Euclid, 1949-1951 , Cartea a IX-a, Propunerea 20, p. 89.
↑ James Williamson (traducător și comentator), The Elements of Euclid, With Dissertations , Clarendon Press , Oxford, 1782, pagina 63, traducerea în engleză a dovezii lui Euclid Arhivat la 23 ianuarie 2011 la Wayback Machine
↑ Hardy, Michael; Woodgold, Catherine. Prime Simplicity (engleză) // The Mathematical Intelligencer . - 2009. - Vol. 31 , nr. 4 . - P. 44-52 . - doi : 10.1007/s00283-009-9064-8 . (Engleză)
↑ Bostock, Chandler, Rourke, 2014 , p. 168.
↑ Romeo Mestrovic. Teorema lui Euclid despre infinitatea primelor: un studiu istoric al demonstrațiilor sale (300 î.Hr.--2012) și o altă nouă demonstrație // arXiv:1202.3670 [matematică]. — 16-02-2012. Arhivat din original pe 12 iunie 2018.
↑ Saidak, 2006 .
↑ Pinasco, 2009 , p. 172–173.
↑ Whang, 2010 , p. 181.
↑ Debnath, 2010 , p. 214.
↑ Vereshchagin, Uspensky, Shen, 2013 , p. 267.
↑ Diamond G. Metode elementare în studiul distribuției numerelor prime // Uspekhi Mat . - 1990. Arhivat la 7 iulie 2018.

Literatură

Începuturile lui Euclid / Traducere din greacă și comentarii de D. D. Mordukhai-Boltovsky cu participarea editorială a lui M. Ya. Vygodsky și I. N. Veselovsky. - M. - L .: GTTI, 1949-1951. - (Clasice ale științelor naturale).
Michael Hardy, Catherine Woodgold. Prime Simplicity (engleză) // The Mathematical Intelligencer . - 2009. - Vol. 31 , nr. 4 . - P. 44-52. .
The Elements of Euclid, With Disertations // Clarendon Press / James Williamson (traducere și comentariu). - Oxford, 1782. - S. 63 .
Junho Peter Whang. O altă dovadă a infinitității numerelor prime // American Mathematical Monthly . - 2010. - februarie ( vol. 117 , nr. 2 ). - S. 181 .
Philip Saidak. O nouă dovadă a teoremei lui Euclid // American Mathematical Monthly . - 2006. - Decembrie ( vol. 113 , numărul 10 ). - doi : 10.2307/27642094 .
Lokenath Debnath. Moștenirea lui Leonhard Euler: un tribut tricentenar . - World Scientific, 2010. - P. 214 . — ISBN 9781848165267 .
Nikolai Konstantinovici Vereșchagin , Vladimir Andreevici Uspensky , Alexander Shen . Complexitatea Kolmogorov și aleatorietatea algoritmică . — Editura Centrului de Educație Matematică Continuă din Moscova, 2013.
Juan Pablo Pinasco. Noi dovezi ale teoremelor lui Euclid și Euler // American Mathematical Monthly . - 2009. - Februarie ( vol. 116 , Nr. 2 ).

Link -uri

Weisstein, Eric W. Teorema lui Euclid (engleză) pe site-ul Wolfram MathWorld .
Elementele lui Euclid, Cartea a IX-a, Prop. 20 (dovada lui Euclid, pe site-ul lui David Joyce de la Universitatea Clark)
125 de dovezi ale teoremei lui Euclid