Praštevilski izrek: definicija, zgodovina in pomen v teoriji števil
Izrek o praštevilu je izrek iz teorije števil. Natančneje, če z π(x) označimo število praštevil manj ali enako x, potem izrek pravi, da velja π(x) ~ x / ln(x) za x → ∞, kar pomeni, da je razmerje π(x) / (x / ln x) → 1. Posledica te trditve je, da je verjetnost, da naključno izbrano veliko število okoli x predstavlja praštevilo, približno 1 / ln(x). Povprečna razlika med zaporednimi praštevilskimi števili (prvenstveno v območju okoli velikega N) je zato približno ln(N).
Primer z števkami
Če gledamo števila z n števkami, so to približno številke reda veličine 10n. Verjetnost, da naključno izbrano število z n števkami (približno velikosti 10n) postane praštevilo, je torej okoli 1 / ln(10n) = 1 / (n · ln 10). Tako je verjetnost za n = 1000 približno 1 / (1000 · ln 10) ≈ 1 / 2302,6, torej približno ena od 2303 števil. Za n = 2000 je podobno približno 1 / (2000 · ln 10) ≈ 1 / 4605,2, torej približno ena od 4605 števil. Iz tega izhaja tudi poenostavljena opazka, da pri podvojitvi števila števk verjetnost (približno) pade za polovico.
Zgodovina in dokazi
Že kot mlad je o tej povezanosti med praštevilkami in logaritmi. razmišljal Carl Friedrich Gauss, ki je približno leta 1793 prišel do hipoteze, da je π(x) približno integral (logaritemska integrala) ali vsaj sorazmeren z x / ln x. Adrien‑Marie Legendre je nezavisno predlagal podobno formulo okoli leta 1798. Dokaz izreka sta leta 1896 neodvisno podala Jacques Hadamard in Charles‑Jean de La Vallée Poussin; ta dokaz temelji na analitičnih lastnostih Riemannove zeta funkcije ζ(s), zlasti na dejstvu, da ζ(s) nima ničel z realnim delom enakim 1, kar omogoči ustrezno oceno števila praštevil.
Kasneje so Paul Erdős in Atle Selberg leta 1949 ponudili tako imenovan »elementarni« dokaz izreka (brez uporabe kompleksne analize Riemannove zeta funkcije), čeprav je izraz »elementarni« v tem primeru tehničen — dokaz je še vedno precej zapleten. Razvili so se tudi močnejši rezultati o napaki pri približku π(x) ≈ x / ln x; natančnejše aproksimacije vključujejo logaritemski integral Li(x), ki je za večje x natančnejše približanje od x / ln x.
Pomen in nadaljnje posledice
- Izrek o praštevilu je temeljni rezultat v analitični teoriji števil in daje splošno razumevanje porazdelitve praštevil.
- Praktično je pomemben pri izbiri velikih praštevil v kriptografiji, kjer ocene verjetnosti pojavljanja praštevil pomagajo oceniti, koliko naključnih števil je treba preveriti, da najdemo praštevilo primerne velikosti.
- Izrek vodi tudi v raziskave o razlikah med praštevilskimi zaporedji (praštevilski presledki) in v naprednejše probleme, kot je Riemannova hipoteza, katere potrditev bi dala veliko ostrejše ocene napake pri približku π(x) z Li(x).
Dodatne opombe o napakah in izboljšavah
Bolje natančno aproksimacijo števila praštevil zagotavlja logaritemski integral Li(x) = ∫_2^x dt / ln t, za katerega velja π(x) ~ Li(x) in ki za praktične vrednosti pogosto napove π(x) natančneje kot x / ln x. Če bi bila Riemannova hipoteza resnična, bi to zagotovilo zelo močne ocene napake med π(x) in Li(x) (približno O(√x ln x)). Brez Riemannove hipoteze so znane šibkejše ocene, vendar so številne izboljšave rezultat globokih tehnik v analitični teoriji števil.
Skupaj izrek o praštevilu povezuje osnovne lastnosti praštevil z analitičnimi funkcijami in logaritmi ter ostaja ena od centralnih tem pri nadaljnjih raziskavah v teoriji števil.
Vprašanja in odgovori
V: Kaj je teorem o prvih številih?
O: Izrek o praštevilskih številih je izrek iz teorije števil, ki pojasnjuje, kako so praštevilska števila razporejena po številskem območju.
V: Ali so praštevilska števila enakomerno razporejena po številskem območju?
O: Ne, praštevil ni enakomerno razporejenih po številskem območju.
V: Kaj formalizira trditev o praštevilkah?
O: Teorem o praštevilskih številih formalizira zamisel, da se verjetnost, da bomo zadeli praštevilo med 1 in danim številom, z rastjo števila zmanjšuje.
V: Kolikšna je verjetnost, da zadenemo praštevilo med 1 in danim številom?
O: Verjetnost zadetka praštevil med 1 in danim številom je približno n/ln(n), kjer je ln(n) funkcija naravnega logaritma.
V: Ali je verjetnost, da zadenemo praštevilo z 2n števkami, večja od verjetnosti, da zadenemo praštevilo z n števkami?
O: Ne, verjetnost, da boš zadel praštevilo z 2n števkami, je približno za polovico manjša kot z n števkami.
V: Kdo je dokazal trditev o praštevilskih številih?
O: Jacques Hadamard in Charles-Jean de La Vallée Poussin sta leta 1896, več kot stoletje po tem, ko je Gauss leta 1793 posumil na povezavo med praštevilskimi števili in logaritmi, dokazala trditev o praštevilskih izrekih.
V: Kolikšna je povprečna razlika med zaporednimi praštevilskimi števili med prvimi N celimi števili?
O: Povprečna razlika med zaporednimi praštevilskimi števili med prvimi N celimi števili je približno ln(N).