Prosti broj

(Preusmjereno s Prost broj)

Prosti brojevi ili prim-brojevi su svi prirodni brojevi djeljivi bez ostatka samo s brojem 1 i sami sa sobom, a strogo veći od broja 1. Prirodni brojevi koji su veći od broja 1 a nisu prosti brojevi nazivaju se složenim brojevima. Na primjer, 5 je prost broj jer je djeljiv samo s 1 i 5, a 6 je složen broj jer osim što je djeljiv s 1 i 6 dodatno može biti podjeljen s brojevima 2 i 3.[1]

Prirodni brojevi od 0 do 100. Prosti brojevi su označeni crvenom bojom.
Eratostenovo sito do broja 120

Svaki se prosti broj, osim brojeva 2 i 3, može zapisati u obliku 6k + 1 ili 6k − 1, za k ∈ .

Euklidov teoremUredi

Ovdje ćemo dokazati da prostih brojeva ima beskonačno mnogo metodom kontradikcije. Neka je dakle   skup svih prostih brojeva,   Promotrimo broj   Tada je   očito   No, prema fundamentalnom teoremu aritmetike svaki se broj može zapisati kao umnožak konačno mnogo prostih brojeva, što daje kontradikciju.

Uloga prostih brojevaUredi

Prosti brojevi služe pri faktorizaciji, odnosno rastavljanju složenih brojeva na proste ili prim-faktore.

U gornjem smo odjeljku spomenuli da se svaki složeni broj može na jedinstven način rastaviti na nekoliko prim-faktora, a ako je broj   prost tada je jedina takva faktorizacija očito  .

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

Kako rastaviti složene brojeve na prim-faktore?Uredi

Dijeljenjem s prim-brojevima, no ako znamo pravila djeljivosti to rastavljanje postaje jednostavno.

Ako je broj paran (zadnja znamenka mu je 2, 4, 6, 8 ili 0) onda je djeljiv s brojem 2.

Ako broj završava znamenkama 5 ili 0 onda je djeljiv s brojem 5.

Ako mu je zbroj znamenaka djeljiv s 3, onda je taj broj djeljiv s 3. Ako mu je dvoznamenkasti završetak dijeljiv sa brojem 4, onda je taj broj djeljiv s ¨4" , broj 1.824 je djeljiv s brojem 4, jer je dvoznamenkasti završetak "24" djeljiv s "4". Ako je broj djeljiv i s "2" i s "3", onda je taj broj djeljiv i s brojem "6", broj 936 je djeljivs brojem "6", jer je 936 djeljivo s "2" i s "3". Ako mu je troznamenkasti broj djeljiv s "8", onda je taj broj djeljiv s "8", broj 5.960 djeljiv je s "8" jer je mu je zvršetak 960 djeljiv s brojem "8". Ako mu je zbroj znamenaka djeljiv s 9, onda je taj broj djeljiv s 9.

IzvoriUredi


  Nedovršeni članak Prosti broj koji govori o matematici treba dopuniti. Dopunite ga prema pravilima Wikipedije.