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 .
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ă.
Fie cel mai mic multiplu comun al acestor numere, .
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ă).
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 .
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.
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] .
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] .
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:
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:
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 .
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
,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 .
Deoarece inegalitatea eșuează pentru N suficient de mare , trebuie să existe infinit de numere prime.
În 1955 Hillel Furstenberg a publicat o nouă demonstrație a infinitității numărului de numere prime folosind topologia mulțimilor de puncte .
Î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.
Î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
Împărțind cu x și lăsând , obținem
Acesta poate fi rescris ca
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 .
Î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
(produs peste toate numerele prime)Unde
Dar dacă există doar un număr finit de numere prime,
(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.
Reprezentând formula lui Leibniz ca produs al lui Euler dă [9] .
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 .
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
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).
Aceasta oferă o metodă de codificare pentru n de dimensiunea următoare (folosind notația „O mare” ):
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 .
Astfel, există infinit de numere prime.
Teorema distribuției numerelor prime afirmă că numărul de numere prime mai mici decât n , notat cu , crește cu [11] .