Deljivost celih brojeva

Uvod

Kada su brojevi mali, lako možemo proveriti da li je jedan broj deljiv drugim jednostavnim deljenjem. Ali šta ako je broj ogroman, na primer $7^{100}$ , ili ako treba dokazati da je neki izraz deljiv za svaki ceo broj? Tada direktno računanje više nije moguće.

U ovom poglavlju naučićeš kako se ovakvi problemi rešavaju pomoću pravila deljivosti, ostataka pri deljenju i jednostavnih algebrajskih transformacija.

Sadržaj

Osnovni pojmovi i oznake
Osnovna pravila deljivosti
1. Deljivost algebarskih izraza
- 1.1. Faktorizacija i proizvod uzastopnih brojeva
- 1.2. Analiza slučajeva po ostatku
2. Poslednja cifra stepena
3. Primeri

Osnovni pojmovi i oznake

Skoro svaki zadatak u ovoj lekciji oslanja se na sledeća tri pojma, pa ih vredi imati na jednom mestu.

Deljivost. Kažemo da ceo broj $a$ deli ceo broj $b$ , i pišemo $a \mid b$ , ako postoji ceo broj $q$ takav da je $b = a \cdot q$ . Ceo trik većine dokaza je upravo da izraz zapišemo u obliku $a \cdot q$ za neki ceo $q$ .

Teorema o deljenju sa ostatkom. Za svaki ceo broj $n$ i prirodan broj $d$ postoje jedinstveni celi brojevi $q$ (količnik) i $r$ (ostatak) takvi da je

$n = d q + r, \qquad 0 \le r < d.$ Na primer, pri deljenju sa $3$ ostatak može biti samo $0$ , $1$ ili $2$ , pa svaki ceo broj ima oblik $3k$ , $3k+1$ ili $3k+2$ . Ovo je alat kojim beskonačno mnogo brojeva svodimo na konačno mnogo slučajeva.

Uzajamno prosti brojevi. Brojevi $a$ i $b$ su uzajamno prosti ako je $NZD(a, b) = 1$ , to jest ako nemaju zajednički delilac osim $1$ . Na primer, $NZD(2, 3) = 1$ .

Prost i složen broj. Prirodan broj veći od $1$ je prost ako ima tačno dva delioca ( $1$ i samog sebe). U suprotnom je složen, što znači da se može zapisati kao proizvod dva prirodna broja koja su oba veća od $1$ .

Ako je $a \mid n$ i $b \mid n$ , i pri tome su $a$ i $b$ uzajamno prosti ( $NZD(a, b) = 1$ ), onda je $ab \mid n$ . Ovo pravilo često koristimo da deljivost velikim brojem svedemo na deljivost manjim: na primer, $6 = 2 \cdot 3$ , pa je dovoljno posebno dokazati deljivost sa $2$ i sa $3$ . Uslov uzajamne prostosti je obavezan. Broj $12$ je deljiv i sa $4$ i sa $6$ , ali nije deljiv sa $4 \cdot 6 = 24$ , upravo zato što $4$ i $6$ nisu uzajamno prosti.

Osnovna pravila deljivosti

Pre samih dokaza, korisno je imati na jednom mestu brza pravila kojima proveravamo deljivost broja bez deljenja. Ova pravila se stalno koriste kao gotova činjenica.

Sa 2: poslednja cifra mora biti parna ( $0, 2, 4, 6$ ili $8$ ).
Sa 3: zbir svih cifara broja mora biti deljiv sa $3$ .
Sa 4: poslednje dve cifre grade broj koji je deljiv sa $4$ .
Sa 5: poslednja cifra mora biti $0$ ili $5$ .
Sa 6: broj mora biti deljiv i sa $2$ i sa $3$ istovremeno.
Sa 8: poslednje tri cifre grade broj deljiv sa $8$ .
Sa 9: zbir svih cifara broja mora biti deljiv sa $9$ .
Sa 10: poslednja cifra mora biti $0$ .

1. Deljivost algebarskih izraza

Cilj je dokazati da je neki izraz sa promenljivom deljiv datim brojem za sve cele vrednosti promenljive. Obradićemo dva tipična pristupa.

1.1. Faktorizacija i proizvod uzastopnih brojeva

Prvi potez je gotovo uvek faktorizacija. Ako izraz uspemo da rastavimo na proizvod uzastopnih celih brojeva, dobijamo deljivost besplatno, zahvaljujući sledećem pravilu.

