Prosti broj

Izvor: Wikipedija
Prijeđi na navigaciju Prijeđi na pretraživanje
Eratostenovo sito do broja 120

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]

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

Euklidov teorem[uredi VE | uredi]

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 brojeva[uredi VE | uredi]

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 VE | 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.
P math.png Nedovršeni članak Prosti broj koji govori o matematici treba dopuniti. Dopunite ga prema pravilima Wikipedije.

  1. https://sites.google.com/site/obrojevima/Home/1-razred-1/skup-prirodnih-brojeva/djeljivost-u-skupu-n/kriteriji-djeljivosti