Sadržaj

• Koraci
• Metoda 1 od 2: Algoritam razdjelnika
• Metoda 2 od 2: Glavni čimbenici
• Savjeti

Najveći zajednički djelitelj (GCD) dvaju cijelih brojeva najveći je cijeli broj koji dijeli svaki od tih brojeva. Na primjer, gcd za 20 i 16 je 4 (i 16 i 20 imaju velike djelitelje, ali nisu uobičajeni - na primjer, 8 je djelitelj 16, ali ne i djelitelj 20). Postoji jednostavna i sustavna metoda za pronalaženje GCD -a, nazvana "Euklidov algoritam". Ovaj članak će vam pokazati kako pronaći najveći zajednički djelitelj dva cijela broja.

Koraci

Metoda 1 od 2: Algoritam razdjelnika

1. 1 Izostavite sve znakove minus.
2. 2 Naučite terminologiju: pri dijeljenju 32 sa 5,
   • 32 - dividenda
   • 5 - djelitelj
   • 6 - privatno
   • 2 - ostatak
3. 3 Odredi veći broj. Bit će djeljiv, a manji broj bit će djelitelj.
4. 4 Zapišite sljedeći algoritam: (dividenda) = (djelitelj) * (količnik) + (ostatak)
5. 5 Na mjesto dividende stavite veći broj, a na mjesto djelitelja manji broj.
6. 6 Odredi koliko je puta veći broj podijeljen s manjim, a rezultat upiši umjesto količnika.
7. 7 Pronađite ostatak i upišite ga na odgovarajuće mjesto u algoritmu.
8. 8 Ponovo napišite algoritam, ali (A) napišite prethodni djelitelj kao novu dividendu, a (B) prethodni ostatak kao novi djelitelj.
9. 9 Ponavljajte prethodni korak dok ostatak ne bude 0.
10. 10 Posljednji djelitelj bit će najveći zajednički djelitelj (GCD).
11. 11 Na primjer, pronađimo GCD za 108 i 30:
12. 12 Uočite kako brojevi 30 i 18 iz prvog retka tvore drugi redak. Zatim 18 i 12 tvore treći red, a 12 i 6 tvore četvrti red. Više od 3, 1, 1 i 2 se ne koriste. Oni predstavljaju koliko je puta dividenda djeljiva s djeliteljem i stoga su jedinstveni za svaki redak.

Metoda 2 od 2: Glavni čimbenici

1. 1 Izostavite sve znakove minus.
2. 2 Pronađi proste činitelje brojeva. Predstavite ih kako je prikazano na slici.
   • Na primjer, za 24 i 18:
     • 24-2 x 2 x 2 x 3
     • 18-2 x 3 x 3
   • Na primjer, za 50 i 35:
     • 50-2 x 5 x 5
     • 35-5 x 7
3. 3 Pronađite zajedničke osnovne faktore.
   • Na primjer, za 24 i 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • Na primjer, za 50 i 35:
     • 50 - 2 x 5 x 5
     • 35- 5 x 7
4. 4 Pomnožite zajedničke proste faktore.
   • Za 24 i 18, pomnožite 2 i 3 i dobiti 6... 6 je najveći zajednički nazivnik od 24 i 18.
   • Nema se što pomnožiti za 50 i 35. 5 Jedini je zajednički osnovni faktor, a to je GCD.
5. 5 Napravljeno!

Savjeti

• Jedan od načina da to napišete je: dividenda> mod razdjelnik> = ostatak; GCD (a, b) = b ako je mod b = 0, a gcd (a, b) = gcd (b, mod b) inače.
• Kao primjer, pronađimo GCD (-77,91). Prvo upotrijebite 77 umjesto -77: GCD (-77,91) se pretvara u GCD (77,91). 77 je manji od 91, pa ih moramo zamijeniti, ali razmislite kako algoritam radi ako to ne učinimo. Prilikom izračuna 77 mod 91 dobivamo 77 (77 = 91 x 0 + 77). Budući da to nije nula, razmatramo situaciju (b, a mod b), odnosno GCD (77,91) = GCD (91,77). 91 mod 77 = 14 (14 je ostatak). Nije nula pa GCD (91,77) postaje GCD (77,14). 77 mod 14 = 7. Ovo nije nula pa GCD (77.14) postaje GCD (14.7). 14 mod 7 = 0 (budući da je 14/7 = 2 bez ostatka). Odgovor: GCD (-77,91) = 7.
• Opisana metoda vrlo je korisna za pojednostavljivanje razlomka. U gornjem primjeru: -77/91 = -11/13, budući da je 7 najveći zajednički nazivnik od -77 i 91.
• Ako su a i b jednaki nuli, tada je bilo koji broj različit od nule njihov djelitelj, pa u ovom slučaju ne postoji GCD (matematičari jednostavno vjeruju da je najveći zajednički djelitelj 0 i 0 0).