Prost broj

Ovaj članak ili neki od njegovih odlomaka nije dovoljno potkrijepljen izvorima (literatura, veb-sajtovi ili drugi izvori). Ako se pravilno ne potkrijepe pouzdanim izvorima, sporne rečenice i navodi mogli bi biti izbrisani. Pomozite Wikipediji tako što ćete navesti validne izvore putem referenci te nakon toga možete ukloniti ovaj šablon.

Prost broj je prirodni broj veći od 1 koji je dijeljiv jedino sa 1 i samim sobom.

Primjeri prostih brojeva su: 2, 3, 5, 7,...

Broj ${\displaystyle a\,}$ ne možemo rastaviti na proste faktore ako je: ${\displaystyle a=k\cdot l\Rightarrow a=k\lor a=l}$.

Broj ${\displaystyle a\,}$ je prost ako je ${\displaystyle a\,}$ dijeli ${\displaystyle p\cdot q\Rightarrow a\,}$ dijeli ${\displaystyle p\,}$ ili ${\displaystyle a\,}$ dijeli ${\displaystyle q\,}$.

Lahko se može dokazati da ako je broj prost onda је i nerastavljiv i obrnuto. Složen broj je broj koji je djeljiv samim sobom, sa 1, te još nekim brojem.

Svaki složeni broj može se na jedinstven način rastaviti na proste faktore:

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