Djeljivost
D U teoriji brojeva središnji objekt proučavanja su cijeli brojevi. Skup cijelih brojeva se označava sa Z={0,1,-1,2,-2,....}, i njega ćemo često smatrati univerzalnim skupom u ovom poglavlju. Pozitivni cijeli brojevi još se zovu prirodni brojevi - skup svih njih označava se s N={1,2,3,4,....}.
S Cijele brojeve možemo proizvoljno zbrajati, oduzimati i množiti – kažemo da je Z prsten. No što je s dijeljenjem? Pokazuje se da, iako dva cijela broja ne možemo uvijek podijeliti i dobiti kao rezultat cijeli broj, uvijek ih možemo (ako drugi nije nula) podijeliti s ostatkom. (Dijeljenje negativnim brojem nije naročito korisno, a pojednostavljuje definiciju ostatka, pa se često uzima da je djelitelj prirodan.) Na taj način 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 nejednadžbu 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čavamo ga s k div l, dok broj r zovemo ostatak pri dijeljenju k sa l , i označavamo ga s k mod l.
S Naravno, neke cijele brojeve _možemo_ podijeliti. U tom slučaju će gornji r biti 0 . No taj slučaj ima smisla i kad je l negativan, čak i kad je nula, pa stavimo to u posebnu definiciju.

D Neka su k i l proizvoljni cijeli brojevi. Kažemo da l dijeli k (ili da je k djeljiv s l , ali pazite na redoslijed!), i pišemo 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že biti 4 . Nula ne dijeli nijedan broj osim nule!

1Z Djeljivost možemo promatrati kao relaciju na Z, |:Z--Z. Ispitajte njena svojstva.
Rj Refleksivnost: vrijedi. Za svaki k , k|k (m=1) .
Simetričnost: ne vrijedi. 2|4 , ali 4(!|)2 .
Antisimetričnost: ne vrijedi. -3|3 , i 3|-3 , a različiti su.
Tranzitivnost: vrijedi. Ako k|l & l|n , to znači 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čna. No ako je restringiramo na N , tada jest antisimetrična. Zaista, k|l&l|k povlači k=ml&l=nk , odnosno mn=1 , što je u prirodnim brojevima moguće jedino ako je m=n=1 . Dakle, relacija djeljivosti na N je parcijalni uređaj. On nije totalan (niti 2 dijeli 3 niti 3 dijeli 2 , dakle 2 i 3 su neusporedivi s obzirom na taj uređaj), ali je sadržan u standardnom totalnom uređaju prirodnih brojeva <= (ako k|l , tada k<=l ).


2Z Neka su k , l i m prirodni brojevi. Dokažite:
  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đer ne vrijedi: 4|2*2 , ali 4(!|)2 .


3Z Dokažite 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čno jedan od faktorā je uvijek djeljiv s 3 . Onda je i njihov produkt djeljiv s 3 . QED.

DZ Dokažite 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ćenito vrijedi k|nk-n ?


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

Rj Prvo dokažimo 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šemo definiciju djeljivosti, i kvadriramo jednakost). Također, zadatak je simetričan s obzirom na zamjenu a<=>b , pa jednako tako dobivamo da (a+b)2 dijeli i b4 . No tada dijeli i njihov zbroj. QED