Eukleideen algoritmi

Wikipedia

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 algorimi 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

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