Prirodni broj veći od 1 djeljiv jedino samim sobom i brojem 1 je prost broj. Prirodni brojevi veći od 1 koji nisu prosti su složeni.

Primjer

Prosti brojevi su 2, 3, 5, 7 ..., a složeni 4, 6, 8, 9, 10...

Iz navedenog se vidi se prirodni brojevi dijele na Broj 1 Prosti brojevi. 

U skupu prirodnih brojeva broj 1 ima poseban položaj, zato je izdvojen. Djeljivost u skupu N može se proširiti na skup i reći da je 0 djeljiva sa svakim prirodnim broj, jer je . Broj 0 nije ni prost ni složen broj.

Relativno prosti brojevi

Brojevi a i b su relativno prosti ako je najveći zajednički djelitelj brojeva a i b jednak 1, tj. brojevi a i b nemaju zajedničkih faktora ili nzd(a,b)=1. Ako je prirodni broj a djeljiv sa brojem b onda je svaki višekratnik od a djeljiv sa b.

Dokaz


Da bi suma bila djeljiva sa c dovoljno je da svaki od brojeva a, b bude djeljiv sa c.

Dokaz:

Ako je

n onda je

Da bi suma , u kojoj je broj a djeljiv sa c, bila djeljiva sa c potrebno je da i drugi broj bude djeljiv sa c.

Dokaz

imamo

Svaki prirodni broj djeljiv je sa bar jednim prostim brojem.

Dokaz

Ako je n prost broj djeljiv je samim sobom, a ako je složen među njegovim djeljiteljima postoji najmanji. Označimo ga sa p. On mora biti prost broj, jer ako bi bio slozen, postojao bi manji djelitelj kao faktor od p. Svaki prost broj djeljiv je sam sa sobom.

Svaki slžen broj možemo napisati kao proizvod prostih brojeva.

Dokaz

Neka je najmanji prost broj, sa kojim je složen broj n djeljiv. Za imamo Ako je složen, postoji najmanji prosti broj takav da . Ovaj postupak možemo nastaviti dok ne dođemo do oblika , a kako je jednom ćemo doći do koji je prost broj.

Primjer

Prostih brojeva ima beskonačno mnogo.

Dokaz

Pretpostavimo da ima konačno mnogo prostih brojeva, i to n njih. Posmatrajmo broj . On je veći od svakog prostog broja i kao takav ne može biti prost. Nije djeljiv ni sa jednim prostim brojem (pri dijeljenju uvijek ostane ostatak 1)

Postoji po volji beskonačno mnogo složenih brojeva.

Dokaz

Za bilo koji prosti broj p, postoji složeni broj . Budući da ima beskonačno mnogo prostih brojeva, onda ima i ovakvih složenih.

Osnovni teorem aritmetike


postoji jedinstven način rastavljanja na proste faktore: Gdje su

te su svi p i prosti brojevi. Faktorizacija svakog prirodnog broja na proste faktore je jedinstvena do na poredak prostih faktora.

Euklidov teorem

Skup svih prostih brojeva je beskonacan, tj. ne postoji najveći prosti broj.

Prostih brojeva ima beskonačno mnogo.

Dokaz

Pretpostavimo suprotno tj. da ih ima konačno mnogo. Ako ih označimo sa tada definišemo

Tada P nije djeljiv sa niti jednim prostim brojem, a iz ranijih tvrdnji zaključujemo da je P ili prost ili ima prostog djelitelja koji je tada različit od svih p. To je u kontradikciji sa pretpostavkom te smo dokazali tvrdnju.

Eratostenovo sito

Ovo je mehanički način pronalaženja prostih brojeva koji nisu veći od n. Ispišemo sve brojeve od 2 do n. Pođemo od broja 2 i precrtavamo svaki drugi broj, zatim pođemo od broja 3 i precrtavamo svaki treći s time da brojimo i precrtane brojeve, pa od prvog neprecrtanog broja itd. Ovaj postupak ponavljamo dok ne dođemo do broja p za koji je . Neprecrtani brojevi su prosti.

Primjer za n=20

Eratostenovo sito'.jpg

Community content is available under CC-BY-SA unless otherwise noted.