Prosti brojevi (prim brojevi) su svi prirodni brojevi djeljivi bez ostatka samo s brojem 1 i sami sa sobom. Broj 1 nije niti prost niti složeni broj. Prirodni brojevi veći od broja 1, koji nisu prosti brojevi nazivaju se složenim brojevima. Složeni brojevi imaju više od dva djelitelja. Npr. 7 je prost broj jer je djeljiv samo s 1 i 7 dok je broj 8 složeni broj jer je djeljiv s 1 i 8 (samim sobom), a može se dijeliti s brojevima 2 i 4.
Kalkulator prostih brojeva
U našem kalkulatoru možete provjeriti je li neki broj prost ili složen:
Takvih brojeva ima beskonačno mnogo. Ovo je prvi dokazao Euklid u svojim Elementima, knjiga X, Teorema 20. Njegov dokaz je sljedeći:
Pretpostavimo da je broj prostih brojeva konačan. Pomnožimo ih sve i dodajmo 1. Dobit ćemo broj koji dijeljen sa bilo kojim prostim brojem daje ostatak 1. Dakle dobili smo broj koji nema djelitelja među postojećim brojevima. To je prost broj veći od prethodnih.
Euklid
Prosti brojevi 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,…
Oni nam služe za rastavljanje složenih brojeva na prim faktore. Svaki složeni broj može se na jedinstven način rastaviti na faktore.
Eratostenovo sito
Eratostenovo sito (rešeto) je jednostavan algoritam za dobivanje svih prostih brojeva manjih od unaprijed izabranoga prirodnog broja. Osmislio ga je grčki matematičar, geograf i astronom Eratosten.
Postupak pomoću Eratostenovog sita:
- napišemo proizvoljan broj uzastopnih prirodnih brojeva počevši od 2
- zaokružimo najmanji neoznačeni broj
- precrtamo sve njegove višekratnike, koji nisu već označeni
- ponavljamo postupak od 2. koraka dok svi brojevi nisu označeni (zaokruženi ili precrtani)
Postupak završi u konačno mnogo koraka, jer na početku imamo konačno mnogo brojeva, a u svakom koraku barem jedan broj označimo. Zaokruženi brojevi su prosti brojevi. Precrtani brojevi su složeni brojevi.
Na slici je demonstracija traženja prostih brojeva manjih od 121. Napisani su svi prirodni brojevi od 2 do 120. U prvom koraku je najmanji neoznačeni broj 2, zato ga označimo crvenom bojom, a onda nježnijom nijansom crvene boje “precrtamo” ostale njegove višekratnike. Nakon toga je najmanji neoznačeni broj broj 3. Njega “zaokružimo” zelenom, a nježnijom nijansom zelene “precrtamo” višekratnike broja 3.
Nakon toga je najmanji neoznačeni broj 5. Njega označimo plavom bojom, a njegove višekratnikom svjetlijom nijansom plave. Isto napravimo s brojem 7. Nakon toga je na redu broj 11. No sve njegove višektratnike smo ionako već precrtali. Zato radi jednostavnosti sve ostale proste brojeve označimo istom bojom, iako to baš nije sasvim korektno.
Složeni brojevi
Složeni broj svaki je pozitivni prirodni broj koji ima barem jedan djelitelj osim broja 1 i samoga sebe. Drugim riječima, složeni broj svaki je prirodni broj koji nije prosti broj.
Broj 1 nije ni prosti broj ni složeni broj.
Broj 12 jest složeni broj jer je djeljiv s: 1, 2, 3, 4, 6 i samim sobom (12), tj. ima više od 2 djelitelja. Svi parni brojevi veći od 2 su složeni brojevi ( 4, 6, 8, 10, 12, 14, 16, 18, 20…) zato što su oni djeljivi barem s jedan, sa samim sobom i s 2 (svi parni brojevi djeljivi su s 2) odnosno imaju više od dva djelitelja.
Relativno prosti brojevi
Relativno prosti brojevi su prirodni brojevi koji nemaju zajedničkog djelitelja osim 1. Teoriju relativnosti utemeljio je Albert Einstein.
To je teorija po kojoj su prostorne i vremenske veličine relativne, tj. ne mogu se određivati neovisno jedne o drugima. Brojevi a i b su relativno prosti ako je njihov najveći zajednički djelitelj jednak 1, tj. brojevi a i b nemaju zajedničkih faktora. Primjer: brojevi 10 i 21 su relativno prosti brojevi, jer iako niti jedan od njih nije prost sam za sebe, oni međusobno nemaju zajedničkih djelitelja osim broja 1.