Izvorni kod stranice Djeljivost

'''Deljivost''' je algebarska osobina [[cijeli broj|celih brojeva]]. Jedan celi broj je deljiv drugim celim brojem, ako je ostatak delenja jednak nuli. Tako na primer, je broj 8 deljiv sa 4, zato što <math>8 \div 4</math> iznosi 2 bez ostatka, dok broj 9 nije deljiv sa 4, zato što <math>9 \div 4</math> iznosi 2 sa ostatkom 1.

Deljivost je centralni pojam [[teorija brojeva|teorije prirodnih brojeva]] ([[aritmetika]]). Jedan od najvećih matematičara svih vremena, koji je i danas poznat kao ''kralj matematike'', [[Karl Friedrich Gauss|Karl Fridrih Gaus]] (1777-1855), jednom je prilikom rekao: "[[Matematika]] je kraljica nauka, a [[teorija brojeva]] je kraljica matematike." Gaus je možda više nego bilo koji drugi matematičar u istoriji doprineo razvoju aritmetike, one iste za koju je na kraju napisao: "Aritmetika je ipak preteška za mene!" 

== Deljivost ==
; Definicija: Prirodan broj <math>a</math> [[deljenje|deljiv]] je prirodnim brojem <math>b</math> ako postoji prirodan broj <math>m</math> takav da je <math>a=mb</math>. Ako je broj <math>a</math> deljiv brojem <math>b</math> pisaćemo <math>b|a</math> (čita se: "b deli a").

Na primer 3|24 jer je 24 = 3h8; slično je 7|28 jer 28 = 7x4; takođe 10|10 jer je 10 = 10h1. Broj b zovemo ''delitelj'' ili ''faktor'' broja a; broj a zovemo ''sadržalac'', ''višekratnik'', ili ''umnožak'' broja b.

Kažemo da je b ''pravi delitelj'' od a ako b|a i a &ne; b.

==== Jednostavni kriterijumi ====
Postoji nekoliko jednostavnih pravila za proveru deljivosti konkretnih brojeva sa kojima radimo često. 
* Broj je deljiv sa 10, 100, 1000, ... ako su mu jedna, dve, tri, ... poslednje [[cifra|cifre]] nule.
* Broj je deljiv sa 2, 4, 8, ... ako su mu poslednje 1, 2, 3, ... cifre deljive datim brojem.
* Broj je deljiv sa 5, 25, 125, ... ako su mu poslednje 1, 2, 3, ... cifre deljive datim brojem.
* Broj je deljiv sa 3 ili 9 ako mu je zbir cifara deljiv datim brojem.

Na primer, broj 12300 je deljiv sa 100 jer su mu poslednje dve cifre deljive sa 100; broj 12345612345632 je deljiv sa 4 jer su mu poslednje dve cifre deljive sa 4; broj ...7125 je deljiv sa 125 jer zu mu zadnje tri cifre deljive sa 125; broj 5886 je deljiv sa 27 jer mu je zbir cifara deljiv sa 27.

Postoji još nekoliko "jednostavnih" pravila koja ne koristimo dnevno. Zapisani broj, ako je dovoljno dugačak, možemo razdvojiti na klase (grupe uzastopnih cifara) sa jednakim brojem cifara. Brojeći sa leva u desno te klase će se nalaziti na parnim i neparnim pozicijama.
* Broj je deljiv sa 11 kada je razlika između zbira cifara (jednocifrenih klasa) koje stoje na neparnim i onih koje stoje na parnim mestima (gleda se od poslednje cifre) deljiva sa 11. Na primer, broj 8684016 na neparnim mestima ima cifre 6,0,8,8 čiji je zbir 22, a na parnim 1,4,6 čiji je zbir 11. Razlika ovih zbirova je 11, što je deljivo sa 11, pa je početni broj 8684016 deljiv sa 11.
* Broj je deljiv sa 101 kada je razlika zbira dvocifrenih klasa koje u broju stoje na neparnim i parnim mestima (gleda se od poslednje cifre) deljiva sa 101. Na primer, broj 7 96 89 ima zbir klasa na neparnim mestima 89+7=96, a na parnim 96, čija je razlika nula, tj. deljiva je sa 101. Zato je početni broj 79689 deljiv sa 101.
* Broj je deljiv sa 7, 11, 13, 77, 91, 143 ili 1001 kada je razlika između zbira trocifrenih klasa koje u broju stoje na neparnim mestima i zbira trocifrenih klasa koje stoje na parnim mestima (takođe se gleda od poslednje cifre) deljiva datim brojem. Na primer, broj 539 693 385 ima razliku ovih klasa 385-693+539=231, pa je deljiv sa 7, 11 i 77, a nije deljiv sa 13, 91, 143 i 1001.

