Eukleideen algoritmi

Eukleideen algoritmin on keino, jonka avulla voidaan selvittää kahden kokonaisluvun suurin yhteinen tekijä (syt).

Oletetaan että meidän pitäisi löytää syt n1:lle(120) ja n2:lle(84)

Jaetaan n1 n2:lla, saadan joku jakojäännös (r1). Jos n2>n1 niin vaihdetaan niitä.

120/84
120=84*1+36, eli r=36.

Nyt otetaan edellisestä askelesta n2(se on pienin) ja r, siis 84 ja 36

84/36
84=36*2+12, ja seuraava pari on 36(pienin) ja 12

36/12=3, eikö me saadan mitään jakojännosta. Siis edellisen jäköjäänös on syt(=12)

84/12=7
120/12=10
10 ja 7 ovat keskenään jaottomia, siis syt(120,84)=12

Tässä on pieni sovellus joka laskee syt(siihen voi laitta muut arvot, sitten pitäisi paina [syt])