Među bilo koja $k$ uzastopna cela broja, tačno jedan je deljiv sa $k$ . Posebno: među dva uzastopna broja jedan je paran (deljiv sa $2$ ), a među tri uzastopna tačno jedan je deljiv sa $3$ .

Zadatak. Dokazati da je $m^3 - m$ deljivo sa $6$ za svaki ceo broj $m$ .

Rešenje.

Izvlačimo zajednički činilac $m$ :

$m^3 - m = m(m^2 - 1)$

Na izraz u zagradi primenjujemo razliku kvadrata $m^2 - 1 = (m-1)(m+1)$ :

$m(m^2 - 1) = m(m - 1)(m + 1)$

Preuređujemo činioce po veličini. Dobijamo proizvod tri uzastopna cela broja:

$(m - 1)\, m \,(m + 1)$

Rastavljamo delilac na proste činioce. Da bi broj bio deljiv sa $6$ , mora biti deljiv i sa $2$ i sa $3$ :

$6 = 2 \cdot 3$

Među tri uzastopna cela broja bar jedan je paran, pa je proizvod deljiv sa $2$ :

$2 \mid (m - 1)\, m \,(m + 1)$

Među tri uzastopna cela broja tačno jedan je deljiv sa $3$ , pa je proizvod deljiv sa $3$ :

$3 \mid (m - 1)\, m \,(m + 1)$

Pošto je izraz deljiv i sa $2$ i sa $3$ , a ti brojevi su uzajamno prosti ( $NZD(2,3)=1$ ), deljiv je i njihovim proizvodom:

$6 \mid (m^3 - m)$

Time je dokaz završen. $\blacksquare$

Korak koji se najčešće preskače je poslednji: nije dovoljno reći „deljivo je sa $2$ i sa $3$ , dakle sa $6$ ". To zaključivanje je tačno samo zato što su $2$ i $3$ uzajamno prosti, prema pravilu datom u napomeni na početku lekcije.

1.2. Analiza slučajeva po ostatku

Kada faktorizacija ne daje odmah uzastopne brojeve, koristimo teoremu o deljenju sa ostatkom: promenljivu zamenimo svim mogućim oblicima koje može imati, pa proverimo svaki slučaj posebno.

Zadatak. Dokazati da je $n^2 + n$ deljivo sa $2$ za svaki prirodan broj $n$ .

Rešenje.

Izvlačimo zajednički činilac $n$ :

$n^2 + n = n(n + 1)$

Pri deljenju sa $2$ broj $n$ ima ostatak $0$ ili $1$ , pa je $n = 2q$ (paran) ili $n = 2q + 1$ (neparan), gde je $q$ ceo broj. Razmatramo oba slučaja.

Slučaj 1: $n = 2q$ . Zamenom dobijamo:

$n(n + 1) = 2q(2q + 1)$ Proizvod sadrži činilac $2$ , pa je deljiv sa $2$ .

Slučaj 2: $n = 2q + 1$ . Zamenom dobijamo:

$n(n + 1) = (2q + 1)(2q + 2) = 2(2q + 1)(q + 1)$ Iz druge zagrade izvukli smo $2$ , pa je i ovaj proizvod deljiv sa $2$ .

Pošto je u oba slučaja izraz deljiv sa $2$ , tvrđenje važi za svaki prirodan broj $n$ . $\blacksquare$

Ovaj zadatak ima i prečicu: $n(n+1)$ je proizvod dva uzastopna broja, pa je jedan od njih obavezno paran. Analiza slučajeva je opštiji alat i vredi je uvežbati, jer za deljivost sa $5$ (izraz $m^5 - m$ ) prečica ne postoji, a metod slučajeva radi jednako dobro, samo sa pet slučajeva: $m = 5q + r$ za $r \in \{0, 1, 2, 3, 4\}$ .

Najčešća greška u ovom tipu zadatka je izostavljanje nekog slučaja. Ako dokazuješ deljivost sa $3$ , moraš proveriti sva tri oblika ( $3k$ , $3k+1$ , $3k+2$ ); ako sa $5$ , svih pet. Dokaz važi tek kada su svi slučajevi obrađeni, jer izostavljen slučaj znači nedokazano tvrđenje.

2. Poslednja cifra stepena

Kada treba odrediti poslednju cifru ogromnog stepena, na primer $2^{102}$ , taj broj ne treba (niti je moguće) računati u celini. Srećom, to nije ni potrebno: poslednja cifra proizvoda zavisi samo od poslednjih cifara činilaca, pa se pri uzastopnom množenju iste osnove poslednje cifre ponavljaju u ciklusu.

