Suurin yhteinen tekijä
Kahden kokonaisluvun suurin yhteinen tekijä on luku, joka jakaa molemmat luvut ilman jakojäännöstä ja jolle ei ole olemassa mitään toista suurempaa lukua, joka jakaisi myös molemmat luvut ilman jakojäännöstä.
Otetaan esimerkiksi luvut 24 ja 32. Mikä on niiden suurin yhteinen tekijä? Etsimme ensin lukua, joka jakaa molemmat luvut.
- Esimerkiksi luku 12 jakaa luvun 24, mutta ei jaa lukua 32, koska 32 / 12 on 2,666…, mikä ei ole kokonaisluku. Luku 12 ei siis voi olla lukujen 24 ja 32 suurin yhteinen tekijä.
- Entä vaikka luku 4? Se jakaa molemmat luvut, 24 / 4 on 6 ja 32 / 4 on 8. Luku 4 on siis ensimmäinen ehdokkaamme. Onko olemassa jotain suurempaa lukua, joka jakaisi molemmat luvut?
- Luku 8 jakaa sekä luvun 24 että luvun 32 ja on samalla suurempi kuin 4.
- Mitään muuta lukua, joka on suurempi kuin 8 ja jakaisi molemmat luvut, ei ole olemassa. Luku 8 on siis lukujen 24 ja 32 suurin yhteinen tekijä.
Eukleideen algoritmi suurimman yhteisen tekijän löytämiseksi
On melko yksinkertainen tapa löytää kahden luvun suurin yhteinen tekijä Eukleideen algoritmilla. Olkoon alussa kaksi lukua x ja y, joiden suurimman yhteisen tekijän haluamme löytää. Kokeillaan esimerkiksi luvuilla x = 50 ja y = 35. Toimimme sitten näin:
- Jaetaan x / y ja painetaan jakojäännös mieleen. Merkitään tämä jakojäännös z:lla. Esimerkissämme saamme 50 / 35, mikä antaa jakojäännökseksi z = 15.
- Nyt vaihdetaan muuttujat: tallennetaan muuttujaan x arvo y ja muuttujaan y arvo z. Muuttujan x alkuperäinen arvo hylätään. Tämän vaiheen jälkeen saamme x = 35 ja y = 15.
- Nyt katsomme, onko y yhtä suuri kuin nolla. Jos on, suurin yhteinen tekijä on luku x. Koska y ei ole nolla, jatkamme ja toistamme koko menettelyn alusta ensimmäisestä kohdasta.
- Jaamme taas x / y, eli jaamme 35 / 15, mikä antaa jakojäännökseksi z = 5.
- Vaihdamme muuttujat, jolloin saamme x = 15 ja y = 5. Koska y ei ole nolla, jatkamme.
- Jaetaan x / y, eli jaetaan 15 / 5. Jakojäännös on z = 0.
- Vaihdamme muuttujat ja saamme x = 5 ja y = 0.
- Nyt y = 0 ja algoritmimme päättyy. Suurin yhteinen tekijä on luku x = 5.
Tärkeää on, että lukujen järjestyksellä ei ole väliä. Jos vaihtaisimme esimerkin luvut keskenään, saisimme parin x = 35 ja y = 50. Menettely olisi sama:
- Jaetaan x / y, eli jaetaan 35 / 50, mikä antaa jakojäännökseksi z = 35.
- Vaihdetaan muuttujat: x = 50 ja y = 35.
- Näemme, että tämän vaiheen jälkeen vaihdoimme vain muuttujien x ja y sisällöt keskenään…
Laskin
Tämä laskin laskee suurimman yhteisen tekijän.
