Prosti broj

Izvor: Wikipedija
Prijeđi na navigaciju Prijeđi na pretraživanje
Prirodni brojevi od 0 do 100. Prosti brojevi su označeni crvenom bojom.
Eratostenovo sito do broja 120

Prosti brojevi ili primbrojevi 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]

Osnovni teoremi vezani uz strukturu prostih brojeva[uredi | uredi kôd]

Euklidov teorem[uredi | uredi kôd]

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

Prostih brojeva oblika ima beskonačno mnogo[uredi | uredi kôd]

Dokažimo sada da prostih brojeva oblika ima beskonačno mnogo. Prije svega, jasno je da neparni prosti brojevi mogu isključivo biti u obliku ili Uočimo da vrijedi tj. umnožak dva prosta broja oblika je i sam tog oblika.

Pretpostavimo da je skup svih prostih brojeva oblika

Konstrirajmo sada neparni broj Očito daje ostatak 3 pri dijeljenju s 4 pa barem jedan njegov prosti faktor nije u obliku odnosno barem je jedan faktor u obliku Jasno je da niti jedan od ne dijeli jer očito daje ostatak tj. pri dijeljenju s To znači da postoji još barem jedan prosti broj oblika izvan kontradikcija.

Razmak između prostih brojeva[uredi | uredi kôd]

Važno svojstvo prostih brojeva je da ne postoji najveći razmak između dva prosta broja. To je zbog toga što postoji proizvoljno velik skup uzastopnih složenih brojeva. Takav skup je primjerice

Ipak, jasno je da ovo ne dokazuje da postoji beskonačno mnogo parova prostih brojeva koji su udaljeni za točno Odnosno, nije dokazano da za svaki možemo naći neka dva prosta broja takva da je . Tome svjedoči tzv. hipoteza o Prostim blizancima koja kaže da postoji beskonačno mnogo prostih brojeva koji su udaljeni za točno 2, no ta hipoteza do danas nije dokazana.

Uloga prostih brojeva[uredi | uredi kôd]

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

Neka pravila djeljvosti[uredi | uredi kôd]

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

Ako broj završava znamenkama 5 ili 0 onda je djeljiv s prostim 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.

Ova pravila možemo međusobno kombinirati. Na primjer, ako je broj djeljiv i s 2 i s 3, onda je taj broj zacijelo djeljiv i s brojem 6.

Ako je troznamenkasti broj djeljiv s 8, onda je taj broj djeljiv s 8,

Ako je zbroj znamenaka nekog broja djeljiv s 9, onda je taj broj djeljiv s 9.

Napomenimo da vrijede i obrati svih sedam gore navedenih tvrdnji.

Zanimljivosti[uredi | uredi kôd]

Poznata je rečenica velikog švicarskog matematičara Leonharda Eulera vezana uz proste brojeve: "Matematičari su uzalud do danas pokušavali otkriti neku pravilnost u slijedu prostih brojeva, a mi imamo razloga vjerovati da je to misterija u koju ljudski um nikada neće prodrijeti."[nedostaje izvor]

Izvori[uredi | uredi kôd]

Vanjske poveznice[uredi | uredi kôd]


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