==== Lakši zadaci ====
U nekim slučajevima ne koristimo "veliku" [[teorija|teoriju]] da bi ustanovili deljivost, jer je u rešavanju zadatka dovoljno elementarno poznavanje [[matematika|matematike]], ili je situacija izvan domašaja naše teorije.

; 1. Zadatak: Dokazati da je broj <math>117^4-93^4</math> deljiv svim prirodnim brojevima do broja 10 zaključno.
; Rešenje: [[Rastavljanje na faktore|Rastavljanjem na faktore]], dobijamo: <math>117^4-93^4=(117^2-93^2)(117^2+93^2)=(117-93)(117+93)(117^2+93^2).</math> 
:Vrednosti prve dve zagrade lako izračunavamo i množimo 24h210=(6h4)h(5h42)=2h3h...h9h10.

; 2. Zadatak: [[Dokaz]]ati da je za svaki broj n broj <math>n^3-n</math> deljiv brojem 6.
; Rešenje: ''Na primer'', za n = 1, dati broj je [[0 (broj)|nula]], deljiv je sa šest; 
: za n = 2, dati broj je 8 - 2 = 6, takođe; 
: za n = 3 imamo <math>3^3-3=27-3=24</math>, a 24 je broj deljiv sa šest. 
: ''U opštem slučaju'', rastavljamo na faktore i dati izraz postaje n(n-1)(n+1). Faktori su tri uzastopna broja n-1, n, n+1. Međutim, u [[niz]]u od tri uzastopna prirodna broja tačno jedan je deljiv sa tri (u nizu od ''k'' uzastopnih brojeva tačno jedan je deljiv sa ''k''). Prema tome, dati izraz je za svako n deljiv sa 3; ali je deljiv i sa 2, jer svaki niz od 3 člana ima podniz od 2 člana. Otuda je dati izraz deljiv sa 6.

; 3. Zadatak: Dokazati da je za svako n izraz <math>n^3+23n</math> deljiv sa 6.
; Rešenje: Transformišimo dati izraz u oblik <math>(n^3-n)+24n</math>. Prvi sabirak, razlika u zagradi, je prema prethodnom zadatku deljiva sa 6, ali je i drugi sabirak, zbog faktora 24 deljiv sa 6. Njihov zbir mora biti deljiv sa 6.
; Provera: za n = 1, izraz ima vrednost 1+23 + 24, dakle deljiv je sa šest;
: za n = 2, izraz daje rezultat 8+46 + 54, deljiv sa šest;
: za n = 3, izraz je 27+23h3=96, tj. 6h16.

Međutim, u opštem slučaju pretpostavljali smo da su tačna sledeća tvrđenja:
* ako je svaki od sabiraka deljiv sa 6, onda je i zbir deljiv sa 6;
* ako je jedan od faktora deljiv sa 6, onda je i proizvod deljiv sa 6.

Ova [[tvrđenje|tvrđenja]] su mnogima jasna i bez dokaza, ali u teoriji brojeva postoje i teža.

==== Algoritam delenja ====
Sledeća [[teorem]]a sadrži neke od najvažnijih osobina [[djeljivost|deljivosti]].

; Teorema 1: Neka su a, b, c proizvoljni (prirodni) brojevi. Tada:
: (a) ako a|b i b|c onda a|c;
: (b) ako a|b, onda je a &le; b;
: (v) ako a|b i a|c, onda, za proizvoljne cele brojeve x, y važi a|(bx+cy);
: (g) ako a|b i b|a, onda je a = b.

