Prosti broj

Datoteka:Sieve of Eratosthenes animation.gif

Prosti brojevi ili primbrojevi su svi prirodni brojevi veći od 1 koji su bez ostatka djeljivi samo s brojem 1 i sami sa sobom. Prirodni brojevi veći od 1 koji nisu prosti brojevi nazivaju se složenim brojevima.^[1]^:6 Na primjer, broj 5 je prost jer je djeljiv samo s 1 i 5, dok je 6 složen jer se osim s 1 i 6 može podijeliti i brojevima 2 i 3.

Osnovni teoremi vezani uz strukturu prostih brojeva

Euklidov teorem

Ovdje ćemo metodom kontradikcije dokazati Euklidov teorem koji kaže da prostih brojeva ima beskonačno mnogo.^[1]^:9 Pretpostavimo da je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P } konačan skup svih prostih brojeva,

Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P = \{p_1, p_2,\dots, p_n\} }

i promotrimo broj

Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N = p_1 \cdot p_2 \cdot ... \cdot p_n + 1. }

Očito je ostatak pri dijeljenju ovog broja svakim od prostih brojeva iz Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P } jednak jedan,

Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle N\equiv 1{\pmod {p_{i}}},\forall i=\{1,2,...,n\}}

pa Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle N} nije djeljiv ni sa jednim od njih. No prema Osnovnom stavku aritmetike svaki bi se broj morao moći zapisati kao umnožak konačno mnogo prostih brojeva,^[2] a za ovakav $N$ to ne može biti nijedan broj iz skupa Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P } . Očito postoje prosti brojevi izvan tog skupa, čime se početna tvrdnja dovodi u kontradikciju.

Prostih brojeva oblika $4n+3$ ima beskonačno mnogo

Dokažimo sada da prostih brojeva oblika $4n+3$ ima beskonačno mnogo.^[1]^:9 Prije svega, jasno je da neparni prosti brojevi mogu isključivo biti u obliku $4n+1$ ili $4n+3.$ Uočimo da vrijedi $(4s+1)(4t+1)=4(4st+s+t)+1,$ tj. umnožak dva prosta broja oblika $4n+1$ je i sam tog oblika.

Pretpostavimo da je $S=\{p_{1},p_{2},...,p_{n}\}$ skup svih prostih brojeva oblika $4n+3.$

Konstruirajmo sada neparni broj $m=4p_{1}p_{2}\cdot ...\cdot p_{n}-1.$ Očito $m$ daje ostatak 3 pri dijeljenju s 4 pa barem jedan njegov prosti faktor nije u obliku Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 4n+1,} odnosno barem je jedan faktor u obliku Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 4n + 3. } Jasno je da niti jedan od $p_{1},p_{2},...,p_{n}$ ne dijeli Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m } jer očito $m$ daje ostatak Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle -1,} tj. Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_i - 1, } pri dijeljenju s $p_{i},i=\{1,2,...,n\}.$ To znači da postoji još barem jedan prosti broj oblika Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 4n + 3 } izvan Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S, } kontradikcija.

Razmak između prostih brojeva

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 između svaka dva prosta broja. Takav skup je primjerice

Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle S = \{n! + 2, n! + 3, ..., n! + n : n \in \mathbb{N}\},n > 1.}

Ovo vrijedi jer je svaki broj Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n! + 2, ..., n! + n } redom djeljiv s 2, 3, ..., n pa su brojevi složeni.

Ipak, jasno je da ovo ne dokazuje da postoji beskonačno mnogo parova prostih brojeva Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_1, p_2} koji su udaljeni za točno Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k.} Tome svjedoči tzv. hipoteza o prostim brojevima 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.^[3] Isto tako, nije dokazano da postoji beskonačno mnogo parova prostih brojeva čija je je razlika jednaka Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} . Primijetimo da je ova tvrdnja izravna posljedica toga da hipoteza o prostim brojevima blizancima nije dokazana.

Uz to, nije dokazano ni da za svaki Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k \in \mathbb{N}} možemo naći neka dva prosta broja Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_1 < p_2 } takva da je Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p_2 - p_1 = k } .

Uloga prostih brojeva

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

Svaki se složeni broj može na jedinstven način rastaviti na nekoliko prim-faktora, a ako je broj Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p } prost tada je jedina takva faktorizacija očito Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p = p \cdot 1 } .

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

Neka pravila djeljvosti

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 djeljiv s 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.

Vrijede dakako i obrati svih navedenih tvrdnji.

Zanimljivosti

Poznata je rečenica velikog švicarskog matematičara Leonharda Eulera vezana uz proste brojeve:^[4]

Matematičari su uzalud do danas pokušavali otkriti pravilnost u slijedu prostih brojeva, a mi imamo razloga vjerovati da je to misterija u koju ljudski um nikada neće prodrijeti.

Izvori

↑ ^1,0 ^1,1 ^1,2
• Nepoznat parametar: authorlink
• Parametar format nije dopušten u klasi book
↑
• Parametar format nije dopušten u klasi book
↑ https://hrcak.srce.hr › filePDF Prosti brojevi blizanci
↑
• Parametar accessdate nije dopušten u klasi web

Vanjske poveznice

Primbrojevi na mrežnom izdanju Hrvatske enciklopedije

Nedovršeni članak Prosti broj koji govori o matematici treba dopuniti. Dopunite ga prema pravilima uređivanja Hrvatske internetske enciklopedije.

[:0-1] 1,0 ^1,1 ^1,2
• Nepoznat parametar: authorlink
• Parametar format nije dopušten u klasi book

[2] 
• Parametar format nije dopušten u klasi book

[3] ttps://hrcak.srce.hr › filePDF Prosti brojevi blizanci

[4] 
• Parametar accessdate nije dopušten u klasi web

[1]

[2]

[3]

[4]

Prosti broj

Sadržaj

Osnovni teoremi vezani uz strukturu prostih brojeva

Euklidov teorem

Prostih brojeva oblika $4n+3$ ima beskonačno mnogo

Razmak između prostih brojeva

Uloga prostih brojeva

Neka pravila djeljvosti

Zanimljivosti

Izvori

Vanjske poveznice

Navigacijski izbornik

Prosti broj

Osnovni teoremi vezani uz strukturu prostih brojeva

Euklidov teorem

Prostih brojeva oblika 4 n + 3 {\displaystyle 4n+3} ima beskonačno mnogo

Razmak između prostih brojeva

Uloga prostih brojeva

Neka pravila djeljvosti

Zanimljivosti

Izvori

Vanjske poveznice

Navigacijski izbornik

Traži

Prostih brojeva oblika $4n+3$ ima beskonačno mnogo