Zbog toga je postupak uvek isti. Ispišemo poslednje cifre prvih nekoliko stepena osnove dok ne uočimo da se ponavljaju; dužina tog ponavljanja je dužina ciklusa. Zatim izložilac podelimo dužinom ciklusa, a dobijeni ostatak nam govori koji je član ciklusa tražena poslednja cifra.

Zadatak. Odrediti poslednju cifru broja $52^{102}$ .

Rešenje.

Poslednja cifra stepena zavisi samo od poslednje cifre osnove. Osnova $52$ se završava cifrom $2$ , pa tražimo poslednju cifru broja $2^{102}$ .

Ispisujemo poslednje cifre prvih nekoliko stepena broja $2$ :

$2^1 = 2, \quad 2^2 = 4, \quad 2^3 = 8, \quad 2^4 = 16, \quad 2^5 = 32$

Poslednje cifre se ponavljaju u ciklusu dužine $4$ : $\; 2, 4, 8, 6$ .

Delimo izložilac dužinom ciklusa i tražimo ostatak:

$102 = 4 \cdot 25 + 2$

Ostatak je $2$ , pa je poslednja cifra ista kao kod drugog člana ciklusa, odnosno kao kod $2^2$ :

$2^2 = 4$

Poslednja cifra broja $52^{102}$ je $\mathbf{4}$ .

Ovu periodičnost pregledno prikazuje tabela poslednjih cifara stepena osnove $2$ . Poslednja kolona pokazuje ostatak izložioca pri deljenju sa $4$ , to jest mesto cifre u ciklusu:

Stepen	Vrednost	Poslednja cifra	Ostatak pri deljenju sa $4$
$2^1$	$2$	$2$	$1$
$2^2$	$4$	$4$	$2$
$2^3$	$8$	$8$	$3$
$2^4$	$16$	$6$	$0$

Ciklus poslednjih cifara je $2, 4, 8, 6$ , a zatim se ponavlja: $2^5$ se opet završava cifrom $2$ , isto kao $2^1$ . Primeti da izložilac deljiv sa $4$ (ostatak $0$ ) odgovara poslednjem članu ciklusa, cifri $6$ .

Kada je ostatak jednak nuli, ne uzima se prvi član ciklusa, nego poslednji. Na primer, za $2^{100}$ je $100 = 4 \cdot 25 + 0$ , pa poslednja cifra odgovara četvrtom članu ciklusa, dakle $6$ , a ne $2$ . Ostatak $0$ znači da se ciklus završio tačno, pa gledamo njegov kraj. Ovo je najčešća greška u ovom tipu zadatka.

Za neke osnove ciklus je kraći, pa se odgovor vidi odmah. Dužina ciklusa zavisi samo od poslednje cifre osnove: cifre $0, 1, 5, 6$ imaju ciklus dužine $1$ (svaki stepen se završava istom cifrom), cifre $4, 9$ ciklus dužine $2$ , a cifre $2, 3, 7, 8$ ciklus dužine $4$ . Tako se, na primer, svaki stepen broja koji se završava na $6$ (poput $376^{543}$ ) ponovo završava cifrom $6$ , a kod cifara $4$ i $9$ dovoljno je pogledati parnost izložioca.

Ista ideja, gledanje ostatka koji osnova daje pri deljenju, koristi se i za dokaze deljivosti stepena. Kada se osnova može zapisati u obliku $5k \pm 1$ , sve zavisi od stepena broja $-1$ .

Zadatak. Dokazati da je $9^{44} + 4^{99}$ deljivo sa $5$ .

Rešenje.

Cilj je izraz zapisati u obliku $5q$ za neki ceo broj $q$ . Osnove $9$ i $4$ zapisujemo preko umnožaka broja $5$ :

$9 = 5 \cdot 2 - 1 \qquad \text{i} \qquad 4 = 5 \cdot 1 - 1$

Obe osnove imaju oblik „umnožak petice manje $1$ ". Pri deljenju sa $5$ ostatak stepena $(5k - 1)^n$ zavisi samo od $(-1)^n$ : ako je $n$ paran, ostatak je $1$ ; ako je neparan, ostatak je $-1$ .

Za prvi sabirak je izložilac $44$ paran, pa je ostatak $(-1)^{44} = 1$ :

$9^{44} = 5a + 1$

Za drugi sabirak je izložilac $99$ neparan, pa je ostatak $(-1)^{99} = -1$ :

$4^{99} = 5b - 1$

Sabiramo dobijene izraze:

$9^{44} + 4^{99} = (5a + 1) + (5b - 1) = 5a + 5b$

