Teorema o prostim brojevima

Teorema (o prostim brojevima) – engl. Prime Number Theorem (PNT)

Tvrdnja teoreme je da se funkcija moze aproksimirati na sljedeci nacin

$\pi(x)\approx \frac{x}{lnx}$

odnosn

$\lim_{n \to \infty}\frac{\pi (x) (x))}{{x/lnx}}=1$

Prvu sumnju o ovom problemu predstavili su, nezavisno jedan o drugome, C.F.Gauss i A.M.Legendre na prijelazu iz XVIII u XIX vijek.

Legendre je 1798. god. formulisao aproksimaciju za $\pi(x)$ u obliku:

$\pi(x)= \frac{x}{Alnx+B}$

Utvrdio je da bi za najbolju aproksimaciju konstante trebale biti A = 1, B = −1.08366. Legendre je radio sa tablicama prostih brojeva gdje je x bio manji od 400 000, te je zbog toga pogresno odredio konstantu B. Na vecim primjerima se pokaze da je aproksimacija bolja ako je B = -1.

Gauss je u svom poznatom pismu njemackom astronomu Johann Franz Enckeu, poslanom na Badnjak 1849, napisao kako je on kao aesnaestogodisnjak primjetio da gustoca prostih brojeva opada aproksimativno kao $\frac{1}{lnx}$. Te je dosao do pretpostavke da bi se funkcija mogla prikazati pomocu

$\pi{x} \approx{Li{(x})}= \int_{2}^{x} \frac{dt}{lnt}\,$

thumb|left 1896. Jacques-Salomon Hadamard i Charles Jean de la Vallée-Poussin dokazali su nezavisno jedan o drugome PNT. Svedski matematicar Niels Fabian Helge von Koch je pokazao, ako je Riemannova hipoteza tacna, da vrijedi: Najbolja aproksimacija od navedenih u tablici, za funkciju $\pi(x)$ je Gaussov $Li(x)$, te se po L'Hospitalovom pravilu dobija

$\lim_{x \to \infty}\frac{Li(x)}{x/lnx}=1$

thumb|left Usporedjivanje raznih aproksimacija za $\pi{x}$

Procjena n-tog prostog broja

Neka je $p(n)$ n-ti prost broj, tada kao posljedica PNT sljedi:

$p(n)\sim{ n*ln(n)}$

Pierre Dusart : $p(n) > n (log n + log log n - 1)$

G. Robin: za $n > 8601$

$n (log n + log log n - 1.0073) < p(n) < n (log n + log log n - 0.9385)$

Milioniti prosti broj je prema toj procjeni između 15,434,000 i 15,502,000

Tacna vrijednost

$p(10^6 ) = 15,485,863$ Kategorija:Algebra