Obsah

• Kroky
• Metóda 1 z 2: Algoritmus rozdeľovača
• Metóda 2 z 2: Hlavné faktory
• Tipy

Najväčší spoločný deliteľ (GCD) dvoch celých čísel je najväčšie celé číslo, ktoré rozdeľuje každé z týchto čísel. Napríklad gcd pre 20 a 16 je 4 (16 aj 20 majú veľké delitele, ale nie sú bežné - napríklad 8 je deliteľ 16, ale nie deliteľ 20). Na nájdenie GCD existuje jednoduchá a systematická metóda, ktorá sa nazýva „Euclidov algoritmus“. Tento článok vám ukáže, ako nájsť najväčšieho spoločného deliteľa dvoch celých čísel.

Kroky

Metóda 1 z 2: Algoritmus rozdeľovača

1. 1 Vynechajte všetky znamienka mínus.
2. 2 Naučte sa terminológiu: pri delení 32 číslom 5,
   • 32 - dividenda
   • 5 - deliteľ
   • 6 - súkromný
   • 2 - zvyšok
3. 3 Určte väčšie z čísel. Bude deliteľné a menšie číslo bude deliteľ.
4. 4 Zapíšte si nasledujúci algoritmus: (dividenda) = (deliteľ) * (kvocient) + (zvyšok)
5. 5 Väčšie číslo dajte na miesto dividendy a menšie číslo na miesto deliteľa.
6. 6 Zistite, koľkokrát je väčšie číslo delené menším a napíšte výsledok namiesto kvocientu.
7. 7 Nájdite zvyšok a napíšte ho na vhodné miesto v algoritme.
8. 8 Algoritmus napíšte znova, ale (A) napíšte predchádzajúci deliteľ ako novú dividendu a (B) predchádzajúci zvyšok ako nový deliteľ.
9. 9 Opakujte predchádzajúci krok, kým zvyšok nie je 0.
10. 10 Posledný deliteľ bude najväčší spoločný deliteľ (GCD).
11. 11 Nájdeme napríklad GCD pre 108 a 30:
12. 12 Všimnite si, ako čísla 30 a 18 z prvého riadku tvoria druhý riadok. Potom 18 a 12 tvoria tretí rad a 12 a 6 tvoria štvrtý rad. Násobky 3, 1, 1 a 2 sa nepoužívajú. Predstavujú počet delení dividendy deliteľom a preto sú jedinečné pre každý riadok.

Metóda 2 z 2: Hlavné faktory

1. 1 Vynechajte všetky znamienka mínus.
2. 2 Nájdite hlavné faktory čísel. Prezentujte ich tak, ako je to znázornené na obrázku.
   • Napríklad pre 24 a 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • Napríklad pre 50 a 35:
     • 50- 2 x 5 x 5
     • 35- 5 x 7
3. 3 Nájdite spoločné hlavné faktory.
   • Napríklad pre 24 a 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 X 3 x 3
   • Napríklad pre 50 a 35:
     • 50 - 2 x 5 x 5
     • 35- 5 x 7
4. 4 Vynásobte bežné hlavné faktory.
   • Pre 24 a 18 vynásobte 2 a 3 a dostať 6... 6 je najväčší spoločný menovateľ 24 a 18.
   • Pri 50 a 35 nie je čo znásobovať. 5 Je jediným spoločným hlavným faktorom a je ním GCD.
5. 5 Vyrobené!

Tipy

• Jeden zo spôsobov, ako to napísať, je: dividenda> delič modov> = zvyšok; GCD (a, b) = b, ak mod b = 0, a gcd (a, b) = gcd (b, a mod b) inak.
• Ako príklad nájdeme GCD (-77,71). Najprv použite 77 namiesto -77: GCD (-77.91) konvertuje na GCD (77.91). 77 je menej ako 91, takže ich musíme vymeniť, ale zvážte, ako algoritmus funguje, ak nie. Pri výpočte 77 mod 91 dostaneme 77 (77 = 91 x 0 + 77). Pretože to nie je nula, uvažujeme situáciu (b, a mod b), to znamená GCD (77,91) = GCD (91,77). 91 mod 77 = 14 (14 je zvyšok). Nie je nula, takže z GCD (91,77) sa stáva GCD (77,14). 77 mod 14 = 7. Toto nie je nula, takže GCD (77,14) sa stáva GCD (14,7). 14 mod 7 = 0 (pretože 14/7 = 2 bezo zvyšku). Odpoveď: GCD (-77,91) = 7.
• Opísaná metóda je veľmi užitočná na zjednodušenie zlomkov. Vo vyššie uvedenom príklade: -77/91 = -11/13, pretože 7 je najväčší spoločný menovateľ -77 a 91.
• Ak sa a a b rovnajú nule, potom akýmkoľvek nenulovým číslom je ich deliteľ, takže v tomto prípade neexistuje GCD (matematici jednoducho veria, že najväčší spoločný deliteľ 0 a 0 je 0).