Djeljivost

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 ${\displaystyle 8\div 4}$ iznosi 2 bez ostatka, dok broj 9 nije deljiv sa 4, zato što ${\displaystyle 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!"

Definicija
Prirodan broj ${\displaystyle a}$  deljiv je prirodnim brojem ${\displaystyle b}$  ako postoji prirodan broj ${\displaystyle m}$  takav da je ${\displaystyle a=mb}$ . Ako je broj ${\displaystyle a}$  deljiv brojem ${\displaystyle b}$  pisaćemo ${\displaystyle 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

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 ${\displaystyle 117^{4}-93^{4}}$  deljiv svim prirodnim brojevima do broja 10 zaključno.
Rešenje
Rastavljanjem na faktore, dobijamo: ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle n^{3}+23n}$  deljiv sa 6.
Rešenje
Transformišimo dati izraz u oblik ${\displaystyle (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 ≤ 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 ${\displaystyle 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 ${\displaystyle a}$  i ${\displaystyle b}$ , jednoznačno su određeni brojevi ${\displaystyle q}$  i ${\displaystyle r}$ , takvi da je ${\displaystyle a=bq+r,\;0\leq r$ 
Dokaz
Postoji bar jedan takav način predstavljanja broja ${\displaystyle a}$ , recimo kada izaberemo ${\displaystyle bq}$  kao najveći sadržalac broja ${\displaystyle b}$  koji nije veći od ${\displaystyle a}$ . Pretpostavimo da postoji još jedan način, da je ${\displaystyle a=bq_{1}+r_{1},\;0\leq r_{1}$  Tada oduzimanjem dobijamo ${\displaystyle b(q-q_{1})+r-r_{1}=0,}$  što znači da ${\displaystyle b|(r-r_{1})}$  (posledica 1a). Kako je ${\displaystyle |r-r_{1}|$  sledi ${\displaystyle r-r_{1}=0,}$  tj. ${\displaystyle r=r_{1}.}$  Zatim da je ${\displaystyle 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 (${\displaystyle 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 ${\displaystyle c_{1}=NZD(a,b)}$  i ${\displaystyle c_{2}=NZD(a,b)}$  tada je ${\displaystyle c_{1}|c_{2}\wedge c_{2}|c_{1}}$  dakle ${\displaystyle c_{1}=c_{2}}$ .

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

${\displaystyle a=q_{1}b+r_{1},\;r_{1}$ 
${\displaystyle b=q_{2}r_{1}+r_{2},\;r_{2}$ 
${\displaystyle r_{1}=q_{3}r_{2}+r_{3},\;r_{3}$ 
...
${\displaystyle r_{k-3}=q_{k-1}r_{k-2}+r_{k-1},\;r_{k-1}$ 
${\displaystyle r_{k-2}=q_{k}r_{k-1}+r_{k},\;r_{k}$ 
${\displaystyle r_{k-1}=q_{k+1}r_{k}+0,\;(r_{k+1}=0).}$ 

Niz ${\displaystyle 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
${\displaystyle NZD(a,b)=r_{k}}$  gde je ${\displaystyle r_{k}}$  poslednji pozitivan ostatak dobijen primenom Euklidovog algoritma na prirodne brojeve ${\displaystyle a,b;\;a>b.}$ 

Dokaz
Dokazaćemo da važe sledeća dva tvrđenja:
(a) ${\displaystyle r_{k}|a,\;r_{k}|b;}$ 
(b) ${\displaystyle d|a\wedge d|b\Rightarrow d|r_{k}.}$ 
(a) Zaista, iz poslednje jednakosti Euklidovog algoritma dobijamo da je ${\displaystyle r_{k}|r_{k-1}.}$  Na osnovu toga i pretposlednje jednakosti, zaključujemo da je ${\displaystyle r_{k}|r_{k-2}.}$  Nastavljajući taj postupak dobija se da je ${\displaystyle r_{k}|r_{k-3},\;r_{k}|r{k-4},\;...,r_{k}|b,\;}$  a onda iz prve jednakosti sledi da je ${\displaystyle 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 ${\displaystyle 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.