Sisu

• Sammud
• Meetod 1: 2: jagaja algoritm
• Meetod 2/2: esmased tegurid
• Näpunäiteid

Kahe täisarvu suurim ühine jagaja (GCD) on suurim täisarv, mis jagab kõik need arvud. Näiteks gcd 20 ja 16 jaoks on 4 (nii 16 kui ka 20 -l on suured jagajad, kuid need pole tavalised - näiteks 8 jagab 16 -d, kuid ei jaga 20 -d). GCD leidmiseks on lihtne ja süstemaatiline meetod, mida nimetatakse "Eukleidese algoritmiks". See artikkel näitab teile, kuidas leida kahe täisarvu suurim ühine jagaja.

Sammud

Meetod 1: 2: jagaja algoritm

1. 1 Vältige miinusmärke.
2. 2 Õppige terminoloogiat: jagades 32 5 -ga,
   • 32 - dividendid
   • 5 - jagaja
   • 6 - privaatne
   • 2 - ülejäänud
3. 3 Määrake arvudest suurem. See on jagatav ja väiksem arv on jagaja.
4. 4 Kirjutage üles järgmine algoritm: (dividend) = (jagaja) * (jagatis) + (ülejäänud)
5. 5 Pane dividendi asemele suurem ja jagaja asemele väiksem number.
6. 6 Leidke mitu korda suurem arv jagatakse väiksemaga ja kirjutage jagatise asemel tulemus.
7. 7 Leidke ülejäänud osa ja kirjutage see algoritmi sobivasse kohta.
8. 8 Kirjutage algoritm uuesti, kuid (A) kirjutage eelmine jagaja uue dividendina ja (B) eelmine jääk uue jagajana.
9. 9 Korrake eelmist sammu, kuni ülejäänud osa on 0.
10. 10 Viimane jagaja on suurim ühine jagaja (GCD).
11. 11 Näiteks leidke GCD 108 ja 30 jaoks:
12. 12 Pange tähele, kuidas esimese rea numbrid 30 ja 18 moodustavad teise rea. Seejärel moodustavad kolmanda rea ​​18 ja 12 ning neljanda rea ​​12 ja 6. 3, 1, 1 ja 2 kordajaid ei kasutata. Need tähistavad, mitu korda dividend jagaja jagaja on ja on seega iga rea ​​jaoks ainulaadsed.

Meetod 2/2: esmased tegurid

1. 1 Vältige miinusmärke.
2. 2 Leidke numbrite algtegurid. Esitage need nii, nagu pildil näidatud.
   • Näiteks 24 ja 18 puhul:
     • 24-2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • Näiteks 50 ja 35 puhul:
     • 50- 2 x 5 x 5
     • 35-5x7
3. 3 Leidke ühised peamised tegurid.
   • Näiteks 24 ja 18 puhul:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • Näiteks 50 ja 35 puhul:
     • 50–2 korda 5 x 5
     • 35- 5 x 7
4. 4 Korrutage ühised algtegurid.
   • 24 ja 18 korral korrutage 2 ja 3 ja saada 6... 6 on 24 ja 18 suurim ühine nimetaja.
   • 50 ja 35 jaoks pole midagi korrutada. 5 See on ainus ühine peamine tegur ja see on GCD.
5. 5 Valmistatud!

Näpunäiteid

• Üks võimalus seda kirjutada on: dividend> mod divider> = ülejäänud; GCD (a, b) = b, kui mod b = 0, ja gcd (a, b) = gcd (b, a mod b) muidu.
• Näitena leiame GCD (-77,91). Esiteks kasutage -77 asemel 77: GCD (-77,91) teisendatakse GCD -ks (77,91). 77 on väiksem kui 91, seega peame need vahetama, kuid kaaluge, kuidas algoritm töötab, kui me seda ei tee. 77 mod 91 arvutamisel saame 77 (77 = 91 x 0 + 77). Kuna see pole null, kaalume olukorda (b, a mod b), see tähendab GCD (77,91) = GCD (91,77). 91 mod 77 = 14 (14 on ülejäänud). See ei ole null, seega muutub GCD (91,77) GCD -ks (77,14). 77 mod 14 = 7. See pole null, seega muutub GCD (77.14) GCD -ks (14.7). 14 mod 7 = 0 (kuna 14/7 = 2 ilma jäägita). Vastus: GCD (-77,91) = 7.
• Kirjeldatud meetod on murdude lihtsustamiseks väga kasulik. Ülaltoodud näites: -77/91 = -11/13, kuna 7 on suurim ühine nimetaja -77 ja 91.
• Kui a ja b on võrdsed nulliga, siis on nende jagaja mistahes nullist erinev arv, seega antud juhul GCD puudub (matemaatikud lihtsalt usuvad, et 0 ja 0 suurim ühine jagaja on 0).