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 uredi

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 ≠ b.

Jednostavni kriterijumi uredi

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 uredi

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 uredi

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 ≤ 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 ≥ 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\leq r<b.$
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\leq r_{1}<b.$ 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}|<b,$ 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 uredi

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<n,a=nq+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\leq 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 ≥ 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₁=NZD(b,r), pa imamo b=y₁c₁, r = zc₁, a=c₁(y₁q+z), tj. c₁ 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 uredi

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\leq k+1,$ takvi da je

a=q_{1}b+r_{1},\;r_{1}<b;

b=q_{2}r_{1}+r_{2},\;r_{2}<r_{1};

r_{1}=q_{3}r_{2}+r_{3},\;r_{3}<r_{2};

...

r_{k-3}=q_{k-1}r_{k-2}+r_{k-1},\;r_{k-1}<r_{k-2}

r_{k-2}=q_{k}r_{k-1}+r_{k},\;r_{k}<r_{k-1}

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|r₁, iz druge da je d|r₂, ..., i konačno, iz pretposlednje, da je d|r_k. Time je dokazano (b). Dakle $r_{k}=NZD(a,b).$

Primer

Odredićemo NZD(936,588). Po Euklidovom algoritmu imamo:

936 = 1·588 + 348,

588 = 1·348 + 240,

348 = 1·240 + 108,

240 = 2·108 + 24,

108 = 4·24 + 12,

24 = 2·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.