Wikipedija

Prosti broj: razlika između inačica

Pregledaj povijest
← Starija izmjenaNovija izmjena →
Izbrisani sadržaj Dodani sadržaj
VizualnoWikitekst
Oznake: mobilni uređaj m.wiki
+izvori; redaktura
Redak 1:
[[slikaSlika:Primencomposite0100.svg|thumbmini|upright=1.3|Prirodni brojevi od 0 do 100. Prosti brojevi su označeni crvenom bojom.]]
[[Slika:Sieve_of_Eratosthenes_animation.gif|mini|300pxupright=1.3|[[Eratostenovo sito]] do broja 120]]
 
'''Prosti brojevi''' ili '''primbrojevi''' su svi [[prirodni brojevi]] [[djelitelj|djeljivi]]veći od 1 koji su bez [[Modularna aritmetika|ostatka]] [[djelitelj|djeljivi]] samo s [[jedan|brojem 1]] i sami sa sobom, a strogo veći od broja 1. Prirodni brojevi koji su veći od broja 1 akoji nisu prosti brojevi nazivaju se [[složen broj|složenim brojevima]].<ref name=":0">{{Citiranje knjige|title=Uvod u teoriju brojeva|author=Andrej Dujella|authorlink=Andrej Dujella|date=2008.|url=https://web.archive.org/web/20210407155741/https://www.mathos.unios.hr/images/homepages/mirela/UUTB/utblink.pdf|format=PDF|publisher=Prirodoslovno-matematički fakultet|location=Zagreb}}</ref>{{Is|6}} Na primjer, broj 5 je prost broj jer je djeljiv samo s 1 i 5, adok je 6 je složen broj jer se osim što je djeljiv s 1 i 6 dodatno može bitipodijeliti podjeljen si brojevima 2 i 3.<ref>https://sites.google.com/site/obrojevima/Home/1-razred-1/skup-prirodnih-brojeva/djeljivost-u-skupu-n/kriteriji-djeljivosti</ref>
 
== Osnovni teoremi vezani uz strukturu prostih brojeva ==
=== Euklidov teorem ===
Ovdje ćemo metodom kontradikcije dokazati Euklidov teorem koji kaže da prostih brojeva ima [[Beskonačnost|beskonačno]] mnogo. Neka je, dakle, <math>ref Pname=":0" </math> skup svih prostih brojeva, <math> P = \{p_1, p_2, ..., p_n\{Is|9}}. </math>Pretpostavimo Promotrimo broj <math> N = p_1 \cdot p_2 \cdot ... \cdot p_n + 1. </math> Tadada je očito <math> N \equiv 1 \pmod {p_i}, \forall i = \{1, 2, ..., n\}.P </math> No,konačan premaskup [[Osnovni stavak aritmetike|Osnovnom stavku aritmetike]] svaki se broj može zapisati kao umnožak konačno mnogosvih prostih brojeva, što daje kontradikciju.
 
:<math> P = \{p_1, p_2,\dots, p_n\} </math>
 
i promotrimo broj
 
:<math> N = p_1 \cdot p_2 \cdot ... \cdot p_n + 1. </math>
 
Očito je ostatak pri dijeljenju ovog broja svakim od prostih brojeva iz <math> P </math> jednak jedan,
 
:<math> N \equiv 1 \pmod {p_i}, \forall i = \{1, 2, ..., n\} </math>
 
pa <math>N</math> nije djeljiv ni sa jednim od njih. No prema [[Osnovni stavak aritmetike|Osnovnom stavku aritmetike]] svaki bi se broj morao moći zapisati kao umnožak konačno mnogo prostih brojeva,<ref>{{Citiranje knjige|title=Uvod u teoriju brojeva|author=Ivan Matić|date=2013.|url=https://web.archive.org/web/20210407155723/https://www.mathos.unios.hr/images/homepages/mirela/UUTB/uvod_u_teoriju_brojeva.pdf|format=PDF|pages=11|location=Osijek}}</ref> a za ovakav <math>N</math> to ne može biti nijedan broj iz skupa <math> P </math>. Očito postoje prosti brojevi izvan tog skupa, čime se početna tvrdnja dovodi u kontradikciju.
 
=== Prostih brojeva oblika <math> 4n + 3</math> ima beskonačno mnogo ===
Dokažimo sada da prostih brojeva oblika <math> 4n + 3 </math> ima beskonačno mnogo.<ref name=":0" />{{Is|9}}
Prije svega, jasno je da neparni prosti brojevi mogu isključivo biti u obliku <math> 4n + 1 </math> ili <math> 4n + 3. </math> Uočimo da vrijedi <math> (4s + 1)(4t + 1) = 4(4st + s + t) + 1, </math> tj. umnožak dva prosta broja oblika <math> 4n + 1 </math> je i sam tog oblika.
 
Line 16 ⟶ 28:
Konstrirajmo sada neparni broj <math> m = 4p_1p_2 \cdot ... \cdot p_n - 1. </math> Očito <math> m </math> daje ostatak 3 pri dijeljenju s 4 pa barem jedan njegov prosti faktor nije u obliku <math> 4n + 1, </math> odnosno barem je jedan faktor u obliku <math> 4n + 3. </math> Jasno je da niti jedan od <math> p_1, p_2, ..., p_n </math> ne dijeli <math> m </math> jer očito <math> m </math> daje ostatak <math> - 1, </math> tj. <math> p_i - 1, </math> pri dijeljenju s <math> p_i, i =\{1, 2, ..., n\}. </math> To znači da postoji još barem jedan prosti broj oblika <math> 4n + 3 </math> izvan <math> S, </math> kontradikcija.
 
=== Razmak između prostih brojeva ===
Važno svojstvo prostih brojeva je da ne postoji najveći razmak između dva prosta broja.{{Nedostaje izvor}} To je zbog toga što postoji proizvoljno velik skup uzastopnih složenih brojeva između svaka dva prosta broja. Takav skup je primjerice

:<math> S = \{n! + 2, n! + 3, ..., n! + n : n \in \mathbb{N}\}.</math>.{{Pojasniti|zašto?}}
 
Ipak, jasno je da ovo ne dokazuje da postoji beskonačno mnogo parova prostih brojeva <math>p_1, p_2</math> koji su udaljeni za točno <math>k.</math> Tome svjedoči tzv. hipoteza o ''Prostimprostim 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.{{Nedostaje izvor}}
 
Uz to, nije dokazano ni da za svaki <math>k \in \mathbb{N}</math> možemo naći neka dva prosta broja <math>p_1 < p_2 </math> takva da je <math>p_2 - p_1 = k </math>.{{Nedostaje izvor}}
 
==Uloga prostih brojeva==
Line 27 ⟶ 41:
Prosti brojevi služe pri [[Množenje|faktorizaciji]], odnosno rastavljanju složenih brojeva na proste ili '''prim-faktore.'''
 
U gornjem smo odjeljku spomenuli daSvaki se svaki složeni broj može na jedinstven način rastaviti na nekoliko prim-faktora, a ako je broj <math> p </math> prost tada je jedina takva faktorizacija očito <math> p = p \cdot 1 </math>.
 
125|5 34|2
Line 43 ⟶ 57:
Ako mu je zbroj znamenaka djeljiv s 3, onda je taj broj djeljiv s 3.
 
Ako mu je dvoznamenkasti završetak dijeljivdjeljiv sas 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.
Line 51 ⟶ 65:
Ako je zbroj znamenaka nekog broja djeljiv s 9, onda je taj broj djeljiv s 9.
 
NapomenimoVrijede da vrijededakako i obrati svih sedam gore navedenih tvrdnji.
 
== Zanimljivosti ==
Poznata je rečenica velikog [[Švicarska|švicarskog]] [[Matematika|matematičara]] [[Leonhard Euler|Leonharda Eulera]] vezana uz proste brojeve:''<ref>{{Citiranje weba|url=https://www.maa.org/press/periodicals/convergence/quotations/euler-leonhard-1707-1783|title=Euler, Leonhard (1707-1783) {{!}} Mathematical Association of America|work=www.maa.org|accessdate=2021-04-07}}</ref>''<blockquote>''"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."''<ref>https://www.maa.org/press/periodicals/convergence/quotations/euler-leonhard-1707-1783</refblockquote>
 
== Izvori ==
Dobavljeno iz "https://hr.wikipedia.org/wiki/Prosti_broj"