Eukleideen algoritmi

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.

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

Algoritmi 

Alla kaksi esimerkkiä. 

1.

Olkoon a =48 ja b=18

a:b=2 kokonaislukua ja jakojäännös = 12 (48:18 on 2 kokonaista ja 12 on jakojäännös)

b:12=1 kokonaisluku ja jakojäännös = 6

12:6=2 ja jakojäännös on 0.

Suurin yhteinen tekijä luvuilla 48 ja 18 on siis tuo viimeinen jakojäännös, jolla jaoimme eli 6.

2.

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.

Suoritus peräkkäisten jakokulmien avulla 
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 
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":

Lähteet

Kirjallisuutta

Aiheesta muualla 

Eukleideen algoritmi, online sovellus

Lukuteoria
Algoritmit
Seulonnan keskeiset artikkelit