; Dokaz: (a) ako je a|b i b|c, onda postoje brojevi m i n takvi da je b = ma, c = nb. To znači da je c = mna, pa a|c.
: (b) Ako a|b, postoji broj m takav da je b = ma. Neposredno sledi b = am &ge; ax1 = a.
: (v) Ako je a|b i a|c, onda postoje brojevi m, n tako da je b = ma, c = na. Otuda, bx + cy = max + nay = a(mx +ny). Dakle, a|(bx+cy).
: (g) Iz pretpostavke a|b, b|a i iz (b) sledi da je a = b.

; Posledica 1: (a) Ako su a, b, c proizvoljni (prirodni) brojevi takvi da je a|b i a|c, tada a|(b+c) i a|(b-c).
: (b) Ako su u [[jednakost]]i <math>a_1+a_2+...+a_n=b_1+b_2+...+b_n,</math> svi sabirci izuzev jednog deljivi sa c, onda je i taj jedan deljiv sa c.

''Algoritam deljenja'', ili [[teorem]]a o deljenju sa ostatkom, koja sledi, je jedna od važnijih u teoriji brojeva:
; Teorema 2: Za date (prirodne!) brojeve <math>a</math> i <math>b</math>, jednoznačno su određeni brojevi <math>q</math> i <math>r</math>, takvi da je <math>a=bq+r,\; 0\le r < b.</math>
; Dokaz: Postoji bar jedan takav način predstavljanja broja <math>a</math>, recimo kada izaberemo <math>bq</math> kao najveći [[sadržalac]] broja <math>b</math> koji nije veći od <math>a</math>. Pretpostavimo da postoji još jedan način, da je <math>a=bq_1+r_1,\; 0 \le r_1 < b.</math> Tada oduzimanjem dobijamo <math>b(q-q_1)+r-r_1=0,</math> što znači da <math>b|(r-r_1)</math> (posledica 1a). Kako je <math>|r-r_1|<b,</math> sledi <math>r-r_1=0,</math> tj. <math>r=r_1.</math> Zatim da je <math>q=q_1.</math>

Broj q naziva se ''količnik'' a broj r ''ostatak'' pri [[deljenje|deljenju]] a sa b.

[[Algoritam]] deljenja se koristi u [[klasifikacija brojeva|klasifikaciji brojeva]]. Na primer, kada b = 2 za broj (<math>a = 2q+1</math>) kažemo da je ''neparan'' ako r = 1, odnosno da je ''paran'' ako r = 0. [[Prost broj]] p je onaj kome su jedini delitelji 1 i p. Za prirodan broj koji nije prost kažemo da je ''složen''.

==== NZD ====
* ''Zajednički delitelj'' brojeva a i b je (prirodan) broj k ako je k|a i k|b.
* ''Najveći zajednički delitelj'' brojeva a i b je najveći od brojeva zajedničkih [[delitelj]]a. Označava se sa (a,b), ili NZD(a,b), ali može i NZD.
* ''Uzajamno prosti'' brojevi a, b su oni za koje je NZD(a,b)=1. Uzajamno [[prost broj|proste brojeve]] nazivamo i ''relativno prosti'' brojevi.

Na primer, NZD(8,15)=1, NZD(4,40)=4, NZD(40,210)=10, NZD(697,816)=17, NZD(1326,7315)=1.

; Teorema 3: Najveći zajednički delitelj dva (prirodna) broja je jedinstven.
; Dokaz: Ako je <math>c_1=NZD(a,b)</math> i <math>c_2=NZD(a,b)</math> tada je <math>c_1|c_2 \wedge c_2|c_1</math> dakle <math>c_1=c_2</math>.