Izvlačimo zajednički činilac $5$ :

$9^{44} + 4^{99} = 5(a + b)$

Pošto su $a$ i $b$ celi brojevi, njihov zbir $q = a + b$ je ceo broj, pa je izraz oblika $5q$ :

$5 \mid \left(9^{44} + 4^{99}\right)$

Time je dokaz završen. $\blacksquare$

3. Primeri

Sledeći zadaci pokazuju kako se alati iz prethodnih poglavlja koriste na nešto složenijim primerima.

Kada se u zadatku pojavljuju cifre broja (na primer „broj napisan istim ciframa obrnutim redom"), broj se ne posmatra kao celina, nego se razlaže po mesnim vrednostima.

Zadatak. Dokazati da je zbir bilo kog četvorocifrenog broja i broja napisanog istim ciframa obrnutim redom deljiv sa $11$ .

Rešenje.

Neka je četvorocifreni broj $\overline{abcd}$ , gde su $a, b, c, d$ cifre i $a \neq 0$ . Zapisujemo ga u dekadnom sistemu:

$\overline{abcd} = 1000a + 100b + 10c + d$

Broj napisan obrnutim redom je $\overline{dcba}$ :

$\overline{dcba} = 1000d + 100c + 10b + a$

Sabiramo ova dva broja i grupišemo članove uz iste cifre:

$S = 1001a + 110b + 110c + 1001d$

Primetimo da su i $1001$ i $110$ deljivi sa $11$ :

$1001 = 11 \cdot 91, \qquad 110 = 11 \cdot 10$

Zamenjujemo i izvlačimo činilac $11$ :

$S = 11(91a + 10b + 10c + 91d)$

Izraz u zagradi je ceo broj (jer su $a, b, c, d$ cifre); označimo ga sa $q$ . Tada je $S = 11q$ , pa je:

$11 \mid S$

Time je dokaz završen. $\blacksquare$

Kada je poznat ostatak pri deljenju, deljivost prebacujemo na razliku „broj minus ostatak", a za zajednički delilac više takvih razlika koristimo najveći zajednički delilac (NZD).

Delilac je uvek strogo veći od ostatka. Ako pri deljenju sa $n$ dobijamo ostatak $2$ , onda mora biti $n > 2$ . Ovaj uslov se lako zaboravi, a njime se odbacuju „lažna" rešenja koja bi inače prošla račun.

Zadatak. Pri deljenju brojeva $287$ i $431$ prirodnim brojem $n$ dobijaju se redom ostaci $1$ i $2$ , a pri deljenju broja $231$ brojem $n + 1$ ostatak $3$ . Odrediti sve takve brojeve $n$ .

Rešenje.

Ako $287$ pri deljenju sa $n$ daje ostatak $1$ , onda $n$ deli $287 - 1 = 286$ . Slično, $n$ deli $431 - 2 = 429$ . Pošto su ostaci $1$ i $2$ , mora biti $n > 2$ :

$n \mid 286 \qquad \text{i} \qquad n \mid 429$

Tražimo zajedničke delioce, pa brojeve rastavljamo na proste činioce:

$286 = 2 \cdot 11 \cdot 13, \qquad 429 = 3 \cdot 11 \cdot 13$

Najveći zajednički delilac je proizvod zajedničkih prostih činilaca:

$NZD(286, 429) = 11 \cdot 13 = 143$

Broj $n$ mora biti delilac broja $143$ . Delioci su $1, 11, 13, 143$ , a uz uslov $n > 2$ ostaju:

$n \in \{11, 13, 143\}$

Treći uslov: $231$ pri deljenju sa $n + 1$ daje ostatak $3$ , pa $n + 1$ deli $231 - 3 = 228$ . Proveravamo kandidate:

\begin{aligned} n = 11 &\implies n + 1 = 12, \quad 228 : 12 = 19 \quad (\text{deli se}) \\ n = 13 &\implies n + 1 = 14, \quad 228 = 14 \cdot 16 + 4 \quad (\text{ne deli se}) \\ n = 143 &\implies n + 1 = 144, \quad 228 = 144 \cdot 1 + 84 \quad (\text{ne deli se}) \end{aligned}

Sve uslove ispunjava jedino:

$n = 11$

Celi brojevi

Deljivost celih brojeva

Uvod

Sadržaj

Osnovni pojmovi i oznake

Osnovna pravila deljivosti

1. Deljivost algebarskih izraza

1.1. Faktorizacija i proizvod uzastopnih brojeva

1.2. Analiza slučajeva po ostatku

2. Poslednja cifra stepena

3. Primeri