Eukleideen algoritmi

Wikipedia

Eukleideen algoritmin avulla löydetään kahden kokonaisluvun suurin yhteinen tekijä (s.y.t.). Algoritmi perustuu ns. jakoyhtälön perättäiseen käyttöön.

[muokkaa] Esimerkkejä

Etsitään lukujen 31 ja 56 suurin yhteinen tekijä.

Ensin jaetaan 56 31:llä: 56 = 1 * 31 + 25.
Sitten 31 25:llä: 31 = 1 * 25 + 6.
Sitten 25 6:lla: 25 = 4 * 6 + 1.
Sitten 6 1:llä: 6 = 6 * 1 + 0.

Viimeinen nollasta eroava on lukujen 31 ja 56 suurin yhteinen tekijä eli syt(31,56)=(31,56)=1. Tämä nähdään myös lukujen alkutekijähajotelmien avulla selvästi: 31 on alkuluku ja 56 = 23 * 7, joten suurin yhteinen tekijä on 1.

Kiinalaiset suorittivat saman algoritmin helmitaulussa seuraavasti:

Vähennä toistuvasti pienempää suuremmasta. Kun luvut ovat samat, algoritmi päättyy ja ko. luku on suurin yhteinen tekijä.

31 31 6 6 6 6 6 ... 1
56 25 25 19 13 7 1 ... 1


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

[muokkaa] 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 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 rn - 2 = qnrn - 1 + rn, 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.