Prost broj

Za drugu upotrebu, pogledajte članak Broj (višeznačna odrednica).

Prirodni brojevi od 0 do 100. Prosti brojevi su označeni crvenom bojom.

Prosti brojevi su prirodni brojevi veći od jedan koji nisu proizvodi dva manja broja.

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 $a\,$ je nerastavljiv broj ako važi: $a=k\cdot l\Rightarrow a=k\lor a=l$. Broj $a\,$ je prost broj ako važi: $a\,$ deli $p\cdot q\Rightarrow a\,$ deli $p\,$ ili $a\,$ deli $q\,$. 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.

Definicija

$12:3=4$, $11$ je prost broj

Prirodni broj (1, 2, 3, 4, 5, 6, etc.) se zove prost broj, ako je veći od 1 i ako se ne može zapisati kao proizvod dva prirodna broja koja su manja od njega. Brojevi veći od 1 koji nisu prosti brojevi se zovu složenim brojevima. Drugim rečima, $n$ je prost, ako se $n$ stavki ne može podeliti na manje grupe jednake veličine sa više od jedne stavke, ili ako nije moguće organizovati $n$ tački na pravougaonoj rešetci tako da je više od jedne tačke široka ili više od jedne tačke visoka. Na primer, među brojevima od 1 do 6, brojevi 2, 3, i 5 su prosti brojevi, jer nema drugih brojeva koji ih ravnomerno dele (bez ostatka). Isto tako, broj 12 nije prost, jer se 12 može podeliti u 3 kolone po 4 elementa. Broj 11 se može smestiti samo u jednu ili 11 kolona od po 11 odnosno 1 elemenat, tj 11 je prost broj.

Iz navedenog se vidi da su prirodni brojevi podeljeni u tri klase.

• Broj 1
• Prosti brojevi
• Složeni brojevi

U skupu prirodnih brojeva broj $1$ ima poseban položaj, i zato je izdvojen u posebnu klasu. Deljivost u skupu $\mathbb {N}$ može se proširiti na skup $\mathbb {N} _{0}$ i reći da je $0$ deljiva sa svakim prirodnim brojem, jer je $0=a\times 0$. Broj $0$ nije ni prost ni složen broj.

Ovo se može reći na još jedan način: broj $n>1$ je prost, ako se može napisati kao proizvod dva prirodna broja $a$ i $b$, koji su veći od $1$

$n=a\times b$

Svi prosti brojevi manji od 1000 su:

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, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997

Osnovna teorema aritmetike

Za svaki prirodni broj $n$ ($n>1$) postoji jedinstven rastav na proste faktore $n={p_{1}}^{a_{1}}\times {p_{2}}^{a_{2}}\times ...\times {p_{k}}^{a_{k}}$

Gde su $p_{1}<p_{2}<...<p_{k}$ te su svi $p_{i}$ prosti brojevi.

Primer

$23244=2\times 2\times 3\times 13\times 149=2^{2}\times 3\times 13\times 149$

$1200=2^{4}\times 3^{1}\times 5^{2}=3\times 2\times 2\times 2\times 2\times 5\times 5=5\times 2\times 3\times 2\times 5\times 2\times 2$

Rastavljanje složenih brojeva na proste faktore

Rastavljanje se može postići deljenjem s prostim brojevima, i uz poznavanje nekoliko jednostavnih pravila, to rastavljanje postaje vrlo jednostavno.

• Ako je broj paran (zadnja cifra mu je 2, 4, 6, 8 ili 0) onda je deljiv s brojem 2.
• Ako broj završava ciframa 5 ili 0 onda je deljiv s brojem 5.
• Ako mu je zbir cifara deljiv s 3, onda je taj broj deljiv s 3.

Eratostenovo sito

Glavni članak: Eratostenovo sito

Ovo je mehanički postupak pronalaženja prostih brojeva koji nisu veći od n. Ispišu se svi brojeve od 2 do n. Pođe se od broja 2 i precrta se svaki drugi broj, zatim se pođe od broja 3 i precrta se svaki treći s time da se broje i precrtani brojevi, pa od prvog neprecrtanog broja itd. Ovaj postupak se ponavlja dok ne dođe do broja p za koji je p^2 > n. Neprecrtani brojevi su prosti. Primer za $n=20$:

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20

Kriptografija

Važna primena prostih brojeva je u oblasti kriptografije. Algoritmi za šifriranje poruke zavise od toga što ne postoji efikasan algoritam za rastavljanje broja na proste faktore. Tako se lako mogu pomnožiti dva dovoljno velika prosta broja, međutim, obrnuti proces, tj. nalaženje njegovih prostih faktora traje dosta duže. Poznata šifra koja na tome bazira je RSA.

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

$\lim _{x\to \infty }\sum _{p<x}{\frac {1}{p}}\ \sim \ \ln \ln x$

U matematici postoji funkcija $\pi (x)\,$ čija je vrednost jednaka broju prostih brojeva u intervalu $(1,x]\,$. Ona daje odgovor na pitanje koliko ima prostih brojeva manjih od nekog datog. Tako je $\pi (100000)=9592\,$. Funkcija se za veće brojeve može aproksimirati sledećim izrazom

$\pi (x)\sim {\frac {x}{\ln x-1}}$.

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

Manjih od broja	ima prostih brojeva $\pi (x)$
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

Gustina raspodele prostih brojeva

Posmatrajmo odnos gustine prostih brojeva manjih od nekog broja n i recipročne vrednosti prirodnog logaritma tog broja. Gustina prostih brojeva u skupu $\mathbb {N}$ opada kao i recipročna vrednost prirodnog logaritma broja n, za velike vrednosti n ($k/m\to 1$).

