Ero sivun ”Eukleideen algoritmi” versioiden välillä
[katsottu versio] | [katsottu versio] |
Ei muokkausyhteenvetoa |
Ei muokkausyhteenvetoa |
||
Rivi 75: | Rivi 75: | ||
==Kirjallisuutta== |
==Kirjallisuutta== |
||
* {{Kirjaviite | Tekijä=Kaleva, Osmo | Nimeke=Numeerinen analyysi | Selite=Opintomoniste 163 | Julkaisija=TTKK | Julkaisupaikka=Tampere | Vuosi=1993 | Tunniste=ISBN 951-721-941-5}} |
* {{Kirjaviite | Tekijä=Kaleva, Osmo | Nimeke=Numeerinen analyysi | Selite=Opintomoniste 163 | Julkaisija=TTKK | Julkaisupaikka=Tampere | Vuosi=1993 | Tunniste=ISBN 951-721-941-5}} |
||
* {{Kirjaviite | Tekijä=Häsä, Jokke |
* {{Kirjaviite | Tekijä=Häsä, Jokke & Rämö, Johanna | Nimeke=Johdatus abstraktiin algebraan | Julkaisupaikka=Helsinki | Julkaisija=Gaudeamus | Vuosi=2015 | Tunniste=ISBN 978-952-495-361-0}} |
||
=== Aiheesta muualla === |
=== Aiheesta muualla === |
Versio 16. joulukuuta 2016 kello 16.49
Eukleideen algoritmin on keino, jonka avulla voidaan selvittää kahden kokonaisluvun suurin yhteinen tekijä (syt). Algoritmi perustuu jakoyhtälön perättäiseen käyttöön.
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
- Toistetaan niin usein, että jakojäännökseksi saadaan nolla.
- Lukujen a ja b suurin yhteinen tekijä on viimeisin nollasta eroava jakojäännös
Algoritmi
Olkoot luvut a ja b kokonaislukuja ja b erisuuri kuin nolla. Käyttämällä toistuvasti jakoyhtälöä saadaan:
...
- .
Algoritmi päättyy, koska luvut r0, r1, ...,rn muodostavat aidosti vähenevän jonon positiivisia kokonaislukuja.
Viimeinen jakojäännös rn jakaa (tasan) luvut a ja b:
Alimmasta yhtälöstä rn jakaa luvun rn-1.
Koska , niin rn jakaa luvun rn-2
Näin jatkamalla saadaan lopulta, että rn jakaa b:n ja a:n.
Jos luvuilla a ja b on yhteinen tekijä c, ts. sanoen a ja b ovat tasan jaollisia luvulla c, c jakaa luvun r0, r1, ... yllä olevien yhtälöiden nojalla. Näin siis c jakaa luvun rn, joka on siten yhteisistä tekijöistä suurin.
Esimerkkejä
Määritetään lukujen 112 ja 408 suurin yhteinen tekijä eli syt(112, 408).
Määritetään lukujen suurin yhteinen tekijä Eukleideen algoritmin avulla:
Lukujen 112 ja 408 suurin yhteinen tekijä on siis kahdeksan eli syt(112, 408)=8.
Kiinalaisten käyttämä algoritmi
Kiinalaiset suorittivat saman algoritmin helmitaulussa seuraavasti:
Vähennä toistuvasti pienempi luku suuremmasta. Kun luvut ovat keskenään yhtä suuret, algoritmi päättyy ja kyseinen luku on suurin yhteinen tekijä.
Esimerkki etsitään syt(15,25).
25 = 1 * 15 + 10.
15 = 1 * 10 + 5.
10 = 2 * 5 + 0.
eli syt(15,25) = 5.
"Kiinalaisittain":
25 | 10 | 10 | 5 |
15 | 15 | 5 | 5 |
Kirjallisuutta
- Kaleva, Osmo: Numeerinen analyysi. Opintomoniste 163. Tampere: TTKK, 1993. ISBN 951-721-941-5.
- Häsä, Jokke & Rämö, Johanna: Johdatus abstraktiin algebraan. Helsinki: Gaudeamus, 2015. ISBN 978-952-495-361-0.