Prost Broj

Prosti brojevi ili prim-brojevi su svi prirodni brojevi djeljivi bez ostatka samo s brojem 1 i sami sa sobom, a veći od broja 1.

Prost Broj
Eratostenovo sito do broja 120

Čemu nam prosti brojevi služe?

Prosti nam brojevi služe za rastavljanje složenih brojeva (onih koji nisu prosti) na prim-faktore.

Svaki složeni broj može se na jedinstven način rastaviti na prim-faktore.

  125|5      34|2    25|5      17|17     5|5       1      1      125=5*5*5   34=2*17 

Kako rastaviti složene brojeve na prim-faktore?

Dijeljenjem s prim-brojevima, no ako znamo neka jednostavna pravila to rastavljanje postaje vrlo jednostavno.

Ako je broj paran (zadnja znamenka mu je 2, 4, 6, 8 ili 0) onda je djeljiv s brojem 2.

Ako broj završava znamenkama 5 ili 0 onda je djeljiv s brojem 5.

Ako mu je zbroj znamenaka djeljiv s 3, onda je taj broj djeljiv s 3.


Prost broj je prirodan broj veći od 1, deljiv samo brojem 1 i samim sobom. Prosti brojevi su, na primer:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113,...


Broj Prost Broj  je nerastavljiv broj ako važi: Prost Broj .

Broj Prost Broj  je prost broj ako važi: Prost Broj  deli Prost Broj  deli Prost Broj  ili Prost Broj  deli Prost Broj .

Lako se može pokazati da ako je broj prost onda je i nerastavljiv i obrnuto, tj. to su dva ekvivalentna pojma! Osobine prostih brojeva izučava oblast koja se zove teorija brojeva.

Broj koji pored 1 (jedinice) ima još delilaca se naziva složen broj. To je pojam suprotan prostom, u smislu deljivosti.

Sinonim za prost broj je prim broj.

Brojnost prostih brojeva

Prostih brojeva ima beskonačno mnogo. Ovo je prvi dokazao Euklid u svojim Elementima, knjiga X, Teorema 20. Njegov dokaz je sledeći:

    Pretpostavimo da je broj prostih brojeva konačan. Pomnožimo ih sve i dodajmo 1. Dobićemo broj koji deljen sa bilo kojim prostim brojem daje ostatak 1. Dakle dobili smo broj koji nema delitelja među postojećim brojevima. To jeste prost broj veći od prethodnih.

Matematičari su otkrili još osobina koje su vezane za brojnost prostih brojeva. Ojler je otkrio da red recipročnih prostih brojeva divergira. Čak je nađena asimptotska formula za zbir prostih brojeva manjih od nekog datog

    Prost Broj 

U matematici postoji funkcija Prost Broj  čija je vrednost jednaka broju prostih brojeva u intervalu Prost Broj . Ona daje odgovor na pitanje koliko ima prostih brojeva manjih od nekog datog. Tako je Prost Broj . Funkcija se za veće brojeve može aproksimirati sledećim izrazom

    Prost Broj .

Broj prostih brojeva u nekom opsegu se može videti iz sledeće tablice

Manjih od broja ima prostih brojeva Prost Broj 
10 4
100 25
1.000 168
10.000 1.229
100.000 9.592
1.000.000 78.498
10.000.000 664.579
100.000.000 5.761.455
1.000.000.000 50.847.534
10.000.000.000 455.052.511
100.000.000.000 4.118.054.813
1.000.000.000.000 37.607.912.018
10.000.000.000.000 346.065.536.839
100.000.000.000.000 3.204.941.750.802
1.000.000.000.000.000 29.844.570.422.669
10.000.000.000.000.000 279.238.341.033.925
100.000.000.000.000.000 2.623.557.157.654.233
1.000.000.000.000.000.000 24.739.954.287.740.860
10.000.000.000.000.000.000 234.057.667.276.344.607
100.000.000.000.000.000.000 2.220.819.602.560.918.840
1.000.000.000.000.000.000.000 21.127.269.486.018.731.928
10.000.000.000.000.000.000.000 201.467.286.689.315.906.290

Najveći poznati prost broj

Trenutno najveci poznati prost broj je 277,232,917 - 1 .Ovaj broj predstavlja 50. Mersenov broj.

