Sisältö

• Askeleet
• Menetelmä 1/2: Jakajaalgoritmi
• Menetelmä 2/2: Esitä tekijät
• Vinkkejä

Suurin yhteinen jakaja (GCD) kahdesta kokonaisluvusta on suurin kokonaisluku, joka jakaa nämä numerot. Esimerkiksi gcd 20: lle ja 16: lle on 4 (sekä 16: lla että 20: llä on suuret jakajat, mutta ne eivät ole yleisiä - esimerkiksi 8 on jakaja 16, mutta ei 20: n jakaja). GCD: n löytämiseksi on olemassa yksinkertainen ja järjestelmällinen menetelmä, jota kutsutaan "Eukleidesin algoritmiksi". Tämä artikkeli näyttää, kuinka löytää kahden kokonaisluvun suurin yhteinen jakaja.

Askeleet

Menetelmä 1/2: Jakajaalgoritmi

1. 1 Jätä kaikki miinusmerkit pois.
2. 2 Opi terminologia: kun jaat 32 5: llä,
   • 32 - osinko
   • 5 - jakaja
   • 6 - yksityinen
   • 2 - loput
3. 3 Määritä suurempi numeroista. Se on jaollinen ja pienempi luku on jakaja.
4. 4 Kirjoita seuraava algoritmi muistiin: (osinko) = (jakaja) * (osamäärä) + (loppuosa)
5. 5 Laita suurempi numero osingon tilalle ja pienempi luku jakajan tilalle.
6. 6 Etsi, kuinka monta kertaa suurempi luku jaetaan pienemmällä, ja kirjoita tulos osamäärän sijaan.
7. 7 Etsi loput ja kirjoita se oikeaan paikkaan algoritmissa.
8. 8 Kirjoita algoritmi uudelleen, mutta (A) kirjoita edellinen jakaja uutena osinkona ja (B) edellinen jäännös uutena jakajana.
9. 9 Toista edellinen vaihe, kunnes loppuosa on 0.
10. 10 Viimeinen jakaja on suurin yhteinen jakaja (GCD).
11. 11 Etsitään esimerkiksi GCD 108: lle ja 30: lle:
12. 12 Huomaa, kuinka ensimmäisen rivin numerot 30 ja 18 muodostavat toisen rivin. Sitten 18 ja 12 muodostavat kolmannen rivin ja 12 ja 6 muodostavat neljännen rivin. Useita numeroita 3, 1, 1 ja 2 ei käytetä. Ne edustavat sitä, kuinka monta kertaa osinko jakautuu jakajalla, ja ovat siten yksilöllisiä kullekin riville.

Menetelmä 2/2: Esitä tekijät

1. 1 Jätä kaikki miinusmerkit pois.
2. 2 Etsi numeroiden alkutekijät. Esitä ne kuvan osoittamalla tavalla.
   • Esimerkiksi 24 ja 18:
     • 24-2 x 2 x 2 x 3
     • 18-2 x 3 x 3
   • Esimerkiksi 50 ja 35:
     • 50-2 x 5 x 5
     • 35-5 x 7
3. 3 Etsi yhteisiä alkutekijöitä.
   • Esimerkiksi 24 ja 18:
     • 24- 2 x 2 x 2 x 3
     • 18- 2 x 3 x 3
   • Esimerkiksi 50 ja 35:
     • 50 - 2 x 5 x 5
     • 35- 5 x 7
4. 4 Kerro yhteiset alkutekijät.
   • Kerro 24 ja 18 2 ja 3 ja saada 6... 6 on 24 ja 18 suurin yhteinen nimittäjä.
   • Ei ole mitään kerrottavaa 50: lle ja 35: lle. 5 On ainoa yhteinen ensisijainen tekijä, ja se on GCD.
5. 5 Valmistettu!

Vinkkejä

• Yksi tapa kirjoittaa tämä on: osinko> mod jakaja> = jäännös; GCD (a, b) = b, jos mod b = 0, ja gcd (a, b) = gcd (b, a mod b) muutoin.
• Esimerkkinä löydetään GCD (-77,91). Käytä ensin 77 -arvon sijaan -77: GCD (-77,91) muuntaa GCD: ksi (77,91). 77 on pienempi kuin 91, joten meidän on vaihdettava ne, mutta harkitse, miten algoritmi toimii, jos emme tee sitä. Kun lasketaan 77 mod 91, saamme 77 (77 = 91 x 0 + 77). Koska tämä ei ole nolla, tarkastelemme tilannetta (b, a mod b), eli GCD (77,91) = GCD (91,77). 91 mod 77 = 14 (14 on loppuosa). Se ei ole nolla, joten GCD: stä (91,77) tulee GCD (77,14). 77 mod 14 = 7. Tämä ei ole nolla, joten GCD: stä (77.14) tulee GCD (14.7). 14 mod 7 = 0 (koska 14/7 = 2 ilman jäännöstä). Vastaus: GCD (-77,91) = 7.
• Kuvattu menetelmä on erittäin hyödyllinen jakeiden yksinkertaistamiseksi. Yllä olevassa esimerkissä: -77/91 = -11/13, koska 7 on suurin yhteinen nimittäjä -77 ja 91.
• Jos a ja b ovat nolla, niin mikä tahansa muu kuin nolla on niiden jakaja, joten tässä tapauksessa ei ole GCD: tä (matemaatikot yksinkertaisesti uskovat, että suurin yhteinen jakaja 0 ja 0 on 0).