Eukleideen algoritmi

Kohteesta Wikipedia
Loikkaa: valikkoon, 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ä]