;Teorema 4: Ako je <math>c</math> najveći zajednički delilac prirodnih brojeva <math>a</math> i <math>b</math>, onda postoje [[cijeli broj|celi brojevi]] <math>x</math> i <math>y</math> takvi da je <math>xa+yb=c.</math>
; Dokaz: Posmatrajmo [[skup]] celih [[broj]]eva oblika <math>xa+yb</math>, gde <math>x,y \in \mathbb{Z}.</math> Izaberimo u njemu najmanji prirodan broj, recimo <math>n=xa+yb</math>. 
: Dokažimo da <math>n|a</math> i <math>n|b</math>: 
: Pretpostavimo da <math>n</math> ne deli <math>a</math>. Onda bi postojali takvi brojevi <math>q</math> i <math>r</math> da je <math>r<n, a=nq+r.</math> 
: Pa bi bilo <math>r = a-nq=a-q(xa+yb)=(1-xq)a-yqb</math>, tj. prirodan broj <math>r</math> bio bi manji od <math>n</math> i pripadao bi skupu brojeva <math>xa+yb</math>, što je u kontradikciji sa pretpostavkom da je <math>n</math> najmanji.
: Dokažimo sada da je <math>n</math> najveći zajednički delilac brojeva <math>a</math> i <math>b</math>, tj. da je <math>n = c.</math> Kako je <math>c=NZD(a,b),</math> možemo pisati <math>a=pc, b=qc,</math> pa imamo da je <math>n=xpc+yqc=c(xp+yq).</math> Sledi da <math>c|n,</math> pa <math>c\le n.</math> Zato što je <math>c</math> najveći zajednični delilac, biće <math>c=n,</math> tj. <math>c=xa+yb.</math> 

Na primer, najveći zajednički delioci iz prethodnog primera 
: NZD(8,15)=1 i imamo 2h8-1h15=1; NZD(4,40)=4 i 11h4-1h40=4; (40,210)=40 i -5h40+1h210=10.

''Najmanji zajednički delilac'' brojeva <math>a, b</math> možemo definisati i kao najmanji prirodan broj oblika <math>xa+yb=c;\; x, y \in Z.</math> Pogledajmo na kraju još jednu teoremu koja se često koristi prilikom rešavanja (težih) zadataka [[aritmetika|aritmetike]].

; Teorema 5: '''(a)''' Ako je k>0, onda je NZD(ka,kb)=kNZD(a,b).
: '''(b)''' Ako je a=bq i b &ge; 0, onda je NZD(a,b)=b.
: '''(v)''' Ako q|ab i pri tome su q i b uzajamno prosti brojevi, tj. NZD(b,q)=1, onda q|a.
: '''(g)''' Ako je a=bq+r, onda je NZD(a,b)=NZD(b,r).

; Dokaz: '''(v)''' Pretpostavićemo da je a>0; za a<0 radili bi jednako. Prvo primetimo da NZD(b,q)=1 povlači NZD(ab,q)=NZD(a,q). Naime, broj NZD(ab,q) deli brojeve ab i aq, pa deli i broj NZD(ab,aq)=aNZD(b,q)=a. Kako NZD(ab,q) deli q sledi da NZD(ab,q) da NZD(a,q). Međutim, broj NZD(a,q) deli oba ab i q, pa NZD(a,q) deli NZD(ab,q), dakle NZD(ab,q)=NZD(a,q). Kako iz pretpostavke q|ab proizilazi NZD(ab,q)=q, to iz poslednje dokazane jednakosti izlazi q|a.
: '''(g)''' Neka je c=NZD(a,b). Tada c deli oba broja a i b, pa je a=xc, b=yc, odnosno r =c(x-yq), pa c|r, tj. c je zajednički delilac brojeva b i r. Otuda NZD(a,b) deli NZD(b,r). Stavimo c<sub>1</sub>=NZD(b,r), pa imamo b=y<sub>1</sub>c<sub>1</sub>, r = zc<sub>1</sub>, a=c<sub>1</sub>(y<sub>1</sub>q+z), tj. c<sub>1</sub> deli a. Dakle NZD(b,r)|NZD(a,b), te je NZD(a,b)=NZD(b,r).

; Teorema 6: <math>NZD(a_1,a_2,...,a_n)=NZD(NZD(a_1,a_2,...,a_{n-1}),a_n).</math>

