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\times \,3+72$

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

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

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

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

Lukujen 112 ja 408 suurin yhteinen tekijä on siis kahdeksan eli syt(112, 408)=8.

Kiinalaisten käyttämä algoritmi

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