Vsebina

• Koraki
• Metoda 1 od 2: Algoritem delilnika
• Metoda 2 od 2: Glavni dejavniki
• Nasveti

Največji skupni delitelj (GCD) dveh celih števil je največje celo število, ki deli vsako od teh števil. Na primer, gcd za 20 in 16 je 4 (tako 16 kot 20 imata velika delitelja, vendar nista pogosta - na primer 8 je delitelj 16, ne pa delitelj 20). Obstaja preprosta in sistematična metoda za iskanje GCD, imenovana "Euclidov algoritem". Ta članek vam bo pokazal, kako najti največji skupni delitelj dveh celih števil.

Koraki

Metoda 1 od 2: Algoritem delilnika

1. 1 Izpustite vse znake minus.
2. 2 Naučite se terminologije: pri deljenju 32 s 5,
   • 32 - dividenda
   • 5 - delitelj
   • 6 - zasebno
   • 2 - ostanek
3. 3 Določite večje število. To bo deljivo, manjše število pa delitelj.
4. 4 Zapišite naslednji algoritem: (dividenda) = (delitelj) * (količnik) + (ostanek)
5. 5 Na mesto dividende postavite večje število, na mesto delitelja pa manjše število.
6. 6 Poiščite, kolikokrat je večje število deljeno z manjšim, in namesto količnika zapišite rezultat.
7. 7 Poiščite ostanek in ga zapišite na ustrezno mesto v algoritmu.
8. 8 Znova zapišite algoritem, vendar (A) napišite prejšnji delitelj kot novo dividendo in (B) prejšnji ostanek kot nov delitelj.
9. 9 Ponovite prejšnji korak, dokler ostanek ni 0.
10. 10 Zadnji delilec bo največji skupni delitelj (GCD).
11. 11 Najdemo na primer GCD za 108 in 30:
12. 12 Opazite, kako številki 30 in 18 iz prve vrstice tvorita drugo vrstico. Nato 18 in 12 tvorita tretjo vrstico, 12 in 6 pa četrto vrstico. Večkratniki 3, 1, 1 in 2 se ne uporabljajo. Predstavljajo, kolikokrat je dividenda deljiva z deliteljem in so zato edinstvene za vsako vrstico.

Metoda 2 od 2: Glavni dejavniki

1. 1 Izpustite vse znake minus.
2. 2 Poiščite osnovne faktorje števil. Predstavite jih, kot je prikazano na sliki.
   • Na primer za 24 in 18:
     • 24-2 x 2 x 2 x 3
     • 18-2 x 3 x 3
   • Na primer za 50 in 35:
     • 50-2 x 5 x 5
     • 35-5 x 7
3. 3 Poiščite skupne glavne dejavnike.
   • Na primer za 24 in 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • Na primer za 50 in 35:
     • 50 - 2 x 5 x 5
     • 35- 5 x 7
4. 4 Pomnožite skupne osnovne faktorje.
   • Za 24 in 18 pomnožite 2 in 3 in dobite 6... 6 je največji skupni imenovalec 24 in 18.
   • Za 50 in 35 ni kaj pomnožiti. 5 Je edini skupni glavni faktor in je GCD.
5. 5 Narejeno!

Nasveti

• Eden od načinov za zapis tega je: dividend> mod delilnik> = ostanek; GCD (a, b) = b, če je mod b = 0, in gcd (a, b) = gcd (b, mod b) drugače.
• Kot primer poiščimo GCD (-77,91). Najprej uporabite 77 namesto -77: GCD (-77,91) se pretvori v GCD (77,91). 77 je manj kot 91, zato jih moramo zamenjati, vendar razmislite, kako deluje algoritem, če tega ne storimo. Pri izračunu 77 mod 91 dobimo 77 (77 = 91 x 0 + 77). Ker to ni nič, upoštevamo situacijo (b, mod b), to je GCD (77,91) = GCD (91,77). 91 mod 77 = 14 (14 je ostanek). Ni nič, zato GCD (91,77) postane GCD (77,14). 77 mod 14 = 7. To ni nič, zato GCD (77.14) postane GCD (14.7). 14 mod 7 = 0 (od 14/7 = 2 brez ostanka). Odgovor: GCD (-77,91) = 7.
• Opisana metoda je zelo uporabna za poenostavitev ulomkov. V zgornjem primeru: -77/91 = -11/13, saj je 7 največji skupni imenovalec -77 in 91.
• Če sta a in b enaka nič, potem je vsako deljeno število, ki ni nič, njihov delitelj, zato v tem primeru ni GCD (matematiki preprosto verjamejo, da je največji skupni delitelj 0 in 0 0).