; Dokaz: Prvi, odnosno drugi sa leva najmanji zajednički delilac nazovimo c, odnosno d. Kako je <math>d|a_i, \; i=1,2,...,n,</math> dobijamo da <math>c|NZD(a_1,a_2,...,a_{n-1})</math> i <math>c|a_n</math>. Dakle, c|d. Obratno, kako <math>d|NZD(a_1,a_2,...,a_{n-1}), \; d|a_n</math> to je <math>d|a_i,\;i=1,2,...,n,</math> pa je d|c. Preme tome c|d.

==== Euklidov algoritam ====
''[[Euklidov algoritam]]'' služi za određivanje najvećeg zajedničkog delitelja prirodnih brojeva a > b:

Prema [[algoritam|algoritmu]] delenja, jednoznačno su određeni brojevi <math>q_i, r_i,\; i \le k+1,</math> takvi da je
: <math>a=q_1b+r_1,\; r_1<b;</math>
: <math>b=q_2r_1+r_2,\; r_2<r_1;</math>
: <math>r_1=q_3r_2+r_3,\; r_3<r_2;</math>
: ...
: <math>r_{k-3}=q_{k-1}r_{k-2}+r_{k-1},\; r_{k-1}<r_{k-2}</math>
: <math>r_{k-2}=q_kr_{k-1}+r_k,\; r_k<r_{k-1}</math>
: <math>r_{k-1}=q_{k+1}r_k+0,\; (r_{k+1}=0).</math>

[[Niz]] <math>r_1, r_2, r_3, ..., r_{k-1}, r_k</math> je opadajući niz prirodnih brojeva manjih od b, što znači da gore opisani postupak mora završiti posle konačno mnogo delenja.

; [[Teorem]]a 7: <math>NZD(a,b)=r_k</math> gde je <math>r_k</math> poslednji pozitivan ostatak dobijen primenom Euklidovog algoritma na prirodne brojeve <math>a, b;\; a>b.</math>

; Dokaz: Dokazaćemo da važe sledeća dva tvrđenja:
: (a) <math>r_k|a, \; r_k | b;</math>
: (b) <math>d|a \wedge d|b \Rightarrow d|r_k.</math>
: '''(a)''' Zaista, iz poslednje [[jednakost]]i Euklidovog algoritma dobijamo da je <math>r_k|r_{k-1}.</math> Na osnovu toga i pretposlednje jednakosti, zaključujemo da je <math>r_k|r_{k-2}.</math> Nastavljajući taj postupak dobija se da je <math>r_k|r_{k-3}, \; r_k|r{k-4}, \; ..., r_k|b,\;</math> a onda iz prve jednakosti sledi da je <math>r_k|a.</math> 
: '''(b)''' Neka je d prirodan broj takav da je d|a i d|b. Tada, iz prve jednakosti Euklidovog algoritma dobijamo da je d|r<sub>1</sub>, iz druge da je d|r<sub>2</sub>, ..., i konačno, iz pretposlednje, da je d|r<sub>k</sub>. Time je dokazano (b). Dakle <math>r_k=NZD(a,b).</math>

;Primer: Odredićemo NZD(936,588). Po Euklidovom algoritmu imamo:
:: 936 = 1&middot;588 + 348,
:: 588 = 1&middot;348 + 240,
:: 348 = 1&middot;240 + 108,
:: 240 = 2&middot;108 + 24,
:: 108 = 4&middot;24 + 12,
:: 24 = 2&middot;12.

: Dakle, NZD(936,588)=12.

Na osnovu teoreme 6, zaključujemo da se višestrukom primenom Euklidovog algoritma može dobiti najveći zajednički delitelj više brojeva.

; Reference: Vladimir Mićić, Zoran Kadelburg: "Uvod u teoriju brojeva", Društvo matematičara SR Srbije, Beograd, 1989.
: Ratko Tošić, Vanja Vukoslavčević: "Elementi teorije brojeva", Alef, Novi Sad, 1995.

[[Kategorija:Teorija brojeva]]
[[Kategorija:Prosti brojevi]]