n	$k=\pi (n)/n$	$m=1/ln(n)$	$k/m$
$10^{3}$	0,168	0,1448	1,16022
$10^{6}$	0,078498	0,0723824	1,08449
$10^{9}$	0,050847534	0,048254942	1,05372
$10^{12}$	0,037607912018	0,03619120682	1,03914
$10^{24}$	0,018435599767349	0,018095603412635	1,018788

Dirihlova teorema

Neka su d i a prirodni brojevi takvi da je njihova mera $(d,a)=1$, tj. oni su relativno prosti, tada postoji beskonačno mnogo prim brojeva oblika $dn+a$, $n\in N_{0}$, tj. postoji beskonačno mnogo prim brojeva u aritmetičkom nizu $a,\ d+a,\ 2d+a,\ 3d+\ a...$

Prosti brojevi 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, … u aritmetičkim nizu

$1+2n$

Prosti brojevi 5, 13, 17, 29, 37, 41, 53, 61, 73, 89, … u aritmetičkim nizu $1+4n$

Prosti brojevi 3, 7, 11, 19, 23, 31, 43, 47, 59, 67, … u aritmetičkim nizu $3+4n$

Euklidova teorema

Skup svih prostih brojeva je beskonačan.

Dokaz za neke opšte aritmetičke nizove. Svaki prost broj veći od 2 je neparan, te je oblika $4n+3$ ili $4n+1$. Proizvod dva broja oblika $4n+1$ takođe je tog oblika:

$(4a+1)(4b+1)=16ab+4a+4b+1=4(4ab+a+b)+1$

Pretpostavimo da postoji konačno mnogo prostih brojeva

$p_{1},p_{2},...,p_{n}$ koji su oblika $4n+3$.

$N=4\times p_{1}\times p_{2}\times ...\times p_{n}-1=4\times (p_{1}\times p_{2}\times ...\times p_{n}-1)+3$

N je prost broj, ili se može rastaviti na proizvod prostih brojeva, od kojih nijedan nije $p_{1},p_{2},...,p_{n}$ jer ostatak deljenja broja N sa nekim od brojeva p je -1. Svi prosti faktori broja N ne mogu biti oblika $4n+1$, jer N nije tog oblika. Kao što smo videli, proizvod brojeva oblika $4n+1$ je takođe je broj tog oblika.

Prema tome, bar jedan prost faktor mora biti oblika $4n+3$, što je nemoguće, jer taj faktor nije nijedan od brojeva p, za koje smo pretpostavili da su svi prosti brojevi oblika $4n+3$.

Dakle, broj prostih brojeva takvog oblika je beskonačan.

Posledica Dirihlove teoreme je

Red recipročnih prostih brojeva oblika $4n+3$

${\frac {1}{3}}+{\frac {1}{7}}+{\frac {1}{11}}+{\frac {1}{19}}+...$ divergira

Najveći poznati prost broj

Trenutno najveći poznati prost broj je 2^74.207.281 − 1 (ovaj broj ima 22.338.618 cifara). Izračunali su ga 15. decembra 2005. godine dva profesora sa Misuri državnog univerziteta. Označava se sa M_30402457 i predstavlja 49. Mersenov prost broj.

Prethodni najveći poznati prost broj je bio M_25964951 = 2^25.964.951 − 1 (42. poznati Mersenov prost broj, 7.816.230 cifara) a pre njega M_24036583 = 2^24.036.583 − 1 (41. poznati Mersenov prost broj, 7.235.733 cifara)

Postoji dobar praktičan razlog zašto su svi veliki 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 prost broj koji nije ovog oblika je 27.653 × 2^9.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 10⁷ decimalnih cifara postoji nagrada od 100000 dolara.

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 10³⁰⁰). Broj n takav da je binomial(n+k-1,k) k-almoust prajm (ima tačno n prostih faktora) je k-poliprost.

Vidi još

• Uzajamno prosti brojevi
• Spisak prostih brojeva
• Deljivost
• Faktorizacija
• Eratostenovo sito
• Euklidov algoritam

Literatura

• Leff, Lawrence S. (2000). Math Workbook for the SAT I. Barron's Educational Series. str. 360. ISBN 978-0-7641-0768-9. 
• Adler, Irving (1960). The Giant Golden Book of Mathematics: Exploring the World of Numbers and Space. Golden Press. str. 16. OCLC 6975809. 
• Henderson, Anne (2014). Dyslexia, Dyscalculia and Mathematics: A practical guide (2nd izd.). Routledge. str. 62. ISBN 978-1-136-63662-2. 
• Gardiner, Anthony (1997). The Mathematical Olympiad Handbook: An Introduction to Problem Solving Based on the First 32 British Mathematical Olympiads 1965–1996. Oxford University Press. str. 26. ISBN 978-0-19-850105-3. 

Spoljašnje veze

• Hazewinkel Michiel, ur. (2001). „Prime number”. Encyclopaedia of Mathematics. Springer. ISBN 978-1556080104. 
• Caldwell, Chris, The Prime Pages at primes.utm.edu.
• Prime Numbers on In Our Time at the BBC.
• Plus teacher and student package: prime numbers from Plus, the free online mathematics magazine produced by the Millennium Mathematics Project at the University of Cambridge.

Generatori i kalkulatori

• Prime Number Checker identifies the smallest prime factor of a number.
• Fast Online primality test with factorization makes use of the Elliptic Curve Method (up to thousand-digits numbers, requires Java).
• Huge database of prime numbers
• Prime Numbers up to 1 trillion Архивирано на сајту Wayback Machine (27. фебруар 2021)