Primaarvuteoreem on arvuteooria teoreem, mis kirjeldab, kuidas esmased arvud jaotuvad suurte arvude hulgas. Täpsemalt ütleb teoreem, et primaarvude loendfunktsioon π(x) — see on arv esmastest arvudest, mis on väiksemad või võrdsed x-ga — kasvab suurusjärgus x/ln(x). Vormiliselt kirjutatakse seda sageli kui

π(x) ~ x / ln(x), ehk teisiti: lim_{x→∞} π(x) ln(x) / x = 1.

Mis see tähenduselt tähendab

Teoreemist järeldub, et primaarvude suhteline tihedus lähedal arvule n on ligikaudu 1/ln(n). See tähendab, et tõenäosus tabada algarv juhuslikust arvust suurusjärgus n on ligikaudu 1/ln(n) — mida suurem on n, seda harvemini esinevad algarvud. Seetõttu on ka kahe järjestikuse algarvu vahe keskmiselt ligikaudu ln(N) esimest N täisarvu arvestades.

Praktiline näide: ligikaudse tõenäosuse arvutamiseks numbri ~10^1000 juures kasutatakse ln(10^1000) = 1000·ln(10) ≈ 2302,6; st tõenäosus, et juhuslik arv suurusjärgus 10^1000 on algarv, on umbes 1/2302. Sarnaselt arvude juures ~10^2000 on tõenäosus umbes 1/4605. See illustreerib, miks 2n-kohaliste arvude hulgas on ligikaudu poole vähem algarve kui n-kohaliste hulgas: ln(10^{2n}) = 2·ln(10^n).

Täpsustused ja paremad ligikaudsed avaldised

Lihtne avaldis x/ln(x) annab hea esialgse hinnangu, kuid paremini sobivad lähendused põhinevad liitfunktsioonil

li(x) = ∫_2^x dt / ln t,

mis annab tihti täpsema prognoosi sellest, mitu algarvu kuni x leidub. On ka täpsemaid asümptootilisi parandusi, mis kasutavad Riemanni zeta-funktsiooni ning selle nullide paiknemisest tulenevaid täiendavaid termineid.

Ajalugu ja tõestused

Seose olemasolu algarvude ja logaritmide vahel märkas noor Carl Friedrich Gauss juba 1793. aastal ning sarnaseid tähelepanekuid tegi ka Adrien-Marie Legendre 1798. aastal. Püsivat edasiminekut tõestuses pakkusid 19. sajandi lõpus Jacques Hadamard ja Charles-Jean de La Vallée Poussin, kes 1896. aastal iseseisvalt tõestasid primaarvuteoreemi, kasutades kompleksanalüütilisi meetodeid ja Riemanni zeta-funktsiooni omadusi — üheks oluliseks sammuks oli näidata, et ζ(s) ≠ 0 reaalse osa s = 1 läheduses.

Hiljem, 1949. aastal, leidsid Atle Selberg ja Paul Erdős „elementaarsed” tõestused, mis ei kasutanud Riemanni zeta-funktsiooni keerukaid omadusi (kuigi ka nende lähenemised kasutavad sügavat analüütilist aritmeetikat). Alates nende tulemustest on teoreemile olemas mitmeid erinevaid väljendeid ja ümbertõestusi, ning teooria on aluseks paljudele edasistele uurimistele primaarvude jaotuse kohta, sealhulgas primaararvude jaotusele aritmeetilistes jadas.

Tagajärjed ja rakendused

  • Krüptograafia: primaararvude esinemissageduse teadmine on oluline suures osas tänapäevastest krüptosüsteemidest (nt RSA), kus primesuhe määrab võtmete genereerimise kulukuse.
  • Teoreetiline arvujaotus: primaarvuteoreem annab aluse täpsemate küsimuste uurimiseks, näiteks primaaride jaotusele kindlate vormidega (aritmeetilistes jadas) või primaaride vahede statistikale.
  • Lisafunktsioonid: Chebyshev' funktsioonid θ(x) ja ψ(x), samuti funktsioonid nagu R(x) ja li(x), aitavad saada täpsemaid hinnanguid ja arendada arvulisi algoritme primaaride leidmiseks.

Kokkuvõtlikult kirjeldab primaarvuteoreem fundamentaalset omadust: kuigi primaarve arv kasvab lõpmatuseni, muutub nende suhteline esinemissagedus järjest väiksemaks ja seda juhib aastaid tuntud logaritmiline seaduspära.