Back خوارزمية أقليدس Arabic Algoritmu d'Euclides AST Evklid alqoritmi Azerbaijani Евклид алгоритмы Bashkir Алгарытм Эўкліда Byelorussian Алгоритъм на Евклид Bulgarian ইউক্লিডীয় এলগরিদম Bengali/Bangla Algorisme d'Euclides Catalan ئەلگۆریتمی ئیقلیدس CKB Eukleidův algoritmus Czech
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
- ↑ Viittausvirhe: Virheellinen
<ref>-elementti; viitettäm1ei löytynyt