Prethodni najveći poznati prost broj je 230.402.457 − 1 (ovaj broj ima 9.152.052 cifara). Izračunali su ga 15. decembra 2005. godine dva profesora sa Misuri državnog univerziteta. Označava se sa M30402457 i predstavlja 43. Mersenov prost broj.

Prethodni najveći poznati prost broj je bio M25964951 = 225.964.951 − 1 (42. poznati Mersenov prost broj, 7.816.230 cifara) a pre njega M24036583 = 224.036.583 − 1 (41. poznati Mersenov prost broj, 7.235.733 cifara)

Postoji dobar praktičan razlog zašto su svi veliki poznati prosti brojevi oblika Mersenovih prostih brojeva. To je relativno jednostavan metod za proveru složenosti broja (Lukas-Lemer test). Za ostale brojeve je metoda vremenski zahtevna.

Najveći poznati prost broj koji nije ovog oblika je 27.653 × 29.167.433 + 1 (2.759.677 cifara) i šesti je po veličini na listi najvećih poznatih prostih brojeva.

Za nalaženje prostog broja sa 107 decimalnih cifara postoji nagrada od 100000 dolara.

                                                                                                                                                                         Broj f(x)=(1/360)*x^6+(11/72)*x^4+(38/45)*x^2+14 je ceo broj za sve x i složen za |x|<137, ali je prost za |x|=137 i za oba argumenta x(-137 i 137) iznosi 18420103073(jer je f(x) parna funkcija), što je najmanji prost broj ovog oblika. 

Primena prostih brojeva

Činjenica da je problem nalaženja svih delitelja velikog broja je doveo do pronalaženja metoda za šifrovanje koji se koristi velikim prostim brojevima. U ovakvoj kriptografiji sa javnim ključem je izuzetno važno imati metod za generisanje velikog prostog broja (reda 10300).

Najmanji nenegativan ceo broj n takav da je polinom f(n)=(1/360)*(n^6+55*n^4+304*n^2+5040) prost broj je broj 137, koji je takođe prost (dajući novi prost broj, 18420103073). U kontrasti toga, jedini nenegativni celi brojevi takvi da je polinom (1/60)*(n^6+15*n^4+104*n^2+660)=(1/60)*(n^2+11)*(n^4+4*n^2+60) su 0, 1, 2, 3 i 7 (dajući proste brojeve 11, 13, 23, 59 i 2657, respektivno). Beleška: 2, 3 i 7 su takođe prosti brojevi

Povezano

Vanjske poveznice

Tags:

Prost Broj Čemu nam prosti brojevi služe?Prost Broj Kako rastaviti složene brojeve na prim-faktore?Prost Broj Brojnost prostih brojevaProst Broj Najveći poznati prost brojProst Broj Primena prostih brojevaProst Broj PovezanoProst Broj Vanjske povezniceProst BrojDjeljivostPrirodni brojevi

🔥 Trending searches on Wiki Srpskohrvatski / Српскохрватски:

Egipatske piramideBor (grad)Osmansko CarstvoHercegovinaĐorđe BalaševićJagodinaAlgoritamRat u Bosni i HercegoviniREM faza spavanjaGruzijciSlonoviJutarnji listMilan ObrenovićMostarJeres u hrišćanstvuAnatemaZračenjePanta reiRakijaEuroKGBSrna LangoOtpornikTrombBol u trbuhuSavet bezbednosti Ujedinjenih nacijaMarko Todorović (crnogorski glumac)Miloš ŽutićIronijaTuzlaVuk Stefanović KaradžićBolji životAteizamDramaProkletijeIngušetijaOsiguračKoličnikTarzan XRNKDušan NemanjićParanojaProteinSlanutakOrlovi rano lete (film)Drugi Hristov dolazakPlacebo efekatBiljkeAdriana LimaLasicaSpisak šefova države JugoslavijeBar, Crna GoraŽabaLista turcizama u srpskohrvatskom jezikuHalogeni elementiBošnjaciDragana MirkovićPesticidiNada TopčagićMerkurRatni zločini u Kosovskom ratuSpisak pozivnih brojeva u HrvatskojKemseksLuka ModrićKazahstanStokholmski sindromSrbiStari EgipatHerceg NoviBijeli sljezBalkanTrapez (geometrija)EkologijaAutomobilJužnoafrička RepublikaAntička Grčka🡆 More