Eukleideen algoritmi

Kohteesta Wikipedia
Siirry navigaatioon Siirry hakuun

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[muokkaa | muokkaa wikitekstiä]

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ä[muokkaa | muokkaa wikitekstiä]

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[muokkaa | muokkaa wikitekstiä]

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[muokkaa | muokkaa wikitekstiä]

  • 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.

Aiheesta muualla[muokkaa | muokkaa wikitekstiä]