Prosti brojevi
D Za prirodan broj n@N\.{1} ka~zemo da je prost (ili primbroj) ako su mu jedini prirodni djelitelji 1 i n : n@N =>: prost(n) :<=> (Ak@N)(k|n => k=1Vk=n) Skup primbrojeva ozna~cava se s P.

Slo~zen je (prirodan broj koji nije 1 ) ako nije prost. Primijetimo, broj 1 nije ni prost ni slo~zen!
P Primbrojevi: 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,.... .
Slo~zeni brojevi: 4,6,8,9,10,12,14,15,16,18,20,21,22,24,25,26,27,28,30,.... .

5aZ Doka~zite da svaki prirodan broj strogo ve~ti od 1 ima bar jedan prost faktor (prirodni djelitelj). D:) (Ak@N\.{1})(Ep@P)(p|k)

Rj Pretpostavimo suprotno, da postoji prirodan broj ve~ti od 1 , koji nema nijednog prostog faktora. Neka je m najmanji takav. To zna~ci da je m prirodan broj, nije 1 , nema nijednog prostog faktora (svaki "faktor" je ili 1 ili slo~zen), te da svaki broj strogo izme~du 1 i m ima bar jedan prost faktor.
m je prirodan broj koji nije 1 , dakle ili je prost ili je slo~zen. Pretpostavka da je prost vodi na kontradikciju - m je tada sam svoj prost faktor; a pretpostavka da je slo~zen vodi na ~cinjenicu da postoji faktor k|m , koji nije ni 1 ni m . No u prirodnim brojevima k|m povla~ci k<=m , pa je k prirodan broj strogo izme~du 1 i m . Po gornjoj pretpostavci, k ima prost faktor - postoji p@P takav da p|k . No tranzitivnost sad povla~ci p|m , dakle m ima prost faktor p , ~sto je kontradikcija. Jedino je dakle mogu~te da takav m ne postoji, pa zaista svaki prirodan broj osim broja 1 ima bar jedan prost faktor.

5bZ Doka~zite da se svaki slo~zen broj mo~ze zapisati kao produkt dva ili vi~se prostih brojeva. Prosti brojevi se mogu onda shvatiti kao "produkt jednog prostog broja", a broj 1 se mo~ze shvatiti kao "produkt nula prostih brojeva". Na taj na~cin, svaki prirodni broj je produkt prostih brojeva. Svi su oni njegovi faktori, pa ka~zemo da smo ga rastavili na proste faktore.

Rj Na vrlo sli~can na~cin, i koriste~ti prethodni zadatak. Pretpostavimo suprotno - da postoji slo~zen broj koji nije produkt prostih. Neka je m najmanji takav. To zna~ci da je m slo~zen broj, koji nije produkt prostih, te da su svi slo~zeni brojevi manji od m produkti prostih.
m je slo~zen broj, dakle nije 1 . Po zadatku 5a , m ima prost faktor p . Ozna~cimo k:=m/p . To je prirodan broj koji je strogo manji od m ( p je prost, dakle bar 2 ).
Ako je k prost, m=k*p je produkt prostih brojeva. Ako k nije prost, onda je slo~zen (nije 1 , jer m(!=)p -- m je slo~zen a p je prost), pa je produkt prostih. Ako na taj produkt prostih na kraju stavimo jo~s p , dobit ~temo m kao produkt prostih brojeva. To je kontradikcija, dakle takav m ne postoji. QED

N Koristili smo va~zno svojstvo skupa N - od prirodnih brojeva s nekim svojstvom, ako ih uop~te ima, uvijek postoji najmanji. Primijetimo da npr. skupovi Z i Q+ nemaju to svojstvo. To ("metoda najmanjeg kontraprimjera", kako je kori~stena ovdje) nam omogu~tuje efikasno dokazivanje mnogih tvrdnji vezanih uz prirodne brojeve, o ~cemu ~te biti vi~se govora kasnije.

N Tvrdnja zadatka mo~ze se i poja~cati - ne samo da postoji rastav, nego je on jedinstven (do na poredak faktor~a). To je slavni Osnovni Teorem Aritmetike, ~ciji dokaz se mo~ze na~ti u knjizi EM2 .

6Z Doka~zite da je skup P beskona~can.

Rj Opet, pretpostavimo suprotno - da ima samo kona~cno mnogo primbrojeva, i neka su to P={p1,p2,...,pn}. Pogledajmo sljedbenik njihovog umno~ska: m:=p1*p2*...*pn+1. Taj prirodni broj je o~cito strogo ve~ti od 1 (~cak i da je P=0 , produkt nula prostih brojeva je 1 , pa je m=2 ), dakle (po zadatku 5a ) ima prost faktor. No svi prosti brojevi su popisani gore, dakle taj prost faktor je jedan od njih - BSOMP da je to p1 . Sada p1 dijeli m , a dijeli i m-1 (jer je to produkt svih prostih brojeva), pa dijeli i njihovu razliku: p1|1 . To bi zna~cilo p1=1 , a to je nemogu~te jer 1 nije prost broj. Dakle, po~cetna pretpostavka je kriva, odnosno postoji beskona~cno mnogo prostih brojeva. QED

N To je dokaz poznat jo~s od Euklida. Zanimljivo je to da Stari Grci nisu priznavali beskona~cnost kao legitimni matemati~cki pojam, pa je Euklid zapravo pokazao (vlastitim rije~cima) da "prostih brojeva ima vi~se od bilo koje predlo~zene koli~cine prostih brojeva". I dokaz zaista tako po~cinje: "neka je p1,...,pn bilo koja predlo~zena koli~cina prostih brojeva...". Neka, bar je metoda kontradikcije bila vrlo prirodna stvar. ;-)

DZ ~Cemu komplikacija sa zadatkom 5a , i prostim faktorom od m ? Nije li ve~t m prost? Zaista,

  1. 'P'=0 => m=1+1=2@P .
  2. 'P'={2} => m=2+1=3@P .
  3. 'P'={2,3} => m=2*3+1=7@P . ...
Doka~zite da to vrijedi i op~tenito, ili na~dite kontraprimjer.
7Z (pismeni, 2001-09-21) Neka je m umno~zak prvih 100 primbrojeva. Odredite ostatak pri dijeljenju broja m s a)10 , b)4 .

Rj a) Odrediti ostatak pri dijeljenju s 10 isto je ~sto i odrediti zadnju znamenku (za odre~divanje predzadnje, mo~ze poslu~ziti Perl), u ovom slu~caju broja m . No budu~ti da je prvi primbroj jednak 2 , a tre~ti je 5 , o~cito oba ulaze u produkt, pa je m djeljiv s 10 , odnosno zadnja znamenka mu je 0 .
b) 2 je jedini paran primbroj - svi ostali parni brojevi su djeljivi njime, pa nisu prosti. Dakle, ostalih 99 brojeva u rastavu m na proste faktore, su neparni, pa je i njihov produkt neparan, odnosno oblika 2k+1 . Sada je m taj produkt pomno~zen jo~s s 2 , dakle m=2(2k+1)=4k+2 , odnosno m mod 4 = 2.