Eukleideen algoritmi

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:

$a=q_{0}b+r_{0},\ 0<r_{0}<|b|$

$b=q_{1}r_{0}+r_{1},\ 0<r_{1}<|r_{0}|$

$r_{0}=q_{2}r_{1}+r_{2},\ 0<r_{2}<|r_{1}|$

$r_{1}=q_{3}r_{2}+r_{3},\ 0<r_{3}<|r_{2}|$

$r_{2}=q_{4}r_{3}+r_{4},\ 0<r_{4}<|r_{3}|$

$r_{3}=q_{5}r_{4}+r_{5},\ 0<r_{5}<|r_{4}|$

...

$r_{n-2}=q_{n}r_{n-1}+r_{n},\ 0<r_{n}<|r_{n-1}|$

$r_{n-1}=q_{n+1}r_{n}+0\$.

Algoritmi päättyy, koska luvut r₀, r₁, ...,r_n muodostavat aidosti vähenevän jonon positiivisia kokonaislukuja.

Viimeinen jakojäännös r_n jakaa (tasan) luvut a ja b:

Alimmasta yhtälöstä r_n jakaa luvun r_n-1.
Koska $r_{n-2}=q_{n}r_{n-1}+r_{n}$, niin r_n jakaa luvun r_n-2
Näin jatkamalla saadaan lopulta, että r_n 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 r₀, r₁, ... yllä olevien yhtälöiden nojalla. Näin siis c jakaa luvun r_n, 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:

$408=112\cdot \,3+72$

$112=72\cdot \,1+40$

$72=40\cdot \,1+32$

$40=32\cdot \,1+8$

$32=8\cdot \,4+0$

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":

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.

Aiheesta muualla

• Eukleideen algoritmi, online sovellus