Najveći zajednički delilac — koliko najviše jednakih paketića može da se napravi?
Najveći zajednički delilac NZD(a, b) kroz deljenje na jednake delove, NZD preko prostih činilaca, NZD dva i tri broja uz uspravnu crtu, Euklidov algoritam (NZD(a, b) = NZD(b, r)), zajednički delioci kao presek skupova delilaca, ako a | b onda NZD(a, b) = a, uzajamno prosti brojevi (NZD = 1, ne moraju biti prosti).
Video
Pojmovi
- Minini paketići
- Ako Mina napravi 5 paketića, u svakom je 6 lizalica i 9 bombona — ništa ne ostaje. Može i 3 paketića, ali ne može 6, jer se 45 ne deli sa 6. Broj paketića mora da deli i 30 i 45. Najveći broj koji deli oba je 15: tada u svakom paketiću budu 2 lizalice i 3 bombone. Taj broj zovemo najveći zajednički delilac i pišemo $\mathrm{NZD}(30, 45) = 15$.
- NZD preko prostih činilaca
- Rastavimo brojeve: $30 = 2 \cdot 3 \cdot 5$ i $45 = 3^2 \cdot 5$. Delilac oba broja može da ima samo proste činioce koji su zajednički, i svaki najviše onoliko puta koliko ga ima manje. Zajednički su 3 i 5, pa je $\mathrm{NZD}(30, 45) = 3 \cdot 5 = 15$. Isto radi i za veće brojeve: $84 = 2^2 \cdot 3 \cdot 7$, $126 = 2 \cdot 3^2 \cdot 7$, pa je NZD jednak $2 \cdot 3 \cdot 7 = 42$.
- NZD uz uspravnu crtu
- Brojeve napišemo u red levo od crte. Desno upišemo prost broj koji deli sve njih, a ispod svakog broja njegov količnik. Ponavljamo dok preostali brojevi ne postanu takvi da ih nijedan broj veći od 1 ne deli sve zajedno. NZD je proizvod brojeva desno od crte. Za 48 i 120: delimo sa 2 (24 i 60), sa 2 (12 i 30), sa 2 (6 i 15), sa 3 (2 i 5); zato je $\mathrm{NZD}(48, 120) = 2 \cdot 2 \cdot 2 \cdot 3 = 24$. Kod tri broja stajemo kad sva tri zajedno nemaju zajednički delilac veći od 1 — makar neka dva od njih i imala.
- Euklidov algoritam
- Za dva velika broja postoji brži put, star više od dve hiljade godina i nazvan po Euklidu: uzastopno deljenje sa ostatkom. Veći broj podelimo manjim; zatim manji broj podelimo dobijenim ostatkom; pa taj ostatak novim ostatkom … sve dok ostatak ne bude 0. Poslednji ostatak koji nije nula je NZD — jer ako je $a = b \cdot q + r$, brojevi $a$ i $b$ imaju iste zajedničke delioce kao $b$ i $r$. Za 315 i 84: $315 = 84 \cdot 3 + 63$, $84 = 63 \cdot 1 + 21$, $63 = 21 \cdot 3 + 0$, pa je $\mathrm{NZD}(315, 84) = 21$.
- Svi zajednički delioci
- Zajednički delioci brojeva 30 i 45 su 1, 3, 5 i 15 — to su baš svi delioci broja 15. Ako napravimo skup delilaca jednog i skup delilaca drugog broja, zajednički delioci su elementi koji su u oba skupa, tj. njihov presek. Svaki zajednički delilac deli i NZD. A kad jedan broj deli drugi, NZD je baš manji broj: $\mathrm{NZD}(9, 45) = 9$.
- Uzajamno prosti brojevi
- Ako je jedini zajednički delilac dva broja broj 1, tj. $\mathrm{NZD}(a, b) = 1$, brojevi su uzajamno prosti — nemaju nijedan zajednički prost činilac. Takvi su 8 i 15: $8 = 2^3$, $15 = 3 \cdot 5$. Pazi: uzajamno prosti brojevi ne moraju sami biti prosti — 8 i 15 su složeni. Dva različita prosta broja su uvek uzajamno prosta.
Formule
| Oznaka | Šta znači | Jedinica |
|---|---|---|
| $a, b$ | prirodni brojevi | — |
Najveći broj koji deli i a i b. Ako a | b, onda je NZD(a, b) = a.
| Oznaka | Šta znači | Jedinica |
|---|---|---|
| $a, b$ | uzajamno prosti brojevi | — |
Nemaju zajednički prost činilac.
| Oznaka | Šta znači | Jedinica |
|---|---|---|
| $q$ | količnik | — |
| $r$ | ostatak, 0 ≤ r < b | — |
Poslednji ostatak različit od nule je NZD.
Pitanja
Pitanje 1 od 10
1. Šta je zajednički delilac brojeva a i b?
2. Koliko je NZD(12, 18)?
3. Šta znači da su dva broja uzajamno prosta?
4. Koji par brojeva je uzajamno prost?
5. Koliko je NZD(13, 52)?
6. Koji je jedini zajednički delilac svih prirodnih brojeva?
7. Kada se završava Euklidov algoritam?
8. Šta je NZD u Euklidovom algoritmu?
9. Da li dva složena broja mogu biti uzajamno prosta?
10. Koliko je NZD(2 · 3 · 7, 3 · 5 · 7)?
Rešeni zadaci
Voćar ima 42 sadnice jabuke i 56 sadnica kruške. Hoće da ih posadi u što više jednakih redova (u svakom redu isto jabuka i isto krušaka), da nijedna sadnica ne ostane. Koliko redova i šta je u svakom?
-
$42 = 2 \cdot 3 \cdot 7,\quad 56 = 2^3 \cdot 7$Zajednički prosti činioci su 2 i 7.
-
$\mathrm{NZD}(42, 56) = 2 \cdot 7 = 14$Broj redova mora deliti oba broja; najveći takav je NZD.
-
$42 : 14 = 3,\quad 56 : 14 = 4$Sadnice u jednom redu.
Odredi NZD(90, 150, 210) deljenjem uz uspravnu crtu.
-
Sva tri broja delimo sa 2: 45, 75, 105.2 deli sva tri.
-
Sa 3: 15, 25, 35. Sa 5: 3, 5, 7.3, 5 i 7 su uzajamno prosti — stajemo.
-
$\mathrm{NZD} = 2 \cdot 3 \cdot 5 = 30$Proizvod brojeva desno od crte.
Euklidovim algoritmom odredi NZD(391, 299).
-
$391 = 299 \cdot 1 + 92$Veći delimo manjim.
-
$299 = 92 \cdot 3 + 23$Manji delimo ostatkom.
-
$92 = 23 \cdot 4 + 0$Ostatak je 0 — stajemo.
Test
Kod računskih zadataka reši u svesci i upiši rezultat (decimalni broj sa zarezom, npr. 2,5), a kod ostalih izaberi tačan odgovor.
Jovan ima 64 kiflice i 112 mandarina. Hoće da napravi što više jednakih kesica tako da ništa ne ostane. Koliko najviše kesica može da napravi?
Odredi NZD(140, 130). Možeš da koristiš Euklidov algoritam. (Ako su brojevi uzajamno prosti, odgovor je 1.)
Koji od ovih parova brojeva NIJE uzajamno prost?
Ako je NZD(a, b) = 12, koji broj sigurno deli i a i b?
Koliko je NZD(36, 60, 84)?
Bravo, čas je završen!
Želiš sertifikat? Napravi besplatan nalog, pa uradi test još jednom (treba bar 3 od 5 tačno). Rezultati se tada čuvaju, a sertifikat možeš da odštampaš ili podeliš.
Napravi besplatan nalogPohvali se i pozovi drugara:
Sledeći čas: 20. Najmanji zajednički sadržalac — kada će dva autobusa ponovo krenuti zajedno?