Eukleideen algoritmi
algoritmi suurimman yhteisen tekijän laskemiseen / From Wikipedia, the free encyclopedia
Eukleideen algoritmi on Eukleideen mukaan nimetty menetelmä, jonka avulla voidaan selvittää kahden kokonaisluvun suurin yhteinen tekijä (syt). Algoritmi perustuu jakoyhtälön perättäiseen käyttöön.[1]
Eukleideen algoritmi etenee seuraavasti:
- Ensin kirjoitetaan jakoyhtälö luvuilla a ja b
- Seuraavaksi kirjoitetaan jakoyhtälö luvulle b ja edellisen jakoyhtälön jakojäännökselle
- Aiempi jakojäännös jaetaan uudella jakojäännöksellä
- Toistetaan niin usein, että jakojäännökseksi saadaan nolla.
- Lukujen a ja b suurin yhteinen tekijä on viimeisin nollasta eroava jakojäännös