GCD & LCM laskin

GCD, jota kutsutaan myös suurimmaksi yhteiseksi tekijäksi (Greatest Common Factor, GCF), on suurin positiivinen kokonaisluku, joka jakaa molemmat luvut ilman jäännöstä. Esimerkiksi 12:n ja 18:n GCD on 6, koska 6 on suurin luku, joka jakaa molemmat tasan.

LCM on pienin positiivinen kokonaisluku, joka on jaollinen molemmilla luvuilla. Esimerkiksi 4:n ja 6:n LCM on 12, koska 12 on pienin luku, joka voidaan jakaa sekä 4:llä että 6:lla.

Mille tahansa kahdelle positiiviselle kokonaisluvulle a ja b pätee: GCD(a,b) × LCM(a,b) = a × b. Tämän suhteen avulla voit laskea LCM:n, jos tiedät GCD:n, tai päinvastoin.

GCD on olennainen murtolukujen yksinkertaistamisessa (jaa osoittaja ja nimittäjä niiden GCD:llä), diofanttisten yhtälöiden ratkaisemisessa sekä erilaisissa kryptografian ja tietotekniikan sovelluksissa.

Yksinkertaista murtoluku jakamalla sekä osoittaja että nimittäjä niiden GCD:llä. Esimerkiksi yksinkertaistaaksesi 24/36: etsi GCD(24,36) = 12 ja jaa molemmat luvut 12:lla, jolloin saat 2/3. Näin saat murtoluvun pienimpänä.

LCM:ää käytetään synkronoitaessa toistuvia tapahtumia. Esimerkkeinä voidaan mainita, milloin kaksi bussia saapuu samaan aikaan, murtolukujen yhteenlaskun yhteisten nimittäjien määrittäminen, toistuvien tehtävien ajoittaminen tai sen suunnittelu, milloin hammaspyörät, joiden hammasluvut ovat erilaiset, asettuvat kohdakkain.

Jaa jokainen luku alkutekijöihin ja kerro sitten yhteiset tekijät pienimmillä potensseilla. Esimerkiksi 48 = 2^4 × 3 ja 18 = 2 × 3^2. Yhteiset tekijät ovat 2^1 ja 3^1, joten GCD = 2 × 3 = 6.

Jaa jokainen luku alkutekijöihin ja kerro sitten kaikki tekijät suurimmilla potensseilla. Jos 12 = 2^2 × 3 ja 18 = 2 × 3^2, ota 2^2 ja 3^2, joten LCM = 4 × 9 = 36.

Euklidinen algoritmi löytää GCD:n tehokkaasti jakamalla ja ottamalla jäännökset toistuvasti. GCD(48,18): Kun jäännös on 0, viimeinen jakaja (6) on GCD: 48÷18=2 jäännös 12, 18÷12=1 jäännös 6, 12÷6=2 jäännös 0. Kun jäännös on 0, viimeinen jakaja (6) on GCD.