Djeljivost
D U teoriji brojeva sredi~snji objekt prou~cavanja su cijeli brojevi. Skup cijelih brojeva se ozna~cava sa Z={0,1,-1,2,-2,....}, i njega ~temo ~cesto smatrati univerzalnim skupom u ovom poglavlju. Pozitivni cijeli brojevi jo~s se zovu prirodni brojevi - skup svih njih ozna~cava se s N={1,2,3,4,....}.
S Cijele brojeve mo~zemo proizvoljno zbrajati, oduzimati i mno~ziti ~ ka~zemo da je Z prsten. No ~sto je s dijeljenjem? Pokazuje se da, iako dva cijela broja ne mo~zemo uvijek podijeliti i dobiti kao rezultat cijeli broj, uvijek ih mo~zemo (ako drugi nije nula) podijeliti s ostatkom. (Dijeljenje negativnim brojem nije naro~cito korisno, a pojednostavljuje definiciju ostatka, pa se ~cesto uzima da je djelitelj prirodan.) Na taj na~cin dobijemo kao rezultat _dva_ broja ~ kvocijent i ostatak.
T (o dijeljenju s ostatkom)
Neka su k i l cijeli brojevi, l>0 . Tada postoje jedinstveni cijeli brojevi q i r , tako da r zadovoljava nejedna~gbu 0<=r<l , te vrijedi k=q*l+r . (A(k,l)@ZxN)(E!(q,r)@Zxl)(k=q*l+r) D Broj q zovemo (cjelobrojni) kvocijent pri dijeljenju k sa l , i ozna~cavamo ga s k div l, dok broj r zovemo ostatak pri dijeljenju k sa l , i ozna~cavamo ga s k mod l.
S Naravno, neke cijele brojeve _mo~zemo_ podijeliti. U tom slu~caju ~te gornji r biti 0 . No taj slu~caj ima smisla i kad je l negativan, ~cak i kad je nula, pa stavimo to u posebnu definiciju.

D Neka su k i l proizvoljni cijeli brojevi. Ka~zemo da l dijeli k (ili da je k djeljiv s l , ali pazite na redoslijed!), i pi~semo l|k , ako postoji cijeli broj m takav da je k=l*m . l|k :<=> (Em@Z)(k=l*m)
P Slijede neki primjeri djeljivosti:

  1. 3|15 , jer postoji cijeli broj 5 takav da je 15=3*5 .
  2. 15(!|)3 , jer ne postoji cijeli broj m takav da je 3=15*m .
  3. -2|4 & 2|-4 (m=-2)
  4. 8|8 & -5|-5 (m=1)
  5. -3|-15 & -15(!|)-3
  6. 4|0 & 0|0 (m=0) - svaki broj dijeli nulu!
  7. 0(!|)4 , jer za svaki m , 0*m=0 , pa ne mo~ze biti 4 . Nula ne dijeli nijedan broj osim nule!
1Z Djeljivost mo~zemo promatrati kao relaciju na Z, |:Z--Z. Ispitajte njena svojstva.
Rj Refleksivnost: vrijedi. Za svaki k , k|k (m=1) .
Simetri~cnost: ne vrijedi. 2|4 , ali 4(!|)2 .
Antisimetri~cnost: ne vrijedi. -3|3 , i 3|-3 , a razli~citi su.
Tranzitivnost: vrijedi. Ako k|l & l|n , to zna~ci l=k*m za neki m , i n=l*p za neki p . No tada je n=l*p=(k*m)*p=k*(m*p) , a m*p je kao produkt cijelih brojeva cijeli broj, pa k|n .

N Vidjeli smo da relacija djeljivosti na Z nije antisimetri~cna. No ako je restringiramo na N , tada jest antisimetri~cna. Zaista, k|l&l|k povla~ci k=ml&l=nk , odnosno mn=1 , ~sto je u prirodnim brojevima mogu~te jedino ako je m=n=1 . Dakle, relacija djeljivosti na N je parcijalni ure~daj. On nije totalan (niti 2 dijeli 3 niti 3 dijeli 2 , dakle 2 i 3 su neusporedivi s obzirom na taj ure~daj), ali je sadr~zan u standardnom totalnom ure~daju prirodnih brojeva <= (ako k|l , tada k<=l ).

2Z Neka su k , l i m prirodni brojevi. Doka~zite:
  1. Ako k|l i k|m , tada k|l+m i DZ k|l-m .
  2. Ako k|l , tada k|l*m .
Vrijede li obrati?

Rj a) l=k*s i m=k*t za neke cijele brojeve s i t . No tada je l+m=k*s+k*t=k*(s+t) , a s+t je kao zbroj cijelih brojeva cijeli broj. Dakle, k|l+m
Obrat ne vrijedi: Kp 2|1+1 , ali 2(!|)1 .
b) Trivijalno l|l*m . Sada tvrdnja slijedi iz tranzitivnosti relacije | .
Obrat tako~der ne vrijedi: 4|2*2 , ali 4(!|)2 .

3Z Doka~zite da je broj n3-n djeljiv s 3 za svaki prirodni n .

Rj n3-n=n(n2-1)=n(n-1)(n+1) . To je produkt tri uzastopna cijela broja, dakle to~cno jedan od faktor~a je uvijek djeljiv s 3 . Onda je i njihov produkt djeljiv s 3 . QED.

DZ Doka~zite da je broj n5-n djeljiv s 5 za svaki prirodni n . Vrijedi li analogna tvrdnja za 7? 9? 11? Za koje prirodne brojeve k op~tenito vrijedi k|nk-n ?

4Z (pismeni, 2002-04-23) Doka~zite: ako a+b|a2+ab+b2 , tada (a+b)2|a4+b4 .

Rj Prvo doka~zimo da a+b dijeli a2 . To je lako, jer sigurno dijeli ab+b2=(a+b)b , pa dijeli i razliku toga i navedenog u zadatku. Sad, ako a+b|a2 , lako se dobije (a+b)2|a4 (samo napi~semo definiciju djeljivosti, i kvadriramo jednakost). Tako~der, zadatak je simetri~can s obzirom na zamjenu a<=>b , pa jednako tako dobivamo da (a+b)2 dijeli i b4 . No tada dijeli i njihov zbroj. QED