Изворни код странице Teorema prostih brojeva

U [[number theory|teoriji brojeva]], '''teorema prostih brojeva''' ({{jez-eng-lat|prime number theorem}}, -{'''PNT'''}-) opisuje [[asymptotic analysis|asimptotsku]] distribuciju [[prime number|prostih brojeva]] među pozitivnim celim brojevima. To formalizuje intuitivnu ideju da prosti brojevi postaju manje zastupljeni kako postaju veći u skladu sa precizno kvantifikovanom stopom kojom do toga dolazi. Teoremu su nezavisno dokazali [[Žak Adamar]] i [[Charles Jean de la Vallée Poussin|Šarl Žan de la Vale-Pusen]] 1896. godine, koristeći ideje koje je uveo [[Bernhard Riman]] (naročito [[Риманова зета-функција|Rimanovu zeta funkciju]]).

Prva takva raspodela je {{math|''π''(''N'') ~ {{sfrac|''N''|log(''N'')}}}}, gde je {{math|''π''(''N'')}} [[funkcija raspodele prostih brojeva]] i {{math|log(''N'')}} je [[prirodni logaritam]] od {{mvar|N}}. To znači da za dovoljno veliko {{mvar|N}}, [[verovatnoća]] da je slučajni celi broj koji nije veći od {{mvar|N}} prost broj vrlo blizu {{math|1 / log(''N'')}}. Sledstveno tome, za slučajni celi broj sa najviše {{math|2''n''}} cifara (za dovoljno veliko {{mvar|n}}) postoji približno upola manja verovatnoća da će on biti prost broj kao slučajni celi broj sa najviše {{mvar|n}} cifara. Na primer, među pozitivnim celim brojevima od najviše 1000 cifara, jedan od 2300 je prost broj ({{math|log(10<sup>1000</sup>) ≈ 2302,6}}), dok je među pozitivnim celim brojevima sa najviše 2000 cifara, približno jedan od 4600 prost broj ({{math|log(10<sup>2000</sup>) ≈ 4605,2}}). Drugim rečima, prosečni razmak između uzastopnih prostih brojeva među prvih {{mvar|N}} celih brojevima je oko {{math|log(''N'')}}.<ref>{{cite book|last = Hoffman|first = Paul|title = The Man Who Loved Only Numbers|url = https://archive.org/details/manwholovedonlyn00hoff/page/227|url-access = registration|publisher = Hyperion Books|year = 1998|page = [https://archive.org/details/manwholovedonlyn00hoff/page/227 227]|isbn = 978-0-7868-8406-3|mr = 1666054|location = New York}}</ref>

== Iskaz ==
[[File:Prime number theorem ratio convergence.svg|thumb|300px|Grafikon koji prikazuje odnos funkcije raspodele prostih brojeva {{math|''π''(''x'')}} i dve njene aproksimacije, {{math|''x'' / log ''x''}} i {{math|Li(''x'')}}. Kako se {{mvar|x}} povećava (napomena: {{mvar|x}} osa je logaritamska), oba se odnosa kreću prema 1. Odnos za {{math|''x'' / log ''x''}} konvergira odozgo vrlo sporo, dok odnos za  {{math|Li(''x'')}} brže konvergira odozdo.]]
[[File:Prime number theorem absolute error.svg|thumb|300px|Log-log grafikon prikazuje apsolutnu grešku od {{math|''x'' / log ''x''}} i {{math|Li(''x'')}}, dve aproksimacije funkcije raspodele prostih brojeva {{math|''π''(''x'')}}. Za razliku od odnosa, razlika između {{math|''π''(''x'')}} i {{math|''x'' / log ''x''}} se povećava bez ograničenja kako se {{mvar|x}} povećava. S druge strane, {{math|Li(''x'') − ''π''(''x'')}} manja znak beskonačno mnogo puta.]]

Neka je {{math|''π''(''x'')}} [[prime-counting function|funkcija raspodele prostih brojeva]] koja daje broj prostih brojeva manji ili jednak sa {{mvar|x}}, za svaki realni broj&nbsp;{{mvar|x}}. Na primer, {{math|''π''(10) {{=}} 4}}, jer postoje četiri prosta broja (2, 3, 5 i 7) manja ili jednaka od 10. Prema teoremi prostih brojeva tada je {{math|''x'' / log ''x''}} dobra aproksimacija za {{math|''π''(''x'')}} (gde log značava prirodni logaritam), u smislu da je [[limit of a function|limit]] količnika dve funkcije {{math|''π''(''x'')}} i {{math|''x'' / log ''x''}} kako se {{mvar|x}} povećava bez ograničenja jednak 1:

: <math>\lim_{x\to\infty}\frac{\;\pi(x)\;}{\;\left[ \frac{x}{\log(x)}\right]\;} = 1,</math>

Ovo je poznato kao '''asimptotski zakon distribucije prostih brojeva'''. Koristeći [[Велико О|asimptotsku notaciju]] ovaj rezultat se može napisati kao

:<math>\pi(x)\sim \frac{x}{\log x}.</math>

Ova notacija (i [[teorema]]) ''ne'' govori o limitu ''razlike'' dve funkcije kad se {{mvar|x}} povećava bez ograničenja. Umesto toga, teorema navodi da {{math|''x'' / log ''x''}} aproksimira {{math|''π''(''x'')}} u smislu da se [[Грешка у апроксимацији|relativna greška]] ove aproksimacije približava 0, kada se {{mvar|x}} povećava bez ograničenja.

Teorema prostih brojeva je ekvivalentna tvrđenju da {{mvar|n}}-ti prosti broj {{mvar|p<sub>n</sub>}} zadovoljava

:<math>p_n \sim n\log(n),</math>

asimptotska notacija ponovo ukazuje na to da relativna greška ove aproksimacije pristupa 0 kad se {{mvar|n}} povećava bez ograničenja. Na primer, {{val|2|e=17}}-ti prosti broj je {{val|8512677386048191063}},<ref>{{cite web|title=Prime Curios!: 8512677386048191063|url=http://primes.utm.edu/curios/cpage/24149.html|work=Prime Curios!|publisher=University of Tennessee at Martin|date=9. 10. 2011}}</ref> i ({{val|2|e=17}})log({{val|2|e=17}}) zaokružuje se na {{val|7967418752291744388}}, sa relativnom greškom od oko 6,4%.

Teorema prostih brojeva je isto tako ekvivalentna sa
:<math>\lim_{x\to\infty} \frac{\vartheta (x)}x = \lim_{x\to\infty} \frac{\psi(x)}x=1,</math>
gde su {{mvar|ϑ}} i {{mvar|ψ}} prva i druga [[Chebyshev function|Čebiševa funkcija]], respektivno.

== Tabela {{math|''π''(''x'')}}, {{math|''x'' / log ''x''}}, and {{math|li(''x'')}} ==

U ovoj tabeli su upoređene vrednosti {{math|''π''(''x'')}} sa dve aproksimacije {{math|''x'' / log ''x''}} i {{math|li(''x'')}}. Zadnja kolna, {{math|''x'' / ''π''(''x'')}}, je prosek [[prime gap|razmaka]] između prostih brojeva ispod&nbsp;{{mvar|x}}.
:{| class="wikitable" style="text-align: right"
! {{mvar|x}}
! {{math|''π''(''x'')}}
! {{math|''π''(''x'') − {{sfrac|''x''|log ''x''}}}}
! {{math|{{sfrac|''π''(''x'')|''x'' / log ''x''}}}}
! {{math|li(''x'') − ''π''(''x'')}}
! {{math|{{sfrac|''x''|''π''(''x'')}}}}
|-
| 10
| 4
| −0.3
| 0.921
| 2.2
| 2.5{{0|00}}
|-
| 10<sup>2</sup>
| 25
| 3.3
| 1.151
| 5.1
| 4{{0|.000}}
|-
| 10<sup>3</sup>
| 168
| 23{{0|.0}}
| 1.161
| 10{{0|.0}}
| 5.952
|-
| 10<sup>4</sup>
| {{val|1229|fmt=gaps}}
| 143{{0|.0}}
| 1.132
| 17{{0|.0}}
| 8.137
|-
| 10<sup>5</sup>
| {{val|9592|fmt=gaps}}
| 906{{0|.0}}
| 1.104
| 38{{0|.0}}
| 10.425
|-
| 10<sup>6</sup>
| {{val|78498}}
| {{val|6116|fmt=gaps}}{{0|.0}}
| 1.084
| 130{{0|.0}}
| 12.740
|-
| 10<sup>7</sup>
| {{val|664579}}
| {{val|44158}}{{0|.0}}
| 1.071
| 339{{0|.0}}
| 15.047
|-
| 10<sup>8</sup>
| {{val|5761455}}
| {{val|332774}}{{0|.0}}
| 1.061
| 754{{0|.0}}
| 17.357
|-
| 10<sup>9</sup>
| {{val|50847534}}
| {{val|2592592}}{{0|.0}}
| 1.054
| {{val|1701|fmt=gaps}}{{0|.0}}
| 19.667
|-
| 10<sup>10</sup>
| {{val|455052511}}
| {{val|20758029}}{{0|.0}}
| 1.048
| {{val|3104|fmt=gaps}}{{0|.0}}
| 21.975
|-
| 10<sup>11</sup>
| {{val|4118054813}}
| {{val|169923159}}{{0|.0}}
| 1.043
| {{val|11588}}{{0|.0}}
| 24.283
|-
| 10<sup>12</sup>
| {{val|37607912018}}
| {{val|1416705193}}{{0|.0}}
| 1.039
| {{val|38263}}{{0|.0}}
| 26.590
|-
| 10<sup>13</sup>
| {{val|346065536839}}
| {{val|11992858452}}{{0|.0}}
| 1.034
| {{val|108971}}{{0|.0}}
| 28.896
|-
| 10<sup>14</sup>
| {{val|3204941750802}}
| {{val|102838308636}}{{0|.0}}
| 1.033
| {{val|314890}}{{0|.0}}
| 31.202
|-
| 10<sup>15</sup>
| {{val|29844570422669}}
| {{val|891604962452}}{{0|.0}}
| 1.031
| {{val|1052619}}{{0|.0}}
| 33.507
|-
| 10<sup>16</sup>
| {{val|279238341033925}}
| {{val|7804289844393}}{{0|.0}}
| 1.029
| {{val|3214632}}{{0|.0}}
| 35.812
|-
| 10<sup>17</sup>
| {{val|2623557157654233}}
| {{val|68883734693281}}{{0|.0}}
| 1.027
| {{val|7956589}}{{0|.0}}
| 38.116
|-
| 10<sup>18</sup>
| {{val|24739954287740860}}
| {{val|612483070893536}}{{0|.0}}
| 1.025
| {{val|21949555}}{{0|.0}}
| 40.420
|-
| 10<sup>19</sup>
| {{val|234057667276344607}}
| {{val|5481624169369960}}{{0|.0}}
| 1.024
| {{val|99877775}}{{0|.0}}
| 42.725
|-
| 10<sup>20</sup>
| {{val|2220819602560918840}}
| {{val|49347193044659701}}{{0|.0}}
| 1.023
| {{val|222744644}}{{0|.0}}
| 45.028
|-
| 10<sup>21</sup>
| {{val|21127269486018731928}}
| {{val|446579871578168707}}{{0|.0}}
| 1.022
| {{val|597394254}}{{0|.0}}
| 47.332
|-
| 10<sup>22</sup>
| {{val|201467286689315906290}}
| {{val|4060704006019620994}}{{0|.0}}
| 1.021
| {{val|1932355208}}{{0|.0}}
| 49.636
|-
| 10<sup>23</sup>
| {{val|1925320391606803968923}}
| {{val|37083513766578631309}}{{0|.0}}
| 1.020
| {{val|7250186216}}{{0|.0}}
| 51.939
|-
| 10<sup>24</sup>
| {{val|18435599767349200867866}}
| {{val|339996354713708049069}}{{0|.0}}
| 1.019
| {{val|17146907278}}{{0|.0}}
| 54.243
|-
| 10<sup>25</sup>
| {{val|176846309399143769411680}}
| {{val|3128516637843038351228}}{{0|.0}}
| 1.018
| {{val|55160980939}}{{0|.0}}
| 56.546
|-
| [[OEIS]]
| {{OEIS link|id=A006880}}
| {{OEIS link|id=A057835}}
| 
| {{OEIS link|id=A057752}}
| 
|}

Vrednost za {{math|''π''(10<sup>24</sup>)}} bila je originalno izračunata koristeći [[Риманова хипотеза|Rimanovu hipotezu]].<ref name="Franke">{{cite web |title=Conditional Calculation of {{math|''π''(10<sup>24</sup>)}} |url=http://primes.utm.edu/notes/pi(10%5E24).html |publisher=Chris K. Caldwell |accessdate=3. 8. 2010 |archive-date=25. 09. 2014 |archive-url=https://web.archive.org/web/20140925215921/http://primes.utm.edu/notes/pi(10%5E24).html |url-status=dead }}</ref> Od tada su bezuslovno verifikovane.<ref name="PlattARXIV2012">{{cite journal | last=Platt | first=David | title=Computing {{math|''π''(''x'')}} analytically | year=2015 | journal=[[Mathematics of Computation]] | volume=84 | issue=293 | pages=1521–1535 | mr=3315519 | arxiv=1203.5712 | doi=10.1090/S0025-5718-2014-02884-6 }}</ref>

== Analog za nesvodljive polinome na konačnom polju ==

Postoji analogna teorema prostih brojeva koja opisuje „raspodelu” [[irreducible polynomial|nesažimljivih polinoma]] preko [[Коначно поље|konačnog polja]]; njen oblik je upadljivo sličan sa klasičnom teoremom prostih brojeva.

Da bi se to precizno izrazilo, može se uzeti da je {{math|''F'' {{=}} GF(''q'')}} konačno polje sa {{mvar|q}} elemenata, za neko fiksno {{mvar|q}}, i da je {{mvar|N<sub>n</sub>}} broj [[monic polynomial|monijskih]] nesažimljivih polinoma preko {{mvar|F}} čiji je [[degree of a polynomial|stepen]] jednak {{mvar|n}}. To jest, razmatraju se polinomi sa koeficijentima odabranim iz {{mvar|F}}, koji se ne mogu zapisati kao proizvodi polinoma nižeg stepena. U ovom okruženju, ti polinomi igraju ulogu prostih brojeva, jer su svi drugi monijski polinomi izgrađeni od njihovih proizvoda. Onda se može dokazati da je
:<math>N_n \sim \frac{q^n}{n}.</math>
Ako se uradi supstitucija {{math|''x'' {{=}} ''q''<sup>''n''</sup>}}, onda je desna strana samo
:<math>\frac{x}{\log_q x},</math>
čime se pojašnjava analogija. Kako postoji tačno {{math|''q''<sup>''n''</sup>}} monijskih polinoma stepena {{mvar|n}} (uključujući one koji su sažimljivi), to se može preformulirati na sledeći način: ako je monijski polinom stepena {{mvar|n}} randomno izabran, onda je verovatnoća da je on nesažimljiv oko&nbsp;{{math|{{sfrac|1|''n''}}}}.

Moguće je dokazati i analognu verziju Rimanove hipoteze, naime da je
:<math>N_n = \frac{q^n}n + O\left(\frac{q^\frac{n}{2}}{n}\right).</math>

Dokazi ovih tvrdnji daleko su jednostavniji nego u klasičnom slučaju. To obuhvata kratako kombinatorično razmatranje,<ref>{{cite journal|last=Chebolu|first=Sunil|first2=Ján|last2=Mináč|title=Counting Irreducible Polynomials over Finite Fields Using the Inclusion {{pi}} Exclusion Principle|url=https://archive.org/details/sim_mathematics-magazine_2011-12_84_5/page/369|journal=Mathematics Magazine|date=decembar 2011|volume=84|issue=5|pages=369–371|doi=10.4169/math.mag.84.5.369|jstor=10.4169/math.mag.84.5.369|arxiv=1001.0409}}</ref> sumirano na sledeći način: svaki element stepena {{mvar|n}} proširenja {{mvar|F}} je koren nekog nesažimljivog polinoma čiji stepen {{mvar|d}} deli {{mvar|n}}; pri prebrojavanu ovih korena su uspostavljena dva različita pristupa
:<math>q^n = \sum_{d\mid n} d N_d,</math>
gde suma obuhvata sve [[Дељивост|dilioce]] {{mvar|d}} od {{mvar|n}}. [[Möbius inversion formula|Mebijusova inverzija]] onda daje
:<math>N_n = \frac{1}{n} \sum_{d\mid n} \mu\left(\frac{n}{d}\right) q^d,</math>
gde je {{math|''μ''(''k'')}} [[Mebijusova funkcija]]. (Ova formula je bila poznata Gausu.) Glavni član se javlja za {{math|''d'' {{=}} ''n''}}, i nije teško vezati preostale članove. Izraz „Rimanove hipoteze” zavisi od činjenice da najveći [[Дељивост|svojstveni dililac]] od {{mvar|n}} ne može da bude veći od {{math|{{sfrac|''n''|2}}}}.

== Reference ==
{{Reflist|}}

== Literatura ==
{{Литература|30em}}
* {{Cite journal |last=Hardy |first=G. H. |last2=Littlewood |first2=J. E. |year=1916 |title=Contributions to the Theory of the Riemann Zeta-Function and the Theory of the Distribution of Primes |journal=Acta Mathematica |volume=41 |issue= |pages=119–196 |doi=10.1007/BF02422942 |url=https://zenodo.org/record/2294397/files/article.pdf }}
* {{Cite journal |last=Granville |first=Andrew |year=1995 |title=Harald Cramér and the distribution of prime numbers |journal=Scandinavian Actuarial Journal |volume=1 |issue= |pages=12–28 |url=http://www.dartmouth.edu/~chance/chance_news/for_chance_news/Riemann/cramer.pdf |issn= |doi=10.1080/03461238.1995.10413946 |citeseerx=10.1.1.129.6847 |access-date=18. 02. 2020 |archive-date=23. 09. 2015 |archive-url=https://web.archive.org/web/20150923212842/http://www.dartmouth.edu/~chance/chance_news/for_chance_news/Riemann/cramer.pdf |url-status= }}
* {{cite book | last=Burris | first=Stanley N. | title=Number theoretic density and logical limit laws | series=Mathematical Surveys and Monographs | volume=86 | location=Providence, RI | publisher=[[American Mathematical Society]] | year=2001 | isbn=0-8218-2666-2 | zbl=0995.11001 }}
* {{cite book | title=Abstract Analytic Number Theory | first=John | last=Knopfmacher | edition=2nd | publisher=Dover Publishing | location=New York, NY | year=1990 | origyear=1975 | isbn=0-486-66344-2 | zbl=0743.11002 }}
* {{cite book | first1=Hugh L. | last1=Montgomery | author1-link=Hugh Montgomery (mathematician) | first2=Robert C. | last2=Vaughan | author2-link=Robert Charles Vaughan (mathematician) | title=Multiplicative number theory I. Classical theory | series=Cambridge studies in advanced mathematics | volume=97 | year=2007 | isbn=0-521-84903-9 | zbl=1142.11001 | page=278}}
* {{cite book | author=Alina Carmen Cojocaru|author1-link= Alina Carmen Cojocaru |author2=M. Ram Murty  | title=An introduction to sieve methods and their applications | series=London Mathematical Society Student Texts | volume=66 | publisher=[[Cambridge University Press]] | isbn=0-521-61275-6 | pages=35–38 |author2-link= M. Ram Murty }}
* {{Cite journal | doi=10.1007/BF01444310 | last=Landau | first=Edmund | author-link=Edmund Landau | title=Neuer Beweis des Primzahlsatzes und Beweis des Primidealsatzes | year=1903 | journal=Mathematische Annalen | volume=56 | issue=4 | pages=645–670 | ref=harv | url=https://zenodo.org/record/1735140 }}
* {{Citation| last=Dudek|first=Adrian W.|date=21. 8. 2014|title=On the Riemann hypothesis and the difference between primes|journal=International Journal of Number Theory|volume=11|issue=3|pages=771–778|doi=10.1142/S1793042115500426|issn=1793-0421|arxiv=1402.6417|bibcode=2014arXiv1402.6417D}}
* {{Citation | last1=Ingham | first1=A.E. | authorlink=Albert Ingham|title=The Distribution of Prime Numbers | publisher=Cambridge University Press | series = Cambridge Tracts in Mathematics and Mathematical Physics | volume=30 | year=1932}}. Reprinted 1990, {{isbn|978-0-521-39789-6}}, {{MathSciNet|1074573}}
*{{citation|last=Mazur|first=Barry|last2=Stein|first2=William|year=2015|title=Prime Numbers and the Riemann Hypothesis|url=http://wstein.org/rh/}}
* {{citation | last = Nicely | first = Thomas R. | doi = 10.1090/S0025-5718-99-01065-0 | mr = 1627813 | issue = 227 | journal = Mathematics of Computation | pages = 1311–1315 | title = New maximal prime gaps and first occurrences | url = http://www.trnicely.net/gaps/gaps.html | volume = 68 | year = 1999 | bibcode = 1999MaCom..68.1311N | accessdate=18. 2. 2020 | archiveurl = https://web.archive.org/web/20141230023254/http://www.trnicely.net/gaps/gaps.html | archivedate = 30. 12. 2014 | url-status = dead }}.
{{Литература крај}}

== Spoljašnje veze ==
{{Commons category-lat|Prime number theorem}}
* {{springer|title=Distribution of prime numbers|id=p/d033530}}
* -{[https://web.archive.org/web/20101115185805/http://www.scs.uiuc.edu/~mainzv/exhibitmath/exhibit/felkel.htm Table of Primes by Anton Felkel]}-.
* -{[https://www.youtube.com/watch?v=3RfYfMjZ5w0 Short video] visualizing the Prime Number Theorem.}-
* -{[http://mathworld.wolfram.com/PrimeFormulas.html Prime formulas] and [http://mathworld.wolfram.com/PrimeNumberTheorem.html Prime number theorem] at [[MathWorld]].}-
* {{planetmath reference|id=199|title=Prime number theorem}}
* -{[http://primes.utm.edu/howmany.shtml How Many Primes Are There?]{{Wayback|url=http://primes.utm.edu/howmany.shtml |date=20121015002415 }} and [http://primes.utm.edu/notes/gaps.html The Gaps between Primes] by Chris Caldwell, [[University of Tennessee at Martin]].}-
* -{[http://www.ieeta.pt/~tos/primes.html Tables of prime-counting functions] by Tomás Oliveira e Silva}-

{{Authority control-lat}}

{{СОРТИРАЊЕ:Теорема простих бројева}}
[[Категорија:Аналитичка теорија бројева]]
[[Категорија:Логаритми]]