Eukleideen algoritmi

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.

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 = 2³ * 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

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.