2
1. DJELJIVOST CIJELIH BROJEVA
1.1.
Osnovne osobine
Definicija 1.1
Neka su a i b cijeli brojevi. Ako postoji cio broj m takav da je b = ma, tada
kažemo da je a djelitelj
ili faktor
broja b i da je b sadržilac
ili višekratnik broja a. To zapisujemo
ovako a | b.
Na primer: 3 | 9, 6 | 30, 5 | 0.
Ako a | b, očigledno je i a | (-b), (-a) | b i (-a) | (-b). Zato se, pri proučavanju djeljivosti, najčešće
ograničavamo na nenegativne cijele brojeve.
Definicija 1.2
Broj a nazivamo pravi djelitelj
od b, ako je a | b i a ≠ b.
U sledećoj teoremi date su neke od najvažnijih osobina relacije djeljivosti.
Teorema 1.1 Neka su a, b, c proizvoljni nenegativni cijeli brojevi.
Tada važi:
a) ako je a | b i b | c, tada je a | c;
b) ako je a | b i b ≠ 0, tada je 0 < a ≤ b;
c) ako je a | b i a | c, tada je, za proizvoljne cijele brojeve x i y, a | (bx + cy);
d) ako a | b i b | a, tada je a = b.
Dokaz.
a) Ako je a | b i b | c, tada postoje cijeli brojevi m i n takvi da je b = ma i c = nb. Tada je,
c = nma, a kako je mn cio broj, sledi da je a | c.
b) Ako je a | b, tada postoji nenegativan cio broj m takav da je b = ma. Kako je b > 0, tada
su i a i m pozitivni brojevi, tj. 1 ≤ a i1 ≤ m. Slijedi da je b = am ≥ a·1 = a > 0.
c) Ako je a | b i a | c, tada postoje cijeli brojevi m i n takvi da je b = ma i c = na. Dakle,
bx + cy = max + nay = a (mx + ny). Kako je mx + ny cio broj, to je a | (bx + cy).
d) Pretpostavimo da je a | b i b | a. Ako je b = 0, tada je i a = 0. Ako b > 0 tada iz (b) sledi
a = b. ■
Posljedica 1.1
a) Ako su a, b, c proizvoljni nenegativni cijeli brojevi takvi da je a | b i a | c, tada je a | (b +
c) i a | (b - c).
b) Ako su u jednakosti a
1
+ a
2
+ … + a
n
= b
1
+ b
2
+ … + b
s
, svi sabirci izuzev jednoga
djeljivi sa c, tada je i taj jedan djeljiv sa c. U teoriji brojeva važnu ulogu ima sledeća
teorema jedinstvenosti o dijeljenju sa ostatkom.
Teorema 1.2 (Algoritam djeljivosti)
Neka su a i b nenegativni cijeli brojevi i b ≠ 0. Tada su
jednoznačno određeni nenegativni cijeli brojevi q i r, takvi da je a = bq + r, 0 ≤ r < b.
3
Dokaz.
Zaista, takav jedan način predstavljanja broja a dobija se ako uzmemo da je bq najveći
sadržilac broja b koji nije veći od a. Pretpostavimo da postoji još jedan način za predstavljanje
broja a.
a = bq
1
+ r
1
, 0 ≤ r
1
< b. Tada je 0 = b(q – q
1
) + r – r
1
, odakle slijedi da je b | (r – r
1
). ■
Posljedica 1.1 a
Kako je |r – r
1
| < b, slijedi da je r – r
1
= 0, tj. r = r
1
. Kako je b ≠ 0, slijedi da je i
q = q
1
.
Broj q naziva se količnik, a broj r ostatak pri dijeljenju a sa b. Algoritam dijeljenja se koristi u
klasifikaciji brojeva. Na primjer za b = 2, ako je r = 1 (a = 2q + 1) tada kažemo da je a neparan
broj, a ako je r = 0 (a = 2q), tada je a paran broj. Slična klasifikacija se uspostavlja za b = 3, 4, ...
Pozitivan cio broj p veći od 1 je prost ako su mu jedini pozitivni djelitelji brojevi 1 i p. Za
pozitivan cio broj veći od 1 koji nije prost, kažemo da je složen. Svaki složen broj n, ima
djelitelje različite od 1 i n.
1.2.
Najveći zajednički djelilac
Definicija 1.3
Neka su a i b nenegativni cijeli brojevi takvi da je bar jedan veći od 0. Za broj k
kažemo da je zajednički djelitelj
brojeva a i b, ako je k | a i k | b.
Definicija 1.4
Najveći pozitivan cio broj koji je djelitelj i od a i od b, naziva se najveći zajednički
djelitelj brojeva a i b. Označavamo ga sa NZD (a, b) ili samo (a, b). On uvek postoji, što se lako
dokazuje, polazeći od principa dobrog uređenja.
Na primjer: NZD (4, 16) = 4, NZD (0, 5) = 5, NZD (30, 50) = 10, NZD (8, 15) = 1.
Da bismo dokazali da je d = NZD (a, b), treba dokazati tačnost sledećeg tvrđenja:
(i)
d | a i d | b
(ii)
ako k | a i k | b, tada je k | d.
Teorema 1.3
Najveći zajednički djelitelj dva cijela broja, od kojih je
bar jedan različit od 0, je
jedinstven.
5
Teorema 1.5
NZD (a, b) = r
k
gde je r
k
poslednji pozitivan ostatak dobijen primjenom Euklidovog
algoritma na prirodne brojeve a i b, a > b.
Dokaz.
Dokažimo da važe sledeća dva tvrđenja:
(i)
rk | a i rk | b
(ii)
ako je d | a i d | b, tada je d | rk.
Iz Euklidovog algoritma dobijamo da je r
k
| r
k-1
. Na osnovu toga i poslednje jednakosti
zaključujemo da je r
k
| r
k-2
. Nastavljajući taj postupak dobije se da je r
k
| r
k-3
, r
k
| r
k-4
,…, r
k
| b, a
onda iz prve jednakosti slijedi da je r
k
| a. Dakle uslov (i) je zadovoljen. Neka je d prirodan broj
takav da je d | a i d | b. Tada iz prve jednakosti Euklidovog algoritma dobijamo da je d | r
1
, iz
druge da je d | r
2
,…, i konačno iz pretposlednje da je d | r
k
. Time je dokazano da važi (ii). Dakle,
rk = NZD (a, b). ■
Primer 1.1
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. Δ
Definicija 1.5
Neka su a
1
, a
2
, …, a
n
nenegativni cijeli brojevi, pri čemu je bar jedan različit od 0.
Najveći pozitivan cio broj d, koji je djelitelj svih tih brojeva se naziva najveći zajednički djelitelj
za brojeve a
1
, a
2
,…, a
n
, a obilježavamo ga sa NZD (a
1
, a
2
,…, a
n
).
Na primjer, NZD (21, 12, 30) = 3 .
Da bismo dokazali da je NZD (a
1
, a
2
,… , a
n
) dovoljno je dokazati:
(i)
d | a
i
, za i = 1, 2 ,… , n;
(ii)
ako je r|a
i
, za i = 1, 2, … , n tada je r | d.
Teorema 1.6
Ako su a
1
, a
2
, …, a
n
pozitivni cijeli brojevi, n ≥ 3, tada je NZD (a
1
, a
2
, …, a
n
) = NZD
(NZD (a
1
, a
2
, … , a
n-1
), a
n
).
