Prost broj

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 $a\,$ ne možemo rastaviti na proste faktore ako je: $a=k \cdot l \Rightarrow a=k \lor a=l$.

Broj $a \,$ je prost ako je $a \,$ dijeli $p \cdot q \Rightarrow a \,$ dijeli $p \,$ ili $a \,$ dijeli $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

Rastavljanje složenih brojeva na proste faktore

Rastavljanje se može postići dijeljenjem s prostim brojevima, međutim, ako znamo neka jednostavna pravila, to rastavljanje postaje vrlo jednostavno.

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

Kriptografija

Važna primjena prostih brojeva je u oblasti kriptografije. Algoritmi za šifriranje poruke žive od toga sto ne postoji efikasan algoritam za rastavljanje broja na proste faktore. Tako se lahko mogu pomnožiti dva dovoljno velika prosta broja, međutim, obrnuti proces, tj. naći njegove proste faktore traje dosta duže.

Također pogledati

• Mertensovi teoremi