Prosti brojevi: što su i koji su? KALKULATOR

Prosti brojevi igraju ključnu ulogu u svijetu matematike, često se pojavljuju kao osnova u mnogim matematičkim teoremima i problemima. U ovom članku, istražit ćemo osnove prostih brojeva, od najmanjeg prvog do tehnika računanja i značenja prim brojeva.

1. Najmanji Prosti Broj: Sjaj Jednostavnosti

Najmanji prosti broj je broj 2. Prosti brojevi su prirodni brojevi veći od 1 koji nemaju pozitivne djelitelje osim 1 i samog sebe. Budući da je 2 samo djeljiv s 1 i 2, smatra se najmanjim prostim brojem. Prosti brojevi igraju ključnu ulogu u teoriji brojeva i kriptografiji.

U našem kalkulatoru možete provjeriti je li neki broj prost ili složen:

Kalkulator

Takvih brojeva ima beskonačno. 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.

Popis prosti brojeva do 1000
Popis prosti brojeva do 1000

Najmanji prosti broj je broj 2. To je ujedno i jedini paran broj koji ima samo dva djelitelja.

PRIM brojevi

To 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 (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.

Eratostenovo sito

Eratostenovo sito
Eratostenovo sito prostih brojeva animacija

Postupak pomoću Eratostenovog sita:

  1. napišemo proizvoljan broj uzastopnih prirodnih brojeva počevši od 2
  2. zaokružimo najmanji neoznačeni broj
  3. precrtamo sve njegove višekratnike, koji nisu već označeni
  4. 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šekratnike 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.