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

Suoritus peräkkäisten jakokulmien avulla[muokkaa | muokkaa wikitekstiä]

Edellä johdettu laskutoimitus voidaan kynällä ja paperilla laskettaessa suorittaa myös peräkkäisten jakokulmien avulla seuraavaan muotoon:

                 408|112
                -336|  3
            112|  72
            -72|   1
         72| 40
        -40|  1
     40| 32
    -32|  1 
 32|  8
-32|  4
  0

Ensimmäisessä jakolaskussa on suurempi alkuperäisistä luvuista jaettavana, pienempi jakajana. Kussakin jakokulmassa on ylävasemmalla jaettava ja yläoikealla jakaja. Osamäärän kokonaisosa merkitään alaoikealle, kun taas alavasemmalla suoritetaan vähennyslasku, josta saadaan jakojäännös. Kun jakolasku on suoritettu, jaetaan edellisen jakolaskun jakaja saadulla jakojäännöksellä, mikä suoritetaan merkitsemällä se jakojäännöksen vasemmalle puolelle ja suorittamalla jakolasku tavalliseen tapaan. Näin jatketaan, kunnes jakojäännös on nolla, jolloin viimeinen sitä edeltänyt jakaja (tässä esimerkissä 8) on alkuperäisten lukujen suurin yhteinen tekijä.

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

Lähteet[muokkaa | muokkaa wikitekstiä]

  1. Thompson, Jan & Martinsson, Thomas: Matematiikan käsikirja, s. 92. Helsinki: Tammi, 1994. ISBN 951-31-0471-0.

Kirjallisuutta[muokkaa | muokkaa wikitekstiä]

Aiheesta muualla[muokkaa | muokkaa wikitekstiä]