Djeljivost

**Deljivost** je algebarska osobina 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 8 \div 4 iznosi 2 bez ostatka, dok broj 9 nije deljiv sa 4, zato što 9 \div 4 iznosi 2 sa ostatkom 1.

Deljivost je centralni pojam teorije prirodnih brojeva (aritmetika). Jedan od najvećih matematičara svih vremena, koji je i danas poznat kao *kralj matematike*, 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 a deljiv je prirodnim brojem b ako postoji prirodan broj m takav da je a=mb. Ako je broj a deljiv brojem b pisaćemo b|a (č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 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" teoriju da bi ustanovili deljivost, jer je u rešavanju zadatka dovoljno elementarno poznavanje matematike, ili je situacija izvan domašaja naše teorije.

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

; 2. Zadatak: Dokazati da je za svaki broj n broj n^3-n deljiv brojem 6.
; Rešenje: *Na primer*, za n = 1, dati broj je nula, deljiv je sa šest; 
: za n = 2, dati broj je 8 - 2 = 6, takođe; 
: za n = 3 imamo 3^3-3=27-3=24, 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 nizu 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 n^3+23n deljiv sa 6.
; Rešenje: Transformišimo dati izraz u oblik (n^3-n)+24n. 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đenja su mnogima jasna i bez dokaza, ali u teoriji brojeva postoje i teža.

#### Algoritam delenja
Sledeća teorema sadrži neke od najvažnijih osobina 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 jednakosti a_1+a_2+...+a_n=b_1+b_2+...+b_n, svi sabirci izuzev jednog deljivi sa c, onda je i taj jedan deljiv sa c.

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

Broj q naziva se *količnik* a broj r *ostatak* pri deljenju a sa b.

Algoritam deljenja se koristi u klasifikaciji brojeva. Na primer, kada b = 2 za broj (a = 2q+1) 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 delitelja. 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 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 c_1=NZD(a,b) i c_2=NZD(a,b) tada je c_1|c_2 \wedge c_2|c_1 dakle c_1=c_2.

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

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 a, b možemo definisati i kao najmanji prirodan broj oblika xa+yb=c;\; x, y \in Z. Pogledajmo na kraju još jednu teoremu koja se često koristi prilikom rešavanja (težih) zadataka 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 a1=NZD(b,r), pa imamo b=y1c1, r = zc1, a=c1(y1q+z), tj. c1 deli a. Dakle NZD(b,r)|NZD(a,b), te je NZD(a,b)=NZD(b,r).

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

; Dokaz: Prvi, odnosno drugi sa leva najmanji zajednički delilac nazovimo c, odnosno d. Kako je d|a_i, \; i=1,2,...,n, dobijamo da c|NZD(a_1,a_2,...,a_{n-1}) i c|a_n. Dakle, c|d. Obratno, kako d|NZD(a_1,a_2,...,a_{n-1}), \; d|a_n to je d|a_i,\;i=1,2,...,n, 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 algoritmu delenja, jednoznačno su određeni brojevi q_i, r_i,\; i \le k+1, takvi da je
: a=q_1b+r_1,\; r_1
: b=q_2r_1+r_2,\; r_2
: r_1=q_3r_2+r_3,\; r_3
: ...
: r_{k-3}=q_{k-1}r_{k-2}+r_{k-1},\; r_{k-1}
: r_{k-2}=q_kr_{k-1}+r_k,\; r_k
: r_{k-1}=q_{k+1}r_k+0,\; (r_{k+1}=0).

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

; Teorema 7: NZD(a,b)=r_k gde je r_k poslednji pozitivan ostatak dobijen primenom Euklidovog algoritma na prirodne brojeve a, b;\; a>b.

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

;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.