Matematiikka:Eukleideen algoritmi

Tällä käsitteellä ei ole otsikon muodostavia nimityksiä.

Eukleideen algoritmi (luo nimityssivu)

Määritelmä Menetelmä, jolla löydetään kahden eri luvun suurin yhteinen tekijä jakamalla ensin suurempi luku pienemmällä ja sitten toistamalla sama pienemmälle luvulle ja jakojäännökselle jne

Selite Eukleideen algoritmia sovelletaan seuraavasti kahteen kokonaislukuun $m$ ja $n$, joilla $m\ge n$. Jaetaan ensin luku $m$ luvulla $n$. Jos jako menee tasan, niin suurin yhteinen tekijä $syt(m,n)=n$. Jos jako ei mene tasan, on $m=kn+r$ jollakin kokonaisluvulla $k$, missä $r$ on jakojäännös. Nyt $syt(m,n)=syt(n,r)$, joten toistetaan edellinen luvuille $n$ ja $r$, ja jatketaan tätä kunnes suurin yhteinen tekijä löytyy.

Etsitään esimerkiksi $\mathrm{s}\mathrm{y}\mathrm{t}(17,20)$. Koska $20/17=1\cdot 17+3$ on jakojäännös $3$, joten $\mathrm{s}\mathrm{y}\mathrm{t}(17,20)=\mathrm{s}\mathrm{y}\mathrm{t}(17,3)$.Koska $17/3=5\cdot 3+2$, on jakojäännös $2$, joten $\mathrm{s}\mathrm{y}\mathrm{t}(17,20)=\mathrm{s}\mathrm{y}\mathrm{t}(3,2)$.Koska $3/2=1\cdot 2+1/$, on jakojäännös $1$, joten $\mathrm{s}\mathrm{y}\mathrm{t}(17,20)=\mathrm{s}\mathrm{y}\mathrm{t}(2,1)$. Koska $2/1=2$, menee jako tasan, joten $\mathrm{s}\mathrm{y}\mathrm{t}(17,20)=1$.

Erikieliset vastineet

euclid's algorithm (luo nimityssivu)	englanti (English)
euclidean algorithm (luo nimityssivu)	englanti (English)

Alaviitteet

Lähdeviittaus tähän sivuun:
Tieteen termipankki 6.12.2025: Matematiikka:Eukleideen algoritmi. (Tarkka osoite: https://tieteentermipankki.fi/wiki/Matematiikka:Eukleideen algoritmi.)

Siirry tarkastelemaan sivun muokkaushistoriaa →