Euklideszi algoritmus forrásának megtekintése

[[Fájl:Euclid's algorithm Book VII Proposition 2 3.png|300px|bélyegkép|jobbra|Euklideszi algoritmus az AB és CD kiindulási szakaszok legnagyobb közös osztójának megtalálására. A két szakaszt egy egység többszöröseként határozták meg, tehát a legnagyobb közös osztójuk létezik. Mivel a CD szakasz rövidebb, ezért megméri vele az AB-t, de csak egyszer fér rá, és marad az AE szakasz. Az AE szakasszal megméri a CD szakaszt, kétszer fér rá, és marad a CF szakasz. Ezután a CF szakasszal megméri az AE szakaszt. Mivel nincs maradék, így a legnagyobb közös osztó CF. Jobb oldalon [[Nikomakhosz Geraszénosz|Nikomakhosz]] példája a 49 és 21 számokkal; a legnagyobb közös osztó a 7 (Heath 1908:300)]]

Az '''euklideszi algoritmus'''<ref>A matematikus nevének szabatos átírása ''Eukleidész'' volna, tehát a szerkezet ''eukleidészi algoritmus'', de ebben a kifejezésben hagyományosan rögzült ''euklideszi'' alakban (lásd például [[Püthagorasz]], de [[Pitagorasz-tétel]] stb.).</ref> egy [[számelmélet]]i [[algoritmus]], amellyel két szám [[legnagyobb közös osztó]]ja határozható meg. Nevét az [[ókori Görögország|ókori görög]] matematikusról, [[Eukleidész (matematikus)|Eukleidészről]] kapta, aki az ''[[Elemek]]''ben írta le (Kr. e. 300 körül). Az egyik legrégibb, gyakran használt algoritmus.

Alapötlete az, hogy a [[legnagyobb közös osztó]] nem változik, ha a nagyobb számot a két szám különbségével helyettesítjük. Például 252 és 105 legnagyobb közös osztója 21, amely legnagyobb közös osztója a 105 és a 147 = 252 − 105 számoknak is. Ez a helyettesítés csökkenti a nagyobb számot, így a cserék ismétlésével egyre kisebb számokat kapunk, egészen addig, amíg a két szám egyenlővé nem válik. Ez az eddigi számpárok, így az eredeti számpár legnagyobb közös osztója. Az algoritmus lépésein visszafelé menve találunk két egész (akár negatív) tényezőt, amelyek felhasználásával a legnagyobb közös osztó kifejezhető a két kiindulási szám lineáris kombinációjaként.

Ha feltesszük, hogy a kivonások és a [[maradékos osztás]]ok ideje körülbelül megegyezik, akkor az algoritmusnak van egy gyorsabb változata is, amely a kivonások helyett maradékos osztással működik. Ennek lényege, hogy ha a nagyobb szám sokkal nagyobb, mint a kisebb, akkor sok kivonást kell elvégezni addig, amíg a két szám szerepe felcserélődik. A maradékképzés művelete ezt a sok kivonást egy lépésben végzi el. Az algoritmus akkor ér véget, amikor a maradék nulla lesz. Ekkor a legnagyobb közös osztó éppen a kisebb szám. Ezzel az algoritmus lépésszáma a kisebb szám [[logaritmus]]ával arányossá válik (sohasem nagyobb, mint a tízes számrendszerbeli jegyek számának ötszöröse). A 20. század folyamán további optimalizációt végeztek.

Az algoritmusnak számos alkalmazása van. A törtek egyszerűsítése mellett a [[Kongruencia|moduláris aritmetika]] osztás műveletének megvalósításában is szerepel. Ehhez az ''ax'' ≡ ''c'' mod ''b'' kongruenciát kell megoldani, ezt a ''Lineáris diofantoszi egyenletek'' szakasz írja le részletesebben. Használható [[diofantoszi egyenlet]]ek megoldására, mint amilyen például a [[kínai maradéktétel]]ben szereplő szimultán kongruenciarendszer. Alkalmas [[lánctört]]be fejtéshez és [[irracionális számok]] közelítéséhez. Végül, de nem utolsósorban számelméleti tételek bizonyításának is hasznos segédeszköze; felhasználja a [[négynégyzetszám-tétel]] és [[a számelmélet alaptétele]].

Eredetileg egész számokra és szakaszokra használták, de a 19. században általánosították [[Gauss-egész]]ekre és egyváltozós [[polinom]]okra.

== Háttere ==

[[Fájl:24x60.svg|bélyegkép|fennjobbra|alt="Magas, keskeny téglalap négyzetrácsra osztva. A téglalap két négyzet széles és öt négyzet magas."|Egy 24-szer 60-as téglalapot tíz 12-szer 12-es négyzet fed le, ahol 12 is 24 és 60 legnagyobb közös osztója. Általában, egy ''a''-szor ''b''-s téglalap akkor és csak akkor fedhető le ''c'' oldalú négyzetekkel, ha ''c'' közös osztója ''a''-nak és ''b''-nek.]]
Az algoritmus alapesetben [[természetes számok]] legnagyobb közös osztóját számítja ki, amely a legnagyobb olyan természetes szám, amely mindkettőnek osztója. Az ''a'' és ''b'' számok legnagyobb közös osztójának jelölése lnko(''a'', ''b'') vagy egyszerűbben (''a'', ''b''),{{refhely|Stark 1978|16. o.}} – habár ez utóbbival más matematikai objektumokat is szoktak jelölni, például [[vektor]]okat.

Ha lnko(''a'', ''b'') = 1, akkor a két szám [[relatív prímek|relatív prím]].{{refhely|Stark 1978|21. o.}} Ebből nem következik, hogy a két szám prím,{{refhely|LeVeque 1996|32. o.}} vagy egyikük prím, habár két különböző [[Prímszámok|prímszám]] relatív prím. Az egy minden egészhez relatív prím, de például 35 és 6 is relatív prímek: 6 = 2 × 3 és 35 = 5 × 7. Mivel nincsenek közös prímtényezőik, csak az egy osztója mindkét számnak.

Legyen g = lnko(''a'', ''b''). Mivel ''a'' és ''b'' többszöröse ''g''-nek, azért ezek felírhatók, mint ''a'' = ''mg'', és ''b'' = ''ng''. Az ''m'' és az ''n'' számok relatív prímek, különben ki lehetne emelni belőlük a legnagyobb közös osztót, így kiderülne, hogy az ''a'' és ''b'' számoknak van ''g''-nél nagyobb közös osztójuk, tehát ''g'' nem legnagyobb közös osztó. A legnagyobb közös osztó a közös osztók többszöröse.{{refhely|LeVeque 1996|31. o.}}

A legnagyobb közös osztó megjeleníthető a következőképpen:
<ref>{{cite book | last = Grossman|first= J. W. | year = 1990 | title = Discrete Mathematics | url = https://archive.org/details/discretemathemat0000gros_a2g6| publisher = Macmillan | location = New York | isbn = 0-02-348331-8 | page = [https://archive.org/details/discretemathemat0000gros_a2g6/page/213 213]}}</ref>

Legyenek egy téglalap oldalai ''a'' és ''b'' hosszúak. Ekkor a téglalap felosztható ''c'' oldalhosszú négyzetrácsra, ha ''c'' közös osztója ''a''-nak és ''b''-nek. A legnagyobb közös osztó a lehető legnagyobb szám, amelyre ez lehetséges. Például a 24-szer 60-as téglalap felosztható a következő méretű négyzetekre: 1, 2, 3, 4, 6 és 12 oldalhosszúakra, amelyek közül a legnagyobb a 12. Ekkor az egyik oldal irányában 2, a másik irányában 5 négyzet van.

A legnagyobb közös osztó a prímtényezős felbontásból is megállapítható, mert a közös prímtényezők összeszorzásával állítható elő, ahol is a kitevő a két szám kanonikus alakjában szereplő minimális kitevő.{{refhely|Schroeder 2005|21–22. o.}} Például 1386 = 2 × 3 × 3 × 7 × 11, és 3213 = 3 × 3 × 3 × 7 × 17, legnagyobb közös osztójuk 63 = 3 × 3 × 7. Ha a számoknak nincsenek közös prímtényezőik, akkor relatív prímek, legnagyobb közös osztójuk 1.
A prímtényezős felbontás megtalálása nehéz, amit a [[kriptográfia]] ki is használ.{{refhely|Schroeder 2005|216–219. o.}} Az euklideszi algoritmusnak az az előnye, hogy enélkül képes meghatározni a legnagyobb közös osztót.{{refhely|Schroeder 2005|19. o.}}<ref>{{cite book | last1 = Ogilvy | first1 = C. S. | author1-link = C. Stanley Ogilvy | last2 = Anderson | first2 = J. T. | year = 1966 | title = Excursions in number theory | url = https://archive.org/details/excursionsnumber00ogil | publisher = [[Oxford University Press]] | location = New York | pages = [https://archive.org/details/excursionsnumber00ogil/page/n30 27]–29}}</ref>

A legnagyobb közös osztó egy másik definíciója a felsőbb matematikában, közelebbről a [[Gyűrű (matematika)|gyűrűelméletben]] hasznos.{{refhely|LeVeque 1996|33. o.}} Két, nullától különböző egész szám legnagyobb közös osztója a legkisebb, egész együtthatókkal előállítható lineáris kombinációjuk; azaz, ''a'' és ''b'' legnagyobb közös osztója felírható, mint ''ua'' + ''vb'', ahol ''u'' és ''v'' akár negatív egészek. Ez a Bézout-lemma. Az összes lineáris kombináció a legnagyobb közös osztó többszöröse. Ezek a legnagyobb közös osztó által generált [[főideál]] elemei, amely így megegyezik az ''a'' és a ''b'' által generált ideállal. Következik, hogy az egészek minden ideálja főideál. Egyes tulajdonságok könnyebben láthatók ezzel, például hogy ''a'' és ''b'' minden közös osztója ''g''-nek is osztója, hiszen ''ua'' + ''vb'' mindkét tagjának osztója.

Három vagy több szám legnagyobb közös osztója a prímtényezős felbontásból is megállapítható, mert a közös prímtényezők összeszorzásával állítható elő, ahol is a kitevő a számok kanonikus alakjában szereplő minimális kitevő.{{refhely|Stark 1978|25. o.}} Kiszámítható úgy is, hogy először vesszük két szám legnagyobb közös osztóját, majd ezt a két számot a legnagyobb közös osztójukkal helyettesítve ezt addig ismételjük, amíg egyetlen szám nem marad.{{refhely|Ore 1948|47–48. o.}} A legnagyobb közös osztó szimmetrikus és asszociatív.
:lnko(a, b, c) = lnko(a, lnko(b, c)) = lnko(lnko(a, b), c) = lnko(lnko(a, c), b).
Emiatt az euklideszi algoritmussal nemcsak két, hanem akárhány, de véges sok szám legnagyobb közös osztója is kiszámítható.

== Formális leírása ==
Az euklideszi algoritmus egymást követő lépései az előző lépés eredményéből indulnak ki.
A lépéseket a ''k'' index számolja nullától kezdődően. Így a kezdőlépés a ''k'' = 0, a következő lépés a ''k'' = 1 indexet használja, és így tovább.

Minden lépés az ''r''<sub>''k''−1</sub> és ''r''<sub>''k''−2</sub> maradékokat használja. Mivel a maradékok folyamatosan csökkennek, azért ''r''<sub>''k''−1</sub> kisebb, mint ''r''<sub>''k''−2</sub>. A cél az, hogy találjunk egy ''q''<sub>''k''</sub> hányadost és egy ''r''<sub>''k''</sub> maradékot, amellyel az
:<math>r_{k-2} = q_k r_{k-1} + r_k</math>
egyenlőség teljesül. Szavakkal, a nagyobb ''r''<sub>''k''−2</sub> számból a kisebb ''r''<sub>''k''−1</sub> többszöröseit vonja le, amíg egy még kisebb ''r''<sub>''k''</sub> számhoz nem jut.

A (''k''&nbsp;=&nbsp;0) kezdőlépésben az ''r''<sub>−2</sub> és ''r''<sub>−1</sub> számok megfeleltethetők a kiindulási számoknak. A következő lépésben (''k''&nbsp;=&nbsp;1) a kisebb kezdőszám és a nulladik lépésben kapott ''r''<sub>0</sub> maradékot használja, és így tovább. Így az algoritmus írható mint az

:<math>\begin{align}
a &= q_0 b + r_0 \\
b &= q_1 r_0 + r_1 \\
r_0 &= q_2 r_1 + r_2 \\
r_1 &=q_3 r_2 + r_3 \\
&\dotsb
\end{align}</math>

egyenlőségek sorozata.

Ha a kisebb szám az ''a'', akkor az első lépésben az algoritmus felcseréli a számokat. Például, ha ''a''&nbsp;<&nbsp;''b'', akkor az első ''q''<sub>0</sub> hányados nulla lesz, és a maradék ''r''<sub>0</sub> = ''a''. Ettől kezdve az ''r''<sub>''k''</sub> maradék mindig kisebb lesz, mint az előző ''r''<sub>''k''−1</sub> maradék minden ''k''&nbsp;≥&nbsp;0 indexre.
Mivel a maradékok minden lépésben csökkennek, és sosem lehetnek negatívok, így előbb-utóbb lesz egy maradék, ''r''<sub>''N''</sub> = 0{{refhely|Stark 1978|18. o.}} Az utolsó nem nulla maradék lesz a legnagyobb közös osztó. Az ''N'' nem lehet végtelen, mert csak véges sok egész van a nulla és az első ''r''<sub>0</sub> maradék között.
=== Bizonyítás ===
Az algoritmus érvényessége két lépésben bizonyítható.{{refhely|Stark 1978|16-20. o.}}

Első lépésként lássuk be, hogy az algoritmus véges sok lépés után véget ér. Ennek főleg gyakorlati szempontok miatt van szerepe. Mivel az [[maradékos osztás|euklideszi osztás]] során a maradék kisebb, mint az osztó [[abszolút érték]]e, a maradékok szigorúan monoton csökkenő sorozatot alkotnak a természetes számok halmazában, így a sorozat utolsó tagja biztosan nulla, mivel két különböző természetes szám különbsége nem lehet kisebb 1-nél (természetesen az abszolút értékét tekintve):
:<math> |b|>r_0>r_1>r_2>...>r_n\geq0</math>

A következő lépés, hogy bebizonyítjuk: az utolsó maradék közös osztó. Ehhez alulról felfelé haladunk az eljárásban:
* <math>r_{n-1}=q_nr_n</math>
* <math>r_{n-2}=q_{n-1}r_{n-1}+r_n=\left(q_{n-1}q_n+1\right)r_n</math>
* <math>r_{n-3}=q_{n-2}r_{n-2}+r_{n-1}</math>
* <math>\dots</math>
Mivel <math>r_n</math> osztója <math>r_{n-2}</math>-nek és <math>r_{n-1}</math>-nek is, ezért a [[lineáris kombináció]]juknak is. Az eljárást végigkövetve kapjuk, hogy <math>r_n|a</math> és <math>r_n|b</math>.{{refhely|Knuth 1997|320. o.}}<ref name="Lovasz_2003">{{cite book | last1 = Lovász |first1=L.|author1-link=László Lovász|last2= Pelikán|first2=J.|last3=Vesztergombi|first3= K. | year = 2003 | title = Discrete Mathematics: Elementary and Beyond | publisher = Springer-Verlag | location = New York | isbn = 0-387-95584-4 | pages = 100–101}}</ref>

Végül bizonyítjuk a maximalitást. Ennek során kihasználjuk azt a tényt, hogy a közös osztók egy szigorúan monoton növekvő természetes számsort alkotnak, amelynek felső határa <math>min(a,b)</math>, valamint hogy a lánc minden tagja osztója az utána következőnek. Tegyük fel, hogy a legnagyobb közös osztó <math>x</math>. Ekkor, mivel <math>r_n</math> is közös osztó, <math>r_n|x</math>. Viszont, mivel a közös osztók osztói a két szám lineáris kombinációinak is, így a lánc elemeire felírva kapjuk:
* <math>x|r_0=a-q_1b</math>.
* <math>x|r_1=b-q_2r_0</math>
* <math>x|r_2=r_0-q_3r_1</math>
* <math>\dots</math>
* <math>x|r_n=r_{n-2}-q_nr_{n-1}</math>.
Mivel a feltételünk az volt, hogy <math>r_n</math> osztója <math>x</math>-nek, ezért az oszthatóság definíciója miatt <math>x=r_n</math>. QED

=== Példa ===
[[Fájl:Euclidean algorithm 1071 462.gif|fennjobbra|bélyegkép|alt=Animáció, amely egyre kisebb négyzetekkel fed le egy téglalapot. |Az euklideszi algoritmus megjelenítése. A kiindulási téglalap méretei ''a''&nbsp;=&nbsp;1071 és ''b''&nbsp;=&nbsp;462. Az első két négyzet mérete 462×462, és a kimaradó téglalapé 462×147. Ezt 147×147 négyzetekkel fedi, amíg ki nem marad egy 21×147-es téglalap, amelyet 21×21 négyzetek teljesen lefednek. A legkisebb méret, 21, az 1071 és 462 legnagyobb közös osztója]]

A 360 és a 225 legnagyobb közös osztójának meghatározása az euklideszi algoritmussal:

:<math>360=225\cdot 1+135 \,</math>
:<math>225=135\cdot 1+90 \,</math>
:<math>135=90\cdot 1+45 \,</math>
:<math>90=45\cdot 2+0 \,</math>

Tehát a legnagyobb közös osztó a 45.

Az ''a'' = 1071 és ''b'' = 462. Először 1071-ből levonogatjuk 462-t, amíg annál kisebb számot nem kapunk. Kétszer kell levonnunk, és marad 147:
:1071 = 2 × 462 + 147.

Most 462-ből vonogatjuk ki 147 többszöröseit, és marad 21:
:462 = 3 × 147 + 21.

Ezután 21-et vonogatunk le 147-ből, és a maradék 0 lesz:
:147 = 7 × 21 + 0.

Mivel az utolsó maradék nulla, azért az algoritmus szerint a legnagyobb közös osztó a 21. Ez megegyezik azzal, amit prímtényezős felbontással találhatunk. Táblázattal:

{| class="wikitable" id="basic_Euclidean_algorithm" style="margin-left:auto; margin-right:auto; text-align:center"
!''k''!!Egyenlet!!Hányados és maradék
|-
| 0 || {{math|1=1071 = ''q''<sub>0</sub> 462 + ''r''<sub>0</sub>}} || {{math|1=''q''<sub>0</sub> = 2 és ''r''<sub>0</sub> = 147}}
|-
| 1 || {{math|1=462 = ''q''<sub>1</sub> 147 + ''r''<sub>1</sub>}} || {{math|1=''q''<sub>1</sub> = 3 és ''r''<sub>1</sub> = 21}}
|-
| 2 || {{math|1=147 = ''q''<sub>2</sub> 21 + ''r''<sub>2</sub>}} || {{math|1=''q''<sub>2</sub> = 7 és ''r''<sub>2</sub> = 0}}; az algoritmus befejeződik
|}

=== Megjelenítése ===
Az algoritmus megjeleníthető a legnagyobb közös osztó fent részletezett tulajdonsága alapján.<ref name="Kimberling_1983">{{cite journal | last = Kimberling|first= C.|authorlink=Clark Kimberling | year = 1983 | title = A Visual Euclidean Algorithm | url = https://archive.org/details/sim_mathematics-teacher_1983-02_76_2/page/108| journal = Mathematics Teacher | volume = 76 | pages = 108–109}}</ref> Az ''a'' × ''b'' méretű téglalapot megpróbáljuk lefedni a kisebb számnak megfelelő méretű négyzetekkel, amelyből a kisebb szám × ''r''<sub>0</sub> méretű téglalap marad. Ezután ezt ''r''<sub>0</sub> méretű négyzetekkel, majd a kimaradt területet ''r''<sub>1</sub> méretű négyzetekkel próbáljuk lefedni, és így tovább. Ha az összes területet lefedte, akkor az algoritmus véget ér, és a legkisebb méretű négyzet mérete lesz a legnagyobb közös osztó.

=== Az osztásos módszer ===
Az osztásos módszerben a maradékos osztás definíciója alapján vannak olyan számok, hogy ''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>, ahol a maradék szigorúan kisebb, mint az osztó. A maradék és a hányados egyértelmű.{{refhely|Cohn 1962|104–110. o.}}

Az osztásos módszer csökkenti a lépések számát. Ha nem akarjuk kifejezni a legnagyobb közös osztót lineáris kombinációként, akkor nincs szükség a hányadosokra. Ezzel egy lépés alakja:
''r''<sub>''k''</sub> = ''r''<sub>''k''−2</sub> mod ''r''<sub>''k''−1</sub>.

=== Az abszolút értékben legkisebb maradék módszere ===
Ebben a módszerben az algoritmus minden lépésben eggyel növeli a hányadost, ha a negatív maradék abszolút értéke kisebb, mint a pozitív maradék.{{refhely|Ore 1948|43. o.}}<ref name="Stewart_1964">{{cite book | last = Stewart|first= B. M. | year = 1964 | title = Theory of Numbers | url = https://archive.org/details/theorynumbers00stew| edition = 2nd | publisher = Macmillan | location = New York | pages = [https://archive.org/details/theorynumbers00stew/page/n53 43]–44 | lccn = 64010964}}</ref> Az általános algoritmus felteszi, hogy az
:''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>
egyenletben |r<sub>k−1</sub>| > r<sub>k</sub> > 0. Ezzel szemben kiszámítható egy negatív maradék is:
:''r''<sub>''k''−2</sub> = (''q''<sub>''k''</sub> + 1) ''r''<sub>''k''−1</sub> + ''e''<sub>''k''</sub>
ha ''r''<sub>''k''−1</sub>&nbsp;>&nbsp;0, vagy
:=''r''<sub>''k''−2</sub> = (''q''<sub>''k''</sub> − 1) ''r''<sub>''k''−1</sub> + ''e''<sub>''k''</sub>,
ha ''r''<sub>''k''−1</sub>&nbsp;<&nbsp;0.

Ha ''r''<sub>''k''</sub> helyett az algoritmus ''e''<sub>''k''</sub>-t veszi, ha |e<sub>k</sub>| < |''r''<sub>''k''</sub>|, akkor teljesülni fog, hogy:
|''r''<sub>''k''</sub>| ≤ |''r''<sub>''k''−1</sub>| / 2

[[Leopold Kronecker]] belátta, hogy az összes változat közül ennek a lépésszáma a legkisebb,{{refhely|Ore 1948|43. o.}}<ref name="Stewart_1964" /> minden ''a'', ''b'' kiinduló számpárra akkor és csak akkor minimális a lépésszám, ha ''q''<sub>''k''</sub>-t úgy választja, hogy <math>\left |\frac{r_{k+1}}{r_k}\right |<\frac{1}{\varphi}\sim 0.618,</math>, ahol <math>\varphi</math> az [[aranymetszés]].<ref>{{cite journal|last=Lazard|first=D.|year=1977|title=Le meilleur algorithme d'Euclide pour ''K''[''X''] et '''Z'''|journal=Comptes Rendus Acad. Sci. Paris|volume=284|pages=1–4}}</ref>

== Bonyolultsága ==
[[Fájl:Euclidean Algorithm Running Time.svg|bélyegkép|alt="Színes egyenesek indulnak ki sugarasan az ''x''-''y'' koordinátarendszer origójából. Az egyes egyenesek azokat a pontokat tartalmazzák, amelyeknek ugyanannyi lépésszámra van szükségük az algoritmus befejezéséhez."|Az euklideszi algoritmus lépéseinek száma az lnko(''x'',''y'') kiszámítására. A piros és sárga pontok kevés, a kék és a lila pontok sok lépést jeleznek. A legsötétebb egyenes az ''y'' = Φ''x'', vonalát követik, ahol Φ az [[aranymetszés]].]]

* Az algoritmus a leggyorsabban akkor ér véget, ha <math>b|a</math>.
* Az algoritmus a szomszédos [[Fibonacci-számok]] esetén rendkívül lassú, ennek oka, hogy végigfut visszafelé a teljes sorozaton. A sorozat ugyanis szigorúan monoton növekvő, valamint a definíció szerint
:<math>a_n=a_{n-1}+a_{n-2}</math>
:ami megfelel a maradékos osztás definíciójának. Ez Émile Léger eredménye (1837).<ref name="Shallit" />

* Szakaszok esetén is értelmezhető a [[maradékos osztás]], így az euklideszi algoritmus is elvégezhető. Itt azonban nem tudjuk biztosítani az eljárás véges hosszát. Ha ez teljesül, akkor a két szakasz '''összemérhető'''.

Az algoritmus bonyolultságát alaposan áttanulmányozták{{refhely|Knuth 1997|339–364. o.}} Az algoritmusok bonyolultságát a megtett lépések számával mérik. Mivel az egyes lépések végrehajtási ideje különböző, ezért számításba veszik, hogy például az osztás mennyivel lassabb a kivonásnál. Valójában többnyire csak a nagyságrend érdekes, mert lényeges, hogy a számítási kapacitás növelésével mennyivel nagyobb feladat oldható meg az adott algoritmussal.

Az euklideszi algoritmus bonyolultságát először A.-A.-L. Reynaud elemezte. 1811-ben megmutatta, hogy a lépések számának felső korlátja a kisebb bemenő szám. Ha a számok ''a'', ''b'', és ''b'' < ''a'', akkor a korlát ''b''. Később jobb becslést is adott: ''b''/2 + 2.,<ref>{{cite book | last = Reynaud |first=A.-A.-L. | year = 1811 | title = Traité d'arithmétique à l'usage des élèves qui se destinent à l'École Polytechnique | edition = 6th | publisher = Courcier | location = Paris | at = Note 60, p.&nbsp;34 }} As cited by {{harvtxt|Shallit|1994}}.</ref> P.-J.-E. Finck 1841-ben megmutatta, hogy az osztások száma legfeljebb <math>2\ \log_2 b + 1</math>,<ref>{{cite book | last = Finck | first = P.-J.-E. | title = Traité élémentaire d'arithmétique à l'usage des candidats aux écoles spéciales | publisher = Derivaux | year = 1841}}</ref> így az algoritmus polinomiális a bemenet méretében.<ref name="Shallit">{{cite journal | authorlink = Jeffrey Shallit|last=Shallit|first=J. | year = 1994 | title = Origins of the analysis of the Euclidean algorithm | journal = Historia Math. | volume = 21 | pages = 401–419 | doi=10.1006/hmat.1994.1031|ref=harv}}</ref>
Ezt 1844-ben Gabriel Lamé finomította azzal,<ref>{{cite journal | authorlink = Gabriel Lamé|last=Lamé|first=G. | year = 1844 | title = Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers | journal = Comptes Rendus Acad. Sci. | volume = 19 | pages = 867–870}}</ref> hogy a lépések száma soha nem nagyobb, mint a kisebb szám tízes számrendszerbeli jegyeinek számának ötszöröse.<ref>{{cite journal | last = Grossman | first = H. | year = 1924 | title = On the Number of Divisions in Finding a G.C.D | url = https://archive.org/details/sim_american-mathematical-monthly_1924-11_31_9/page/443 | journal = The American Mathematical Monthly | volume = 31 | page = 443 | doi = 10.2307/2298146 | jstor = 2298146 | issue = 9}}</ref><ref>{{cite book | last = Honsberger | first = R. | authorlink = Ross Honsberger | year = 1976 | title = Mathematical Gems II | publisher = The [[Mathematical Association of America]] | isbn = 0-88385-302-7 | pages = 54–57}}</ref>

Az egységes költség modellben Lamé eredménye szerint a költség ''O''(''h''); ám ha a számok nagyok, akkor nem hanyagolható el, hogy a maradékképzés drágább, mint az osztás, így az algoritmus költsége egy nagyságrendet nő, ''O''(''h''<sup>2</sup>) lesz.{{refhely|Knuth 1997|257-261. o.}} Ekkor a lépésszámra egy [[teleszkopikus összeg]]et kaphatunk, amely szintén ezt a becslést adja. A modern gyors egészszorzásos [[Schönhage–Strassen algoritmus]]sal felgyorsítható, így az algoritmus [[kvázilineáris]] lehet.{{refhely|Crandall-Pomerance 2001|77–79, 81–85, 425–431. o.}}<ref name="Moller08"/>
=== A lépések száma ===
Két természetes szám, ''a'' és ''b'' legnagyobb közös osztójának kiszámításához szükséges lépések számát ''T''(''a'',&nbsp;''b'') jelöli.{{refhely|Knuth 1997|344. o.}} Ha ''a'' és ''b'' legnagyobb közös osztója ''g'', akkor ''a''&nbsp;=&nbsp;''mg'', ''b''&nbsp;=&nbsp;''ng'', és az ''n'' és ''m'' természetes számok relatív prímek. Ekkor
:''T''(''a'', ''b'') = ''T''(''m'', ''n'')
ami belátható, ha az algoritmusban mindenütt végigosztunk ''g''-vel.{{refhely|Ore 1948|45. o.}} Hasonló teljesül, ha végigszorzunk egy közös tényezővel:
: ''w'': ''T''(''a'', ''b'') = ''T''(''wa'', ''wb'').
Így a ''T'' lépésszám erősen hullámzik a szomszédos számpárok között, a legnagyobb közös osztó méretétől függően.

Az euklideszi algoritmus rekurzív természete miatt
:''T''(''a'', ''b'') = 1 + ''T''(''b'', ''r''<sub>0</sub>) = 2 + ''T''(''r''<sub>0</sub>, ''r''<sub>1</sub>) = … = ''N'' + ''T''(''r''<sub>''N''−2</sub>, ''r''<sub>''N''−1</sub>) = ''N'' + 1
ahonnan ''T''(''x'', 0)&nbsp;=&nbsp;0.{{refhely|Knuth 1997|344. o.}}

=== A legrosszabb eset ===
Ha az algoritmus egy ''a''&nbsp;>&nbsp;''b''&nbsp;>&nbsp;0 számpárra ''N'' lépést tesz meg, akkor a legkisebb ilyen számpár a [[Fibonacci-sorozat]] két szomszédos tagja, ''F''<sub>''N''+2</sub> és ''F''<sub>''N''+1</sub>.{{refhely|Knuth 1997|343. o.}} Ez teljes indukcióval látható be.{{refhely|Mollin 2008|21. o.}} Ha ''N''&nbsp;=&nbsp;1, akkor ''b'' osztója ''a''-nak.{{refhely|Mollin 2008|21. o.}} A legkisebb ilyen pozitív számpár ''b''&nbsp;=&nbsp;1 és ''a''&nbsp;=&nbsp;2, amelyek rendre megegyeznek ''F''<sub>2</sub>-vel és ''F''<sub>3</sub>-mal.

Most tegyük fel, hogy az állítás már be van bizonyítva minden ''N''-re egészen ''M''&nbsp;−&nbsp;1-ig. Az első lépés ''a''&nbsp;=&nbsp;''q''<sub>0</sub>''b''&nbsp;+&nbsp;''r''<sub>0</sub>, és a második ''b''&nbsp;=&nbsp;''q''<sub>1</sub>''r''<sub>0</sub>&nbsp;+&nbsp;''r''<sub>1</sub>. Az algoritmus rekurzív természete miatt ''M''&nbsp;−&nbsp;1 lépés kell lnko(''b'',&nbsp;''r''<sub>0</sub>) megtalálásához, és legkisebb értékük ''F''<sub>''M''+1</sub> és ''F''<sub>''M''</sub>. Emiatt ''a'' legkisebb lehetséges értéke ''q''<sub>0</sub>&nbsp;=&nbsp;1, innen ''a''&nbsp;=&nbsp;''b''&nbsp;+&nbsp;''r''<sub>0</sub>&nbsp;=&nbsp;''F''<sub>''M''+1</sub>&nbsp;+&nbsp;''F''<sub>''M''</sub>&nbsp;=&nbsp;''F''<sub>''M''+2</sub>. Ezt a bizonyítást [[Gabriel Lamé]] adta 1844-ben, ami a [[bonyolultságelmélet]] kezdetét jelenti,{{refhely|LeVeque 1996|35. o.}} továbbá az első példa a Fibonacci-számok gyakorlati felhasználására.{{refhely|Knuth 1997|343. o.}}

Az eredményből az is következik, hogy a lépések száma nem haladhatja meg a kisebb szám tízes számrendszerbeli számjegyeinek számának ötszörösét.{{refhely|Mollin 2008|21–22. o.}} Ha az algoritmus ''N'' lépést tesz meg, akkor ''b'' legalább ''F''<sub>''N''+1</sub>, amelynek alsó becslése ''φ''<sup>''N''−1</sup>, ahol ''φ'' az aranymetszés. Mivel ''b''&nbsp;≥&nbsp;''φ''<sup>''N''−1</sup>, azért ''N''&nbsp;−&nbsp;1&nbsp;≤&nbsp;log<sub>''φ''</sub>''b''. Mivelhogy log<sub>10</sub>''φ''&nbsp;>&nbsp;1/5, (''N''&nbsp;−&nbsp;1)/5&nbsp;<&nbsp;log<sub>10</sub>''φ''&nbsp;log<sub>''φ''</sub>''b''&nbsp;=&nbsp;log<sub>10</sub>''b''. Ezért ''N''&nbsp;≤&nbsp;5&nbsp;log<sub>10</sub>''b''. Tehát az euklideszi algoritmus mindig legfeljebb ''O''(''h'') osztást igényel, ahol ''h'' a kisebb szám jegyeinek száma.

=== Átlagos lépésszám ===
Az átlagos lépésszám többféleképpen is definiálható. Az egyik definíció szerint a ''T''(''a'') átlagos időt úgy mérjük, hogy az ''a'' számhoz a nála kisebb pozitív egészekkel vett legnagyobb közös osztó kiszámításához szükséges időket átlagoljuk.{{refhely|Knuth 1997|344. o.}}

:<math>T(a) = \frac{1}{a} \sum_{0 \leq b<a} T(a, b).
</math>

Azonban, mivel ''T''(''a'',&nbsp;''b'') erősen változik a legnagyobb közös osztóval együtt, a ''T''(''a'') függvény is ennek megfelelően zajos.{{refhely|Knuth 1997|353. o.}} Emiatt vezették be azt az átlagot, amely csak a relatív prímekkel számol:

:<math>\tau(a) = \frac{1}{\varphi(a)} \sum_{\begin{smallmatrix} 0 \leq b<a \\ \gcd(a, b) = 1 \end{smallmatrix}} T(a, b).
</math>

Az ''a''-nál kisebb relatív prímek száma ''φ''(''a''), ahol ''φ'' az [[Euler-függvény]]. Ez már elég jól becsülhető:{{refhely|Knuth 1997|357. o.}}<ref>{{cite journal | last = Tonkov | first= T. | year = 1974 | title = On the average length of finite continued fractions | journal = Acta Arithmetica | volume = 26 | pages = 47–57}}</ref>

:<math>\tau(a) = \frac{12}{\pi^{2}}\ln 2 \ln a + C + O(a^{-1/6-\epsilon})</math>

A hibatag ''a''<sup>−(1/6) + ε</sup>, ahol ε tetszőlegesen kicsi. A képletben a ''C'' (''Porter-konstans''<ref>{{mathworld|id=PortersConstant|title=Porter's Constant}}</ref>):
:<math>C= -\frac{1}{2} + \frac{6 \ln 2}{\pi^{2}}(4\gamma -24\pi^{2}\zeta'(2) + 3\ln 2 - 2) \approx 1.467</math>

ahol γ az Euler–Mascheroni-konstans és ζ' a Riemann-féle zétafüggvény deriváltja.<ref>{{cite journal | last = Porter | first = J. W. | year = 1975 | title = On a Theorem of Heilbronn | journal = Mathematika | volume = 22 | pages = 20–28 | doi = 10.1112/S0025579300004459}}</ref><ref>{{cite journal | last = Knuth|first = D. E. | authorlink = Donald Knuth | year = 1976 | title = Evaluation of Porter's Constant | url = https://archive.org/details/sim_computers-mathematics-with-applications_1976_2/page/137| journal = Computers and Mathematics with Applications | volume = 2 | pages = 137–139 | doi = 10.1016/0898-1221(76)90025-0 | issue = 2}}</ref> A főegyüttható, (12/π<sup>2</sup>) ln 2 két, egymástól független módszerrel határozható meg.<ref>{{cite journal | last = Dixon | first = J. D. | year = 1970 | title = The Number of Steps in the Euclidean Algorithm | journal = J. Number Theory | volume = 2 | pages = 414–422 | doi = 10.1016/0022-314X(70)90044-2 | issue = 4|bibcode = 1970JNT.....2..414D }}</ref><ref>{{cite book | last = Heilbronn | first = H. A. | authorlink = Hans Heilbronn | year = 1969 | chapter = On the Average Length of a Class of Finite Continued Fractions | title = Number Theory and Analysis | editor = Paul Turán | publisher = Plenum | location = New York | pages = 87–96 | lccn = 76016027}}</ref>

Az első átlagfüggvény az ''a'' szám osztóinak tau átlagával számítható ki:{{refhely|Knuth 1997|354. o.}}
:<math> T(a) = \frac{1}{a} \sum_{d \mid a} \varphi(d) \tau(d)
</math>

és a következőképpen approximálható:<ref name="Norton_1990">{{cite journal | last = Norton | first = G. H. | year = 1990 | title = On the Asymptotic Analysis of the Euclidean Algorithm | journal = Journal of Symbolic Computation | volume = 10 | pages = 53–58 | doi = 10.1016/S0747-7171(08)80036-3}}</ref>

:<math>T(a) \approx C + \frac{12}{\pi^{2}} \ln 2 \left(\ln a - \sum_{d \mid a} \frac{\Lambda(d)}{d}\right)</math>

ahol Λ(''d'') a [[von Mangoldt-függvény]].{{refhely|Knuth 1997|355. o.}}

A harmadik átlag az ''Y''(''n''), amely a várható lépésszámot adja meg, ha a két számot az 1-től ''n''-ig terjedő számok közül egyenletes valószínűséggel sorsolják.<ref name="Norton_1990" />

:<math>Y(n) = \frac{1}{n^{2}} \sum_{a=1}^n \sum_{b=1}^n T(a, b) = \frac{1}{n} \sum_{a=1}^n T(a).
</math>

Behelyettesítve a ''T''(''a'')-ra vonatkozó approximációt adódik ''Y''(''n'') approximációja:
{{refhely|Knuth 1997|356. o.}}
:<math>Y(n) \approx \frac{12}{\pi^{2}} \ln 2 \ln n + 0.06.</math>

=== Lépésenkénti költség ===
Az algoritmus minden ''k''-adik lépésében a ''q''<sub>''k''</sub> hányados és az ''r''<sub>''k''</sub> maradékot számítja ki az ''r''<sub>''k''−2</sub> és ''r''<sub>''k''−1</sub> számokból kiindulva:

:''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>.

A költséget inkább a ''q''<sub>''k''</sub> hányados kiszámítása jelenti, mert a maradék gyorsan megkapható:

:''r''<sub>''k''</sub> = ''r''<sub>''k''−2</sub> − ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub>.

Két ''h'' bites szám osztásának költsége ''O''(''h''(''ℓ''+1)), ahol ''ℓ'' a hányados hossza.{{refhely|Knuth 1997|257-261. o.}}

Az eredeti, kivonásos módszer lassabb lehet. Az osztás eredményét adódó hányados az a szám, ahányszor ki kell vonni a kisebb számot a nagyobból, hogy a számok szerepet cseréljenek. Ha a hányados nagy, akkor sok kivonásra van szükség. Másrészt azonban a hányados általában kicsi marad. Annak a valószínűsége, hogy egy adott ''q'' szám hányados, megközelítőleg ln|''u''/(''u''&nbsp;−&nbsp;1)|, ahol ''u''&nbsp;=&nbsp;(''q''&nbsp;+&nbsp;1)<sup>2</sup>.{{refhely|Knuth 1997|352. o.}} Például annak a valószínűsége, hogy a hányados 1, 2, 3 vagy 4, rendre 41,5%, 17,0%, 9,3% és 5,9%. Azonban a kivonás gyorsabban elvégezhető, mint az osztás, különösen a nagy számok esetén,<ref>{{cite book | last = Wagon | first = S. | authorlink = Stan Wagon | year = 1999 | title = Mathematica in Action | url = https://archive.org/details/mathematicaactio00wago_723 | publisher = Springer-Verlag | location = New York | isbn = 0-387-98252-3 | pages = [https://archive.org/details/mathematicaactio00wago_723/page/n359 335]–336}}</ref> így a kivonásos módszer versenyképes az osztásossal.{{refhely|Cohen 1993|14. o.}}

Kombinálva a lépésszámok becslését a lépésenkénti becsült számításigénnyel belátható, hogy az euklideszi algoritmus kvadratikusan nő a jegyek átlagos számában (''h''<sup>2</sup>). Reprezentálják ''h''<sub>0</sub>, :''h''<sub>1</sub>, …, ''h''<sub>''N''−1</sub> az ''r''<sub>0</sub>,&nbsp;''r''<sub>1</sub>,&nbsp;…,&nbsp;''r''<sub>''N''−1</sub> maradékok jegyeinek számát! Mivel a lépések ''N'' száma lineárisan nő ''h''-val, a futási idő korlátja:
:<math>
O\Big(\sum_{i<N}h_i(h_i-h_{i+1}+2)\Big)\subseteq O\Big(h\sum_{i<N}(h_i-h_{i+1}+2)\Big)\subseteq O(h(h_0+2N))\subseteq O(h^2).</math>

== Alternatív módszerek ==
Egyszerűsége miatt az euklideszi algoritmus széles körben használt, különösen kis számokra.<ref>{{cite book
 | last = Sorenson | first = Jonathan P.
 | contribution = An analysis of the generalized binary GCD algorithm
 | mr = 2076257
 | pages = 327–340
 | publisher = American Mathematical Society | location = Providence, RI
 | series = Fields Institute Communications
 | title = High primes and misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams
 | volume = 41
 | year = 2004
 | url = https://books.google.com/books?id=udr3tHHwBl0C&pg=PA327
 | quote = The algorithms that are used the most in practice today [for computing greatest common divisors] are probably the binary algorithm and Euclid's algorithm for smaller numbers, and either Lehmer's algorithm or Lebealean's version of the ''k''-ary GCD algorithm for larger numbers.}}</ref> Alternatívái nála sokkal lassabbak lehetnek.

Egy jóval kevésbé hatékony módszer a legnagyobb közös osztó megtalálására a két szám közös osztóinak meghatározása szitálással. Ezek közül a legnagyobb lesz a legnagyobb közös osztó. A szitálás 2-től indul, és a kisebb számig tart. Ez lineárisan nő a kisebb számmal, vagyis exponenciálisan a jegyek számában. Hasonlóan kevéssé hatékony a prímtényezős felbontáson alapuló módszer.{{refhely|Schroeder 2005|21–22. o.}} A prímtényezős felbontás megtalálását faktorizálásnak nevezik, és kevéssé hatékony, emiatt kriptográfiai módszereket is alapoznak rá.{{refhely|Schroeder 2005|216–219. o.}}

A [[bináris legnagyobb közös osztó algoritmus]] kihasználja, hogy a számítógépek kettes számrendszerben számolnak; így az osztás helyettesíthető gyorsabb műveletekkel.{{refhely|Knuth 1997|321-323. o.}}<ref>{{cite journal | last = Stein | first = J. | year = 1967 | title = Computational problems associated with Racah algebra | journal = Journal of Computational Physics | volume = 1 | pages = 397–405 | doi = 10.1016/0021-9991(67)90047-2 | issue = 3| bibcode = 1967JCoPh...1..397S }}</ref> Ennek a műveletigénye szintén ''O''(''h''²). Mindazonáltal a gyorsabb műveletek miatt gyorsabban fut, mint az euklideszi algoritmus, azonban ugyanúgy skálázódik.{{refhely|Crandall-Pomerance 2001|77–79, 81–85, 425–431. o.}} A hatékonyság tovább javítható, ha a számoknak csak az első jegyét tekintik.{{refhely|Knuth 1997|1328. o.}}<ref>{{cite journal | last = Lehmer|first = D. H.|authorlink=Derrick Henry Lehmer | year = 1938 | title = Euclid's Algorithm for Large Numbers | journal = The American Mathematical Monthly | volume = 45 | pages = 227–233 | doi = 10.2307/2302607 | jstor = 2302607 | issue = 4}}</ref> Az algoritmus más számrendszerekre is kiterjeszthető, amivel a sebesség ötszörösére növelhető.<ref>{{cite journal | last = Sorenson |first=J. | year = 1994 | title = Two fast GCD algorithms | journal = J. Algorithms | volume = 16 | pages = 110–144 | doi = 10.1006/jagm.1994.1006}}</ref> Lehmer legnagyobb közös osztó algoritmusa ugyanezen az elven alapul, de bármely számrendszerben működik.

Nagyon nagy egészekre (egészen 25 ezer jegyig) rekurzív megközelítésekkel kvázilineáris sebesség érhető el.<ref>{{cite book | last1 = Aho|first1= A.|author1-link=Alfred Aho|last2= Hopcroft|first2= J.|author2-link=John Hopcroft|last3=Ullman|first3=J.|author3-link=Jeffrey Ullman | year = 1974 | title = The Design and Analysis of Computer Algorithms | url = https://archive.org/details/designanalysisco00ahoa_502| publisher = Addison–Wesley | location = New York | pages = [https://archive.org/details/designanalysisco00ahoa_502/page/n309 300]–310 | isbn = 0-201-00029-6}}</ref> Ezek közé tartoznak Schönhage,<ref>{{cite journal | last = Schönhage|first= A. |authorlink=Arnold Schönhage| title = Schnelle Berechnung von Kettenbruchentwicklungen | journal = Acta Informatica | volume = 1 | pages = 139–144 | doi = 10.1007/BF00289520 | year = 1971 | issue = 2}}</ref><ref>{{cite book | last = Cesari|first= G. | year = 1998 | chapter = Parallel implementation of Schönhage's integer GCD algorithm | title = Algorithmic Number Theory: Proc. ANTS-III, Portland, OR | editor = G. Buhler | publisher = Springer-Verlag | location = New York | pages = 64–76|volume=1423|series=Lecture notes in Computer Science}}</ref> és Stehlé és Zimmermann módszere.<ref>{{cite book | last1 = Stehlé|first1=D.|last2=Zimmermann|first2=P. | year = 2005 | chapter = [[Gal's accurate tables]] method revisited | title = Proceedings of the 17th IEEE Symposium on Computer Arithmetic (ARITH-17) | publisher = [[IEEE Computer Society Press]] | location = Los Alamitos, CA}}</ref> Ezek az euklideszi algoritmus mátrixos alakját használják fel. Sebességük ''O''(''h'' (log ''h'')<sup>2</sup> (log log ''h'')).{{refhely|Crandall-Pomerance 2001|77–79, 81–85, 425–431. o.}}<ref name="Moller08">{{cite journal | last = Möller|first= N. | title = On Schönhage's algorithm and subquadratic integer gcd computation | journal = Mathematics of Computation | volume = 77 | pages = 589–607 | doi = 10.1090/S0025-5718-07-02017-0 | year = 2008 | url=http://www.lysator.liu.se/~nisse/archive/sgcd.pdf | issue = 261| bibcode = 2008MaCom..77..589M }}</ref>

== Programkód ==
=== [[C (programozási nyelv)|C]]-ben ===
<syntaxhighlight lang="c">
#include <stdio.h>
int lnko(int a, int b){
    int temp;
    while(b>0){
        temp = b;
        b = a%b;
        a = temp;
    }
    return a;
}
int main(void){
    int s1, s2;

    printf("szam1 szam2: ");
    scanf("%d %d", &s1, &s2);

    printf("lnko(%d, %d)=%d", s1, s2, lnko(s1, s2));
    return 0;
}
</syntaxhighlight>

A k-adik iterációban a ''b'' változó tartalmazza ''r''<sub>''k''−1</sub>-et, míg az ''a'' a megelőzőt, ''r''<sub>''k''−2</sub>-t. A b = a%b; lépés megfelel a fenti ''r''<sub>''k''</sub> ≡ ''r''<sub>''k''−2</sub> mod ''r''<sub>''k''−1</sub> formulának. A ''temp'' változó a ''r''<sub>''k''−1</sub> értékét tartalmazza az ''r''<sub>''k''</sub> kiszámítása közben. A ciklus végén ''b'' tartalmazza ''r''<sub>''k''</sub>-t, és ''a'' az előző maradékot, ''r''<sub>''k''−1</sub>-et.{{refhely|Knuth 1997|319–320. o.}}
=== Java nyelvű példa rekurzióval ===
Rekurzióval megvalósítva [[Java (programozási nyelv)|Java]] nyelven:
<syntaxhighlight lang="Java">
class GreaterCommonDivider {
    public static int gcd(int a, int b) {
        if(a%b == 0) {
            return b;
        } else {
            return gcd(b, a%b);
        }
    }

    public static void main(String args[]) {
        if(args.length != 2) {
            System.exit(1);
        }
        System.out.println( gcd( Integer.parseInt( args[0] ), Integer.parseInt( args[1] ) ) );
        System.exit(0);
    }
}
</syntaxhighlight>

A rekurzió azt használja ki,{{refhely|Stillwell 1997|14. o.}} hogy a maradékképzés során megmarad a legnagyobb közös osztó, és a megállási feltétel lnko(''r''<sub>''N''−1</sub>,&nbsp;0)&nbsp;=&nbsp;''r''<sub>''N''−1</sub>. Például az lnko(1071,&nbsp;462) kiszámítható azzal, hogy lnko(462,&nbsp;1071&nbsp;mod&nbsp;462)&nbsp;=&nbsp;lnko(462,&nbsp;147). Ez ugyanaz, mint lnko(147,&nbsp;462&nbsp;mod&nbsp;147)&nbsp;=&nbsp;lnko(147,&nbsp;21), azaz lnko(21,&nbsp;147&nbsp;mod&nbsp;21)&nbsp;=&nbsp;lnko(21,&nbsp;0)&nbsp;=&nbsp;21.

A kivonásos változatban maradékképzés helyett ismételt kivonás szerepel.{{refhely|Knuth 1997|319–320. o.}} Az osztásos módszerrel szemben ez csak pozitív számokra működik, és megáll, ha ''a'' = ''b''. Pszeudokódja:

 '''function''' gcd(a, b)
     '''while''' a ≠ b
         '''if''' a > b
            a := a − b;
         '''else'''
            b := b − a;
     '''return''' a;

Az ''a'' és ''b'' változók felváltva tárolják a maradékokat. Feltéve, hogy az elején az ''a'' a nagyobb, ''a'' = ''r''<sub>''k''−2</sub>, mivel ''r''<sub>''k''−2</sub> > ''r''<sub>''k''−1</sub>. Az adott iterációban az ''a'' változót az előző maradék többszöröseivel csökkenti, amíg ''a'' kisebbé nem válik, mint ''b''. Ekkor ''a'' = ''r''<sub>''k''</sub>, és a szerepek megcserélődnek, amivel az ''r''<sub>''k''+1</sub> maradékot számolja ki, majd újabb szerepcsere, és így tovább.

=== Megvalósítása Python programozási nyelven ===
<syntaxhighlight lang="python">
def Lnko(a, b):
    if a == b:
        return a
    if b < a:
        a, b = b, a
    while (0 < a):
        a, b = b % a, a
    return b

a = int(input("Adjon meg egy szamot: "))
b = int(input("Adjon meg egy masik szamot: "))

print(Lnko(a, b))
</syntaxhighlight>
== Matematikai alkalmazások ==
=== Bézout-lemma ===
A [[Bézout-lemma]] szerint az ''a'' és a ''b'' számok legnagyobb közös osztója előállítható, mint ''g''&nbsp;=&nbsp;''sa''&nbsp;+&nbsp;''tb'', ahol ''s'' és ''t'' egész számok.<ref>{{cite book | last1 = Jones |first1=G. A. | last2 = Jones | first2 = J. M. | year = 1998 | chapter = Bezout's Identity | title = Elementary Number Theory | url = https://archive.org/details/elementarynumber00jone | publisher = Springer-Verlag | location = New York | pages = [https://archive.org/details/elementarynumber00jone/page/n21 7]–11}}</ref> Másképpen szólva mindig lehetséges olyan ''s'' és ''t'' egészeket találni, hogy ''g''&nbsp;=&nbsp;''sa''&nbsp;+&nbsp;''tb''.{{refhely|Rosen 2000|81. o.}}{{refhely|Cohn 1962|104. o.}}

Az ''s'' és a ''t'' a ''q''<sub>0</sub>, ''q''<sub>1</sub>, … hányadosokból számítható, az algoritmus megfordításával.{{refhely|Rosen 2000|91. o.}} Elindulva visszafelé, ''g'' kifejezhető a ''q''<sub>''N''−1</sub> hányadossal és a két korábbi ''r''<sub>''N''−2</sub> és ''r''<sub>''N''−3</sub> maradékkal:
: {{math|1=''g'' = ''r''<sub>''N''−1</sub> = ''r''<sub>''N''−3</sub> − ''q''<sub>''N''−1</sub> ''r''<sub>''N''−2</sub>&nbsp;.}}

Ezek a maradékok hasonlóan írhatók fel:
: {{math|1=''r''<sub>''N''−2</sub> = ''r''<sub>''N''−4</sub> − ''q''<sub>''N''−2</sub> ''r''<sub>''N''−3</sub>}} és
: {{math|1=''r''<sub>''N''−3</sub> = ''r''<sub>''N''−5</sub> − ''q''<sub>''N''−3</sub> ''r''<sub>''N''−4</sub>&nbsp;.}}

Visszahelyettesítve kapjuk a ''g'' legnagyobb közös osztót mint ''r''<sub>''N''−4</sub> és ''r''<sub>''N''−5</sub> lineáris kombinációját. Ezt folytatjuk, amíg el nem érünk az első két számhoz:
: {{math|1=''r''<sub>2</sub> = ''r''<sub>0</sub> − ''q''<sub>2</sub> ''r''<sub>1</sub>}}
: {{math|1=''r''<sub>1</sub> = ''b'' − ''q''<sub>1</sub> ''r''<sub>0</sub>}}
: {{math|1=''r''<sub>0</sub> = ''a'' − ''q''<sub>0</sub> ''b''.}}

Az összes ''r''<sub>0</sub>, ''r''<sub>1</sub>, … maradék helyettesítése után kifejezzük ''g''-t, mint ''a'' és ''b'' lineáris összegét: ''g''&nbsp;=&nbsp;''sa''&nbsp;+&nbsp;''tb''. A Bézout-lemma és az euklideszi algoritmus általánosítható az euklideszi tartományokra (normált, nullosztómentes, nem nullgyűrű).

=== Főideálok és a hozzájuk kapcsolódó problémák ===
A Bézout-lemma egy újabb definíciót ad a legnagyobb közös osztóra.{{refhely|LeVeque 1996|33. o.}} Tekintsük azokat a számokat, amelyek kifejezhetők ''ua''&nbsp;+&nbsp;''vb'' alakban, ahol ''u'', ''v'' egészek. Mivel ''a'' és ''b'' is osztható ''g''-vel, azért ezek a számok is oszthatók lesznek ''g''-vel. Más szavakkal, a halmaz minden eleme többszöröse ''g''-nek, ami ''a'' és ''b'' összes közös osztójára igaz, de a ''g'' az egyetlen közös osztó, amely eleme ennek a halmaznak, mivel a Bézout-lemma által megadott egészek megfelelnek. Egy kisebb közös osztó nem lehet a halmazban, mivel annak minden eleme osztható kell, hogy legyen ''g''-vel. Továbbá a legnagyobb közös osztó minden többszöröse kifejezhető lineáris kombinációként, ''u''&nbsp;=&nbsp;''ms'' és ''v''&nbsp;=&nbsp;''mt'' választással, ahol ''s'' és ''t'' a Bézout-lemma által megadott egészek. Ez látható, ha a lemma egyenletét megszorozzuk ''m''-mel:

: {{math|1=''mg'' = ''msa'' + ''mtb''.}}

Ezért az ''ua''&nbsp;+&nbsp;''vb'' alakú számok halmaza megegyezik ''g'' többszöröseinek halmazával. Azaz két egész egész együtthatós lineáris kombinációinak halmaza megegyezik legnagyobb közös osztójuk többszöröseinek halmazával. A gyűrűelméletben azt mondják, hogy a legnagyobb közös osztó a két szám által generált ideál generátora. Ez vezetett a főideál és a főideálgyűrű fogalmához.

Ez alapján egy további probléma is megoldható.{{refhely|Schroeder 2005|23. o.}} Az öntögetési feladatokban adva van két edény, ''a'' és ''b'' űrtartalommal. Egy harmadik, elég nagy térfogatú edényben hozzátöltéssel és elvétellel bármely ''ua''&nbsp;+&nbsp;''vb'' űrtartalom kimérhető. Ezek mind ''g''&nbsp;=&nbsp;lnko(''a'',&nbsp;''b'') többszörösei.

=== Kiterjesztett euklideszi algoritmus ===
A kiterjesztett algoritmus a legnagyobb közös osztó mellett a Bézout-lemmában szereplő együtthatókat is számolja. Ez két rekurzív egyenletet ad az algoritmushoz:{{refhely|Rosen 2000|90–93. o.}}

:''s''<sub>''k''</sub> = ''s''<sub>''k''−2</sub> − ''q''<sub>''k''</sub>''s''<sub>''k''−1</sub>
:''t''<sub>''k''</sub> = ''t''<sub>''k''−2</sub> − ''q''<sub>''k''</sub>''t''<sub>''k''−1</sub>

ahol a kezdőértékek:

:''s''<sub>−2</sub> = 1, ''t''<sub>−2</sub> = 0
:''s''<sub>−1</sub> = 0, ''t''<sub>−1</sub> = 1.

A rekurzióval az ''s''&nbsp;=&nbsp;''s''<sub>''N''</sub> és ''t''&nbsp;=&nbsp;''t''<sub>''N''</sub>, ahol ''N+1'' az algoritmus utolsó lépése, amikor ''r''<sub>''N+1''</sub>&nbsp;=&nbsp;0.

A megközelítés helyessége teljes indukcióval bizonyítható. Feltesszük, hogy az algoritmus helyesen működik a ''k''&nbsp;−&nbsp;1. lépésig, azaz
:''r''<sub>''j''</sub> = ''s''<sub>''j''</sub> ''a'' + ''t''<sub>''j''</sub> ''b''
minden ''k''-nál kisebb ''j''-re. A ''k''-adik lépésből adódik, hogy
:''r''<sub>''k''</sub> = ''r''<sub>''k''−2</sub> − ''q''<sub>''k''</sub>''r''<sub>''k''−1</sub>.
Mivel a rekurziós képlet korrekt ''r''<sub>''k''−2</sub> és ''r''<sub>''k''−1</sub> esetén, ez kifejezhető ''s'' és ''t'' segítségével:
:''r''<sub>''k''</sub> = (''s''<sub>''k''−2</sub> ''a'' + ''t''<sub>''k''−2</sub> ''b'') − ''q''<sub>''k''</sub>(''s''<sub>''k''−1</sub> ''a'' + ''t''<sub>''k''−1</sub> ''b''
Átrendezve kapjuk a rekurziós képletet ''k''-ra:
''r''<sub>''k''</sub> = ''s''<sub>''k''</sub> ''a'' + ''t''<sub>''k''</sub> ''b'' = (''s''<sub>''k''−2</sub> − ''q''<sub>''k''</sub>''s''<sub>''k''−1</sub>) ''a'' + (''t''<sub>''k''−2</sub> − ''q''<sub>''k''</sub>''t''<sub>''k''−1</sub>) ''b''.
=== Mátrixmódszer ===
A kiterjesztett algoritmusban szereplő ''s'' és ''t'' megtalálható az ekvivalens mátrixmódszerrel is.<ref name="Koshy_2002">{{cite book | last = Koshy | first = T. | year = 2002 | title = Elementary Number Theory with Applications | publisher = Harcourt/Academic Press | location = Burlington, MA | isbn = 0-12-421171-2 | pages = 167–169}}</ref>

Az algoritmus egyenletei
:''a'' = ''q''<sub>0</sub> ''b'' + ''r''<sub>0</sub>
:''b'' = ''q''<sub>1</sub> ''r''<sub>0</sub> + ''r''<sub>1</sub>
:…
:''r''<sub>''N''−2</sub> = ''q''<sub>''N''</sub> ''r''<sub>''N''−1</sub> + 0

írhatók úgy is, hogy egy kétszer kettes mátrixot megszorozzuk a két dimenziós maradékvektorral:
:<math>
\begin{pmatrix} a \\ b \end{pmatrix} =
\begin{pmatrix} q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} b \\ r_{0} \end{pmatrix} =
\begin{pmatrix} q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} q_1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_0 \\ r_1 \end{pmatrix} =
\cdots =
\prod_{i=0}^N \begin{pmatrix} q_i & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} r_{N-1} \\ 0 \end{pmatrix} \,.
</math>

Reprezentáljuk az összes hányadosmátrix szorzatát '''M'''-mel:
:<math>
\mathbf{M} = \begin{pmatrix} m_{11} & m_{12} \\ m_{21} & m_{22} \end{pmatrix} =
\prod_{i=0}^N \begin{pmatrix} q_i & 1 \\ 1 & 0 \end{pmatrix} =
\begin{pmatrix} q_0 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} q_1 & 1 \\ 1 & 0 \end{pmatrix} \cdots \begin{pmatrix} q_{N} & 1 \\ 1 & 0 \end{pmatrix} \,.
</math>
ezzel az algoritmus a következő alakra egyszerűsödik:
:<math>
\begin{pmatrix} a \\ b \end{pmatrix} =
\mathbf{M} \begin{pmatrix} r_{N-1} \\ 0 \end{pmatrix} =
\mathbf{M} \begin{pmatrix} g \\ 0 \end{pmatrix} \,.
</math>

Ahhoz, hogy a ''g'' legnagyobb közös osztót kifejezzük, az egyenlet mindkét oldalát meg kell szorozni '''M''' inverzével.<ref name="Koshy_2002" /><ref name="Bach_1996">{{cite book | last1 = Bach | first1 = E. | author1-link = Eric Bach | last2= Shallit | first2 = J. | author2-link = Jeffrey Shallit | year = 1996 | title = Algorithmic number theory | url = https://archive.org/details/algorithmicnumbe01bach | publisher = MIT Press | location = Cambridge, MA | isbn = 0-262-02405-5 | pages = [https://archive.org/details/algorithmicnumbe01bach/page/n79 70]–73}}</ref> Az '''M''' inverze létezik, hiszen determinánsa (−1)<sup>''N''+1</sup>, mivel megegyezik a hányadosmátrixok determinánsainak szorzatával, amelyek mindegyike mínusz egy. Ekkor az egyenlet megoldása:
:<math>
\begin{pmatrix} g \\ 0 \end{pmatrix} =
\mathbf{M}^{-1} \begin{pmatrix} a \\ b \end{pmatrix} =
(-1)^{N+1} \begin{pmatrix} m_{22} & -m_{12} \\ -m_{21} & m_{11} \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} \,.
</math>

Az első egyenlet szerint
:=''g'' = (−1)<sup>''N''+1</sup> ( ''m''<sub>22</sub> ''a'' − ''m''<sub>12</sub> ''b''),
így ''s''&nbsp;=&nbsp;(−1)<sup>''N''+1</sup>''m''<sub>22</sub> és ''t''&nbsp;=&nbsp;(−1)<sup>''N''</sup>''m''<sub>12</sub>. Hatékonysága megegyezik a rekurzív algoritmusformáéval.

== Eukleidész lemmája és az egyértelmű prímtényezős felbontás ==
A Bézout-egyenlőség lényeges szerepet kap az euklideszi algoritmus több alkalmazásában, például az egyértelmű prímtényezőkre bontásban.{{refhely|Stark 1978|26–36. o.}} Ennek bemutatására: Legyen az ''L'' szám két tényező szorzata, ''L'' = ''uv''. Ekkor, ha ''L'' osztható egy ''w'' számmal, és ez relatív prím ''u''-hoz, akkor osztója ''v''-nek. Ez a következő gondolatmenettel belátható: Ha ''u'' és ''w'' relatív prímek, akkor van ''s'' és ''t'', hogy
:1 = ''su'' + ''tw''&nbsp;
a Bézout-egyenlőség miatt. Az egyenletet ''v''-vel szorozva:
:''v'' = ''suv'' + ''twv'' = ''sL'' + ''twv''&nbsp;
Mivel ''w'' a jobb oldal minden tagjának osztója, azért osztója kell, hogy legyen a bal oldalnak.{{refhely|Ore 1948|44. o.}}

Speciálisan, ha egy prímszám osztója ''L''-nek, akkor ''L'' valamelyik tényezőjének is osztója kell, hogy legyen. Egy másik megfordítás szerint, ha ''a''<sub>1</sub>, ''a''<sub>2</sub>, …, ''a''<sub>''n''</sub> relatív prímek ''w''-hez, akkor szorzatuk is relatív prím ''w''-hez.{{refhely|Ore 1948|44. o.}}

Mindezekkel már könnyen belátható a prímtényezős felbontás egyértelműsége.{{refhely|Stark 1978|281–292. o.}} Tegyük fel indirekt, hogy az ''L'' egész számnak két lényegileg különböző prímtényezős felbontásában ''m'', illetve ''n'' tényező szerepel, azaz
:''L'' = ''p''<sub>1</sub>''p''<sub>2</sub>…''p''<sub>''m''</sub> = ''q''<sub>1</sub>''q''<sub>2</sub>…''q''<sub>''n''</sub>&nbsp;.

Mivel minden ''p'' osztója ''L''-nek, azért legalább egy ''q''-nak osztójának kell lennie; de mivel prím, ezért lényegében meg kell vele egyeznie. Minden ''p''-t és ''q''-t megvizsgálva mindegyik prímnek megtaláljuk a másik oldalon a lényegi megfelelőjét. Ez ellentmondás, így lényegében egyértelmű a felbontás, eltekintve a prímek sorrendjétől és előjelétől.
=== Lineáris diofantoszi egyenletek ===
[[Fájl:Diophante Bezout.svg|bélyegkép|alt="Átló a bal felső sarokból a jobb alsóba. Az átló mentén tizenöt kör helyezkedik el egymástól egyenlő távolságra. Az ortogonális koordinátarendszer x-y tengelyei a bal alsó sarokból indulnak; az egyenes az y tengelyt a bal felső és az x tengelyt a jobb alsó sarokban metszi."|A 9''x''&nbsp;+&nbsp;12''y''&nbsp;=&nbsp;483 diofantoszi egyenlet megoldásai. A megoldásokat kék körök jelzik]]
A [[diofantoszi egyenlet]]ek azok, amelyek megoldásaként csak egész számok fogadhatók el. A név a Kr. e. 3. századi [[Diofantosz]]ra utal.{{refhely|Rosen 2000|119–125. o.}} A lineáris két ismeretlenes alakja
:''ax'' + ''by'' = ''c''
A diofantoszi egyenletben ''a'', ''b'', ''c'', ''x'' és ''y'' egész számok, és ''a'', ''b'' és ''c'' adottak.{{refhely|Schroeder 2005|106–107. o.}} Moduláris aritmetikával:
:''ax'' ≡ ''c'' mod ''b''.

Legyen ''g'' az ''a'' és a ''b'' legnagyobb közös osztója. Ekkor ''ax''&nbsp;+&nbsp;''by'' mindkét tagja osztható ''g''-vel, így az egyenlet csak akkor oldható meg, ha ''c'' is osztható ''g''-vel. Ekkor mindkét oldalt leosztva ''c''/''g''-vel visszajutunk a Bezout-egyenlethez:
:''sa'' + ''tb'' = ''g''
ahol ''s'' és ''t'' a kiterjesztett euklideszi algoritmussal található meg.{{refhely|Schroeder 2005|108–109. o.}} Innen kapunk egy megoldást:
''x''<sub>1</sub>&nbsp;=&nbsp;''s'' (''c''/''g'') és ''y''<sub>1</sub>&nbsp;=&nbsp;''t'' (''c''/''g'').

Egy lineáris diofantoszi egyenletnek vagy nincs megoldása, vagy végtelen sok megoldása van.{{refhely|Rosen 200|120–121. o.}} Ennek belátására legyen két megoldás az (''x''<sub>1</sub>,&nbsp;''y''<sub>1</sub>) és az (''x''<sub>2</sub>,&nbsp;''y''<sub>2</sub>), ahol
:''ax''<sub>1</sub> + ''by''<sub>1</sub> = ''c'' = ''ax''<sub>2</sub> + ''by''<sub>2</sub>
vagy ekvivalenesen
:''a''(''x''<sub>1</sub> − ''x''<sub>2</sub>) = ''b''(''y''<sub>2</sub> − ''y''<sub>1</sub>).

Emiatt a két ''x'' közötti legkisebb különbség ''b''/''g'', és az ''y'' megoldások közötti legkisebb különbség ''a''/''g''. Ezzel a megoldások:
:''x'' = ''x''<sub>1</sub> − ''bu''/''g''
:''y'' = ''y''<sub>1</sub> + ''au''/''g''
Ha megengedett, hogy ''u'' befussa az egészeket, akkor egy megoldásból végtelen sok nyerhető.

Ha a megoldásokat a pozitív egészekre korlátozzuk, akkor ez véges megoldásszámot ad. Ezzel a korláttal a lineáris diofantoszi egyenletrendszerek még alulhatározva is véges számú megoldást adnak.{{refhely|Stark 1978|47. o.}} Ez különbözik attól az esettől, amikor a megengedett megoldások nemcsak egészek lehetnek.

=== Kínai maradéktétel ===
Az euklideszi algoritmus használatával lineáris diofantoszi egyenletrendszerek oldhatók meg.{{refhely|Rosen 2000|143–170. o.}} A kínai maradéktétel éppen ilyen egyenletrendszerekkel foglalkozik. Ha a szám egy megadott határnál kisebb, akkor ábrázolható a jegyei helyett relatív prím modulusokkal vett maradékaival:
: <math>
\begin{align}
x_1 & \equiv x \bmod m_1 \\
x_2 & \equiv x \bmod m_2 \\
& \vdots \\
x_N & \equiv x \bmod m_N\,.
\end{align}
</math>
ahol ''m''<sub>''i''</sub>-k{{refhely|Schroeder 2005|194–195. o.}} az egyes modulusok, és ''x''<sub>''i''</sub> a hozzájuk tartozó maradékok.

Az egyenletrendszer megoldásához ki kell számítani az ''x'' egész számot, illetve maradékosztályt modulo ''M'', ahol ''M'' a modulusok szorzata. Legyen most ''M''<sub>''i''</sub> a következő:
: <math> M_i = \frac{M}{m_i}. </math>
Ekkor minden ''M''<sub>''i''</sub> a modulusok szorzata, kivéve az ''m''<sub>''i''</sub> modulust. A megoldás azon múlik, hogy találjunk ''h''<sub>''i''</sub> számokat, hogy
: <math> M_i h_i \equiv 1 \bmod m_i\,. </math>

Ezekkel a ''h''<sub>''i''</sub> számokkal minden, ''M''-nél kisebb egész ''x'' rekonstruálható maradékaiból az
: <math> x \equiv (x_1 M_1 h_1 + x_2 M_2 h_2 + \cdots + x_N M_N h_N) \bmod M \,.</math>
egyenlet alapján. Definíciójuk szerint a ''h''<sub>''i''</sub> számok az ''M''<sub>''i''</sub> inverzei, amelyek kiszámíthatók az euklideszi algoritmussal.
=== Stern–Brocot-fa ===
Az euklideszi algoritmussal a pozitív racionális számok halmaza végtelen bináris keresőfába rendezhető; ezt [[Stern–Brocot-fa|Stern–Brocot-fának]] nevezik. A gyökérnél helyezkedik el az 1, a többi szám helye a számláló és a nevező legnagyobb közös osztójának kiszámításával határozható meg az euklideszi algoritmus eredeti formája szerint. Ha a két szám közül az elsőt kell helyettesíteni, akkor jobbra kell lépni, ha a másodikat, akkor balra. Ha az algoritmusnak vége, akkor a számot helyben találjuk.<ref>{{cite book|title=Concrete mathematics|page=123|author1-link=Ronald Graham|last1=Graham|first1=R.|author2-link=Donald Knuth|last2=Knuth|first2=D. E.|author3-link=Oren Patashnik|last3=Patashnik|first3=O.|publisher=Addison-Wesley|year=1989}}</ref> A lépések nem függnek attól, hogy a szám milyen alakban van. Ez arra használható, hogy belássuk, a pozitív racionális számok egyszer jelennek meg a fában.

[[Fájl:SternBrocotTree.svg|bélyegkép|400px|A Stern–Brocot-fa, és a legfeljebb 4 rendű Stern–Brocot-sorozatok]]

Például a 3/4 eléréséhez egyet balra, majd kettőt jobbra kell lépni:
:<math>
\begin{align}
 & \operatorname{lnko}(3,4) & \leftarrow \\
= & \operatorname{lnko}(3,1) & \rightarrow \\
= & \operatorname{lnko}(2,1) & \rightarrow \\
= & \operatorname{lnko}(1,1).
\end{align}
</math>

Az euklideszi algoritmusnak hasonló a kapcsolata a [[Calkin–Wilf-fa|Calkin–Wilf-fával]], de ott az irány fordított: a számtól elindulva kell eljutni az egyhez.
=== Lánctörtek ===
Az euklideszi algoritmus kapcsolatba hozható a [[lánctört]]ekkel.<ref name="Vinogradov_1954">{{cite book | authorlink = Ivan Matveyevich Vinogradov | last=Vinogradov | first= I. M. | year = 1954 | title = Elements of Number Theory | url = https://archive.org/details/elementsofnumber0000vino | publisher = Dover | location = New York | pages = [https://archive.org/details/elementsofnumber0000vino/page/3 3]–13}}</ref> Az egyenletek írhatók úgy is, mint
:<math>
\begin{align}
\frac{a}{b} &= q_0 + \frac{r_0}{b} \\
\frac{b}{r_0} &= q_1 + \frac{r_1}{r_0} \\
\frac{r_0}{r_1} &= q_2 + \frac{r_2}{r_1} \\
& {}\ \vdots \\
\frac{r_{k-2}}{r_{k-1}} &= q_k + \frac{r_k}{r_{k-1}} \\
& {}\ \vdots \\
\frac{r_{N-2}}{r_{N-1}} &= q_N\,.
\end{align}
</math>

Megfigyelhető, hogy a jobb oldal utolsó tagja a bal oldal inverze. Így az első két egyenlet írható úgy is, mint
:<math>\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{r_1}{r_0}} \,.</math>
A harmadik egyenletben behelyettesítve az ''r''<sub>1</sub>/''r''<sub>0</sub> hányadossal:
:<math>\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{r_2}{r_1}}}\,. </math>
Az ''r''<sub>''k''</sub>/''r''<sub>''k''−1</sub> végső arány helyettesíthető a következő egyenlet szerint, egészen az utolsó egyenletig. A végeredmény egy lánctört:
:<math>\frac{a}{b} = q_0 + \cfrac{1}{q_1 + \cfrac{1}{q_2 + \cfrac{1}{\ddots + \cfrac{1}{q_N}}}} = [ q_0; q_1, q_2, \ldots , q_N ] \,.</math>

A fenti példában, amelyben kiszámítottuk az lnko(1071, 462) legnagyobb közös osztót, a hányadosok rendre 2, 3 és 7 voltak. Így az 1071/462 lánctört alakja:
:<math>\frac{1071}{462} = 2 + \cfrac{1}{3 + \cfrac{1}{7}} = [2; 3, 7]</math>
amiről ellenőrző számolással is meggyőződhetünk.

=== Faktorizáció ===
A legnagyobb közös osztó kiszámítása több [[faktorizáció|faktorizáló]] algoritmus lényegi eleme,{{refhely|Crandall-Pomerance 2001|225–349. o.}} így tartalmazza [[Pollard rhó algoritmusa]],{{refhely|Knuth 1997|369–371. o.}} [[Shor-algoritmus|Shor algoritmusa]],<ref>{{cite journal | authorlink = Peter Shor|last=Shor |first=P. W. | year = 1997 | title = Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer | journal = SIAM Journal on Scientific and Statistical Computing | volume = 26 | page = 1484 | doi=10.1137/s0097539795293172}}</ref> [[Dixon faktorizációs módszere]]<ref>{{cite journal | last = Dixon |first= J. D. | year = 1981 | title = Asymptotically fast factorization of integers | url = https://archive.org/details/sim_mathematics-of-computation_1981-01_36_153/page/255 | journal = Math. Comput. | volume = 36 | pages = 255–260 | doi = 10.2307/2007743 | jstor = 2007743 | issue = 153}}</ref> és a [[Lenstra elliptikus görbe faktorizáció]].<ref>{{cite journal | authorlink = Hendrik Lenstra|last=Lenstra|first=H. W., Jr. | year = 1987 | title = Factoring integers with elliptic curves | url = https://archive.org/details/sim_annals-of-mathematics_1987-11_126_3/page/649| journal = Annals of Mathematics | volume = 126 | pages = 649–673 | doi = 10.2307/1971363 | jstor = 1971363 | issue = 3}}</ref> Ezekben az euklideszi algoritmus a legnagyobb közös osztó megtalálására szolgál. A [[lánctört faktorizáció|lánctört-faktorizáció]] [[lánctört]]eket használ, amelyek az euklideszi algoritmussal számíthatók ki.{{refhely|Knuth 1997|380–384. o.}}

== Általánosításai ==
Habár az algoritmus eredeti alakjában a természetes számok legnagyobb közös osztóját számítja ki, általánosítható több különböző matematikai objektumra is, mint [[racionális számok]], [[polinomok]],<ref name="Lang_1984"/> [[kvadratikus egészek]],<ref name="weinberger"/> és [[Hurwitz-kvaterniók]].{{refhely|Stillwell 2003|151–152. o.}}Az utóbbi esetben az euklideszi algoritmussal bizonyítható az egyértelmű faktorizáció, amely prím elemek helyett felbonthatatlanok szorzatára való lényegében egyértelmű felbontást jelenti.
=== Racionális számok ===
Euklidesz valós (nem feltétlenül racionális) számokra terjesztette ki az algoritmust, és azt vizsgálta, hogy található-e két adott (a és b) valós számhoz olyan g valós szám, hogy a és b felírhatók g egész többszöröseként. Ha az egyik szám ''a'', a másik ''b'', akkor van ''m'' és ''n'' egész szám, amellyel ''a'' = ''mg'' és ''b'' = ''ng''.<ref name="Weil_1983" /> Ezek ugyanúgy találhatók meg, mint az egészeknél az ''s'' és a ''t'' együtthatók, amelyekkel ''sa'' + ''tb'' = 0. Eukleidész ezt az algoritmust használta a nem összemérhető szakaszok tanulmányozására.<ref>{{cite book | last1 = Boyer |first1=C. B.|last2= Merzbach|first2=U. C. | year = 1991 | title = A History of Mathematics | url = https://archive.org/details/historymathemati00boye_328 | edition = 2nd | publisher = Wiley | location = New York | isbn = 0-471-54397-7 | pages = [https://archive.org/details/historymathemati00boye_328/page/n135 116]–117}}</ref><ref>{{cite book | authorlink = Florian Cajori|last=Cajori|first= F, | year = 1894 | title = A History of Mathematics | url = https://archive.org/details/historyofmathema001062mbp| publisher = Macmillan | location = New York | page = [https://archive.org/details/historyofmathema001062mbp/page/n79 70] | isbn = 0-486-43874-0}}</ref>

A racionális számok euklideszi algoritmusa abban különbözik az egészektől, hogy a maradék lehet tört, de a hányadosnak egésznek kell lennie. Ha mindkét szám racionális, akkor az algoritmus előbb-utóbb véget ér, hiszen a közös mértékegység létezik, ami közös nevezőre hozással belátható. Valós számokra rátérve ha azonban egyik, vagy mindkettő irracionális, akkor az algoritmus nem ér véget, ez végtelen lánctörtként írható le. A maradékokat itt is ''r''<sub>''k''</sub> jelöli, a hányadosok ''q''<sub>''k''</sub>-k. Az ''a''/''b'' = ''mg''/''ng'' = ''m''/''n'' tört lánctört alakja: [''q''<sub>0</sub>; ''q''<sub>1</sub>, ''q''<sub>2</sub>, …, ''q''<sub>''N''</sub>]. Ha az ''a''/''b'' arány irracionális, akkor végtelen lánctörtet kapunk, amelynek lánctört alakja [''q''<sub>0</sub>; ''q''<sub>1</sub>, ''q''<sub>2</sub>, …].<ref>{{cite book|title=Algorithmic Cryptanalysis|first=Antoine|last=Joux|publisher=CRC Press|year=2009|isbn=9781420070033|url=https://books.google.com/books?id=buQajqt-_iUC&pg=PA33|page=33}}</ref> Például az aranymetszés arányszáma ''φ'' = [1; 1, 1, …], és a 2 négyzetgyöke [1; 2, 2, …].<ref>{{cite book|title=Mathematical Omnibus: Thirty Lectures on Classic Mathematics|first1=D. B.|last1=Fuks|first2=Serge|last2=Tabachnikov|authorlink2=Sergei Tabachnikov|publisher=American Mathematical Society|year=2007|isbn=9780821843161|page=13|url=https://books.google.com/books?id=IiG9AwAAQBAJ&pg=PA13}}</ref>

Valós számokon az algoritmus leállása nulla valószínűségű, ugyanis majdnem minden valós szám irracionális..<ref>{{cite book|title=The Universal Book of Mathematics: From Abracadabra to Zeno's Paradoxes|first=David|last=Darling|authorlink=David J. Darling|publisher=John Wiley & Sons|year=2004|isbn=9780471667001|url=https://books.google.com/books?id=HrOxRdtYYaMC&pg=PA175|page=175|contribution=Khintchine's constant}}</ref> A lánctörtek kezdeti szakaszai (''k'' lépés után [''q''<sub>0</sub>; ''q''<sub>1</sub>, ''q''<sub>2</sub>, …, ''q''<sub>''k''</sub>]) közelítést adnak az irracionális számokra, ami hosszabb kezdeti szakasszal javítható. A közelítés egyszerű tört alakra hozva éppen ''m''<sub>''k''</sub>/''n''<sub>''k''</sub>, amelyek konvergens sorozatot alkotnak. A számláló és a nevező relatív prím, és a következő rekurzív szabály érvényes rájuk:
:''m''<sub>''k''</sub> = ''q''<sub>''k''</sub> ''m''<sub>''k''−1</sub> + ''m''<sub>''k''−2</sub> és
:''n''<sub>''k''</sub> = ''q''<sub>''k''</sub> ''n''<sub>''k''−1</sub> + ''n''<sub>''k''−2</sub>
ahol ''m''<sub>−1</sub> = ''n''<sub>−2</sub> = 1 és ''m''<sub>−2</sub> = ''n''<sub>−1</sub> = 0 a [[rekurzió]] kezdőértékei. Az ''m''<sub>''k''</sub>/''n''<sub>''k''</sub> konvergens sorozat a legjobb racionális számokból álló közelítő sorozat az ''a''/''b''-hez az ''n''<sub>''k''</sub> nevezővel:<ref>{{cite book|title=Explorations in Quantum Computing|first=Colin P.|last=Williams|publisher=Springer|year=2010|isbn=9781846288876|url=https://books.google.com/books?id=QE8S--WjIFwC&pg=PA277|pages=277–278}}</ref>
:<math>
\left|\frac{a}{b} - \frac{m_k}{n_k}\right| < \frac{1}{n_k^2}.
</math>

=== Polinomok ===
Az egy változós polinomok adott [[gyűrű (matematika)|gyűrű]] fölött gyűrűt alkotnak. A gyűrű lehet például az egész számok, a racionális vagy a valós számok. Az ezek fölötti polinomok azok, amelyeknek együtthatói az adott számkörből valók, így az egész, a racionális és a valós együtthatós polinomok összeadhatók, kivonhatók és szorozhatók, és az eredmény polinomok együtthatói is a megfelelő számkörből valók. Definiálható a maradékos osztás is. A következőkben testek fölötti polinomokról lesz szó, vagyis az együtthatókat még osztani is lehet.

A polinomok körében a prímszámok megfelelői a felbonthatatlanok, más néven irreducibilis polinomok. Két polinom, ''a''(''x'') és ''b''(''x'') legnagyobb közös osztója az egész számokhoz hasonlóan definiálható az irreducibilis felbontásuk segítségével, és meghatározható az euklideszi algoritmussal.<ref name="Lang_1984" >{{cite book | authorlink = Serge Lang|last=Lang|first= S. | year = 1984 | title = Algebra | url = https://archive.org/details/algebra0000lang| edition = 2nd | publisher = Addison–Wesley | location = Menlo Park, CA | isbn = 0-201-05487-6 | pages = [https://archive.org/details/algebra0000lang/page/n209 190]–194}}</ref>

Az eljárás hasonlít az egészekéhez. A ''k''-adik lépésben a ''q''<sub>''k''</sub>(''x'') hányados és az ''r''<sub>''k''</sub>(''x'') maradék polinom eleget tesz az
:''r''<sub>''k''−2</sub>(''x'') = ''q''<sub>''k''</sub>(''x'') ''r''<sub>''k''−1</sub>(''x'') + ''r''<sub>''k''</sub>(''x'')
rekurzív egyenletnek, ahol ''r''<sub>−2</sub>(''x'')&nbsp;=&nbsp;''a''(''x'') és ''r''<sub>−1</sub>(''x'')&nbsp;=&nbsp;''b''(''x''). A hányados polinom ''q''<sub>''k''</sub>(''x'') ''r''<sub>''k''−1</sub> együtthatóját úgy választják, hogy megegyezzen ''r''<sub>''k''−2</sub>(''x'') legmagasabb fokú tagjával; ez biztosítja, hogy a maradékok foka csökkenjen. Ezzel belátható, hogy az euklideszi algoritmus véget ér. Az utolsó nem nulla maradék lesz a polinomok legnagyobb közös osztója.{{refhely|Cox-Little-O'Shea 1997|37–46. o.}}

Például vegyük a következő, másodfokú polinomok szorzatára bomló polinomokat:
:''a''(''x'') = ''x''<sup>4</sup> − 4''x''<sup>3</sup> + 4 ''x''<sup>2</sup> − 3''x'' + 14 = (''x''<sup>2</sup> − 5''x'' + 7)(''x''<sup>2</sup> + ''x'' + 2 és
:''b''(''x'') = ''x''<sup>4</sup> + 8''x''<sup>3</sup> + 12''x''<sup>2</sup> + 17''x'' + 6 = (''x''<sup>2</sup> + 7''x'' + 3)(''x''<sup>2</sup> + ''x'' + 2).

Az első maradék az ''a''(''x'') / ''b''(''x'') osztást elvégezve ''r''<sub>0</sub>(''x'') = ''x''<sup>3</sup> + (2/3) ''x''<sup>2</sup> + (5/3) ''x'' − (2/3). A következő lépésben ''b''(''x'')-et osztjuk ''r''<sub>0</sub>(''x'')-szel, és maradékként ''r''<sub>1</sub>(''x'') = ''x''<sup>2</sup> + ''x'' + 2 adódik. Végül az ''r''<sub>0</sub>(''x'') osztás ''r''<sub>1</sub>(''x'')-szel nullát ad maradékul, így az algoritmus véget ér.

Több alkalmazás is átvihető az egészekről a polinomokra,{{refhely|Schroeder 2005|254–259. o.}} így megoldhatók vele lineáris diofantoszi egyenletrendszerek a polinomokra, és szimultán lineáris kongruenciarendszerek is. A polinomokra is definiálhatók lánctörtek, és a lánctörtbe fejtés is elvégezhető. De vannak más alkalmazások is, például a [[Sturm-lánc]]ok egy adott intervallumban keresik a polinom gyökeit.<ref>{{cite book|title=Convolutions in French Mathematics, 1800-1840: From the Calculus and Mechanics to Mathematical Analysis and Mathematical Physics. Volume II: The Turns|first=Ivor|last=Grattan-Guinness|authorlink=Ivor Grattan-Guinness|publisher=Birkhäuser|series=Science Networks: Historical Studies|volume=3|location=Basel, Boston, Berlin|year=1990|isbn=9783764322380|page=1148|url=https://books.google.com/books?id=_GgioErrbW8C&pg=PA1148|quote=Our subject here is the 'Sturm sequence' of functions defined from a function and its derivative by means of Euclid's algorithm, in order to calculate the number of real roots of a polynomial within a given interval}}</ref> Ennek további felhasználási területei vannak a [[vezérléselmélet]]ben a [[Routh–Hurwitz stabilitási kritérium]].<ref>{{cite book|title=Solving Ordinary Differential Equations I: Nonstiff Problems|series=Springer Series in Computational Mathematics|volume=8|first1=Ernst|last1=Hairer|first2=Syvert P.|last2=Nørsett|first3=Gerhard|last3=Wanner|edition=2nd|publisher=Springer|year=1993|isbn=9783540566700|pages=81ff|url=https://books.google.com/books?id=F93u7VcSRyYC&pg=PA81|contribution=The Routh–Hurwitz Criterion}}</ref>

A fentiek akkor is alkalmazhatók, ha az együtthatók a véges testek elemei, vagy lehetnek más, általánosabb testből.<ref name="Lang_1984" />

=== Gauss-egészek ===
A [[Gauss-egész]]ek α&nbsp;=&nbsp;''u''&nbsp;+&nbsp;''vi'' alakú komplex számok, ahol ''u'' és ''v'' valós egészek, és ''i'' a képzetes egység.{{refhely|Stillwell 2003|101–116. o.}}Az euklideszi algoritmus bevezetésével megmutatható, hogy egyértelműen bomlanak fel, ahogy azt a fenti Bézout-egyenlőség is mutatja.<ref name="Gauss_1832">{{cite journal | authorlink = Carl Friedrich Gauss|last=Gauss|first=C. F. | year = 1832 | title = Theoria residuorum biquadraticorum | journal = Comm. Soc. Reg. Sci. Gött. Rec. | volume = 4}} Reprinted in {{cite book|first=C. F.|last=Gauss|year=2011|title=Werke|volume=2|publisher=Cambridge Univ. Press|pages=65–92|id={{doi|10.1017/CBO9781139058230.004}} and {{doi|10.1017/CBO9781139058230.005}}}}</ref> Ezt aztán több alkalmazásban is felhasználják, mint a pitagoraszi számhármasok előállítása.{{refhely|Stillwell 2003|101–116. o.}} A tételek gyakran máshogy is bizonyíthatók, az euklideszi algoritmus kényelmi eszköz.

A Gauss-egészekre használt euklideszi algoritmus majdnem ugyanaz, mint a valós egészekre használt.<ref name="hensley">{{cite book|title=Continued Fractions|first=Doug|last=Hensley|publisher=World Scientific|year=2006|isbn=9789812564771|page=26|url=https://books.google.com/books?id=k3PVXFkweKgC&pg=PA26}}</ref> Itt a ''q''<sub>''k''</sub> hányadost és az ''r''<sub>''k''</sub> maradékot úgy választják, hogy
:''r''<sub>''k''</sub> = ''r''<sub>''k''−2</sub> − ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub>,
ahol α, β kiindulási Gauss-egészek, és ''r''<sub>''k''−2</sub>&nbsp;=&nbsp;α, ''r''<sub>''k''−1</sub>&nbsp;=&nbsp;β. A maradékok nagyságának csökkenését a komplex abszolút értékben mérik, tehát |''r''<sub>''k''</sub>|&nbsp;<&nbsp;|''r''<sub>''k''−1</sub>| valós nem negatív egészek, ami ahhoz kell, hogy bizonyítható legyen az algoritmus végessége.<ref>{{cite book|title=Theory of Algebraic Integers|series=Cambridge Mathematical Library|first=Richard|last=Dedekind|authorlink=Richard Dedekind|publisher=Cambridge University Press|year=1996|isbn=9780521565189|pages=22–24|url=https://books.google.com/books?id=KZRBabJY4ewC&pg=PA222}}</ref> A maradékok és a hányadosok Gauss-egészek. A ''q''<sub>''k''</sub> maradékokat általában úgy számolják, hogy az α/β pontos arány valós és képzetes részét egészekre kerekítik.<ref name="hensley"/>
Az utolsó nem nulla maradék lnko(α,β), a legnagyobb abszolút értékű Gauss-egész, amely mindkét kiindulási számnak osztója. Ez lényegében egyértelmű, azaz egységgel szorzás erejéig egyértelmű. Az egységek ±1 és ±''i''.<ref>{{cite book|title=Numbers and Symmetry: An Introduction to Algebra|first1=Bernard L.|last1=Johnston|first2=Fred|last2=Richman|publisher=CRC Press|year=1997|isbn=9780849303012|page=44|url=https://books.google.com/books?id=koUfrlgsmUcC&pg=PA44}}</ref>

Több alkalmazás is átvihető Gauss-egészekre, például a lineáris diofantoszi egyenletek és a szimultán kongruenciarendszerek megoldása.<ref>{{cite book|title=Introduction to Number Theory|url=https://archive.org/details/introductiontonu0000adam|first1=William W.|last1=Adams|first2=Larry Joel|last2=Goldstein|publisher=Prentice-Hall|year=1976|isbn=9780134912820|at=Exercise 24, p.&nbsp;205|quote=State and prove an analogue of the Chinese remainder theorem for the Gaussian integers.}}</ref> A lánctörtbe fejtés is elvégezhető.<ref name="hensley"/>

=== Euklideszi gyűrűk ===
Az [[euklideszi gyűrű]]k [[Gyűrű (matematika)|kommutatív gyűrűk]], amelyekben euklideszi norma biztosítja, hogy elvégezhető az euklideszi algoritmus.{{refhely|Stark 1978|290. o.}}{{refhely|Cohn 1962|104–105. o.}} Ez egy ''f'' leképezés a gyűrű elemein, amely az összes elemet a nem negatív egész számokra képezi le. Teljesíti továbbá azt is, hogy ha ''a'' és ''b'' a gyűrű nullától különböző elemei, akkor van olyan ''q'' és ''r'' elem, hogy ''a'' = ''qb'' + ''r'' és ''f''(''r'') < ''f''(''b'').<ref>{{cite book|title=Concrete Abstract Algebra: From Numbers to Gröbner Bases|first=Niels|last=Lauritzen|publisher=Cambridge University Press|year=2003|isbn=9780521534109|page=130|url=https://books.google.com/books?id=BdAbcje-TZUC&pg=PA130|ref=harv}}</ref> Ilyen norma a polinomoknál a fok<ref>{{harvtxt|Lauritzen|2003}}, p.&nbsp;161</ref> és a Gauss-egészeknél az abszolút érték négyzete.<ref>{{harvtxt|Lauritzen|2003}}, p.&nbsp;132</ref>

[[A számelmélet alaptétele]] minden euklideszi gyűrűben bizonyítható. Ez azt jelenti, hogy minden nullától különböző elem lényegében egyértelműen felbontható irreducibilis elemek szorzatára. Ezzel a tulajdonsággal az euklideszi gyűrűk [[egyértelmű faktorizációs gyűrű]]k. Megfordítva azonban nem minden egyértelmű faktorizációs gyűrű euklideszi.<ref name="sharpe">{{cite book|title=Rings and Factorization|first=David|last=Sharpe|publisher=Cambridge University Press|year=1987|isbn=9780521337182|page=55|url=https://books.google.com/books?id=Nmg4AAAAIAAJ&pg=PA55|ref=harv}}</ref> Az egyértelmű faktorizációs gyűrűkben létezik a legnagyobb közös osztó, bár ez nem mindig található meg euklideszi algoritmussal.<ref>{{harvtxt|Sharpe|1987}}, p.&nbsp;52</ref> Az euklideszi gyűrűk {{forrás|[[főideáltartomány]]ok}}, azaz [[integritási tartomány]]ok, ahol minden ideál főideál. A főideálgyűrűk azonban nem biztos, hogy euklideszi gyűrűk.<ref>{{harvtxt|Lauritzen|2003}}, p.&nbsp;131</ref>

Az euklideszi gyűrűkben az egyértelmű irreducibilis felbontás több alkalmazásban is hasznos. Például a Gauss-egészekkel kényelmesen megadhatók a [[pitagoraszi számhármasok]].{{refhely|Stillwell 2003|101–116. o.}} Ezen felbuzdulva [[Gabriel Lamé]] hasonlóval próbálkozott 1847-ben, amikor a nagy Fermat-tételt próbálta bizonyítani. [[Joseph Liouville]] javaslatával foglalkozott az euklideszi algoritmus hatékonyságával is.<ref>{{cite journal | last = Lamé |first=G. |authorlink=Gabriel Lamé| year = 1847 | title = Mémoire sur la résolution, en nombres complexes, de l'équation A<sup>n</sup> + B<sup>n</sup> + C<sup>n</sup> = 0 | journal = J. Math. Pures Appl. | volume = 12 | pages = 172–184}}</ref> Bizonyítása azon a feltevésen alapult, hogy az ''x'' + ω''y'' alakú számok egyértelműen faktorizálhatók, ahol ''x'', ''y'' egészek, és ω = ''e''<sup>2''i''π/''n''</sup> ''n''-edik komplex egységgyök, azaz ω<sup>''n''</sup> = 1. Az alapfeltevés azonban nem igaz minden ''n''-re, így [[Ernst Kummer]] az ideális számok bevezetésével próbálta javítani a hibát, ami alapján [[Richard Dedekind]] megalapozta az [[ideál (gyűrűelmélet)|ideálok]] fogalmát.<ref>{{cite book|authorlink=Harold Edwards (mathematician) | last=Edwards|first=H.|title=Fermat's last theorem: a genetic introduction to algebraic number theory|url=https://archive.org/details/fermatslasttheor00hmed |year=2000|publisher=Springer|page=[https://archive.org/details/fermatslasttheor00hmed/page/76 76]}}</ref>

==== Kvadratikus egészek ====
A [[kvadratikus test]]ek egészgyűrűi segítenek bemutatni az euklideszi gyűrűket.

A kvadratikus testek a racionális számtest <math>\mathbb{Q}(\sqrt{D})</math> alakú másodfokú bővítései, ahol ''D'' négyzetmentes egész szám.

Egy adott kvadratikus test egészgyűrűjének elemeit kvadratikus egészeknek nevezzük. Adott ''D''-re a kvadratikus egészek tehát az [[Algebrai egész szám|algebrai egészek]] gyűrűjének részgyűrűjét alkotják. Az egészgyűrű elemeit ''D''&nbsp;=&nbsp;−1 esetben [[Gauss-egész]]eknek, ''D''&nbsp;=&nbsp;−3 esetben [[Eisenstein-egész]]eknek nevezzük. Minden kvadratikus egész felírható <math>u+v\sqrt{D}</math> alakban, ahol ''u'' és ''v'' egész vagy [[Félegész számok|félegész]]. (Az utóbbi csak akkor fordulhat elő, ha ''D'' 4-gyel osztva egyet ad maradékul, és ''u'' és ''v'' csak egyszerre lehet félegész.)

A [[Gauss-egész#Norma|Gauss-egészek normafogalma]] kézenfekvő módon általánosítható a kvadratikus egészek körében: <math>u+v\sqrt{D}</math> normája <math>(u+v\sqrt{D})(u-v\sqrt{D})=u^2-Dv^2</math>. Kimutatható, hogy a kvadratikus egész gyűrűk ''ezzel a normával'' pontosan akkor euklidesziek, ha ''D''&nbsp;=&nbsp;−11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57 vagy 73.{{refhely|Cohn 1962|104–110. o.}}<ref>{{cite book | last = LeVeque | first = W. J. | authorlink = William J. LeVeque | title = Topics in Number Theory, Volumes I and II | url = https://archive.org/details/topicsinnumberth0000leve | publisher = Dover Publications | location = New York | year = 2002 | origyear = 1956 | isbn = 978-0-486-42539-9 | zbl=1009.11001 | pages=II:57,81}}</ref>

Elképzelhető persze, hogy a kvadratikus egészek gyűrűje valamilyen, a fentiektől különböző ''D'' értékre is euklideszi gyűrű valamilyen más normával. Nem ismert, hogy mely ''D''-kre található ilyen euklideszi norma,<ref name="Clark_1994">{{cite journal | last = Clark | first = D. A. | year = 1994 | title = A quadratic field which is Euclidean but not norm-Euclidean | journal = Manuscripta Mathematica | volume = 83 | pages = 327–330 | doi = 10.1007/BF02567617 | url = http://www.springerlink.com/content/6t9u2440402n1346/ | zbl = 0817.11047 }}{{Halott link|url=http://www.springerlink.com/content/6t9u2440402n1346/ |date=2020-02 }}</ref> de egy 1994-es eredmény szerint ''D'' = 69-re a kvadratikus egészek euklideszi gyűrűt alkotnak.<ref name="Clark_1994" /> Weinberger 1973-ban bizonyította, hogy D>0 esetén a kvadratikus gyűrűk pontosan akkor euklidesziek, ha főideálgyűrűk, feltéve, hogy az [[általánosított Riemann-hipotézis]] teljesül.<ref name="weinberger">{{cite journal | last = Weinberger | first = P. | title = On Euclidean rings of algebraic integers | journal = Proc. Sympos. Pure Math. | volume = 24 | pages = 321–332}}</ref>

=== Nem kommutatív gyűrűk ===
Nem kommutatív gyűrűkben is alkalmazható az euklideszi algoritmus, például a [[Hurwitz-kvaterniók]]nál.{{refhely|Stillwell 2003|151–152. o.}} Legyen α és β a gyűrű két eleme. Ekkor δ jobb oldali közös osztó, ha van ξ és η eleme a gyűrűnek, hogy α = ξδ és β = ηδ. Hasonlóan, δ bal oldali közös osztó, ha α = δξ és β = δη. Mivel a szorzás nem kommutatív, az euklideszi algoritmus sem szimmetrikus, bal és jobb oldali változata van, a megfelelő oldali legnagyobb közös osztó keresésére.{{refhely|Stillwell 2003|151–152. o.}}

A jobb oldali változat első lépése:
:ρ<sub>0</sub> = α − ψ<sub>0</sub>β = (ξ − ψ<sub>0</sub>η)δ
ahol ψ<sub>0</sub> a hányados, és ρ<sub>0</sub> a maradék. Az egyenlet szerint α és β jobb oldali közös osztói a ρ<sub>0</sub> maradéknak is osztói.

A bal oldali változat hasonlóan kezdődik:
:ρ<sub>0</sub> = α − βψ<sub>0</sub> = δ(ξ − ηψ<sub>0</sub>)&nbsp;.
A következő lépésekben az elemek szerepe a kommutatív esethez hasonlóan változik, de itt végig a jobb vagy a bal változatot kell használni ahhoz, hogy megtaláljuk a jobb vagy a bal legnagyobb közös osztót.

Euklideszi tartományokban van az elemeknek olyan mérete, amely végig csökken. Ez biztosítja az algoritmus végességét, ha a méretek nem csökkenhetnek a végtelenségig.<ref name="entgtrg">{{cite book|title=Elementary Number Theory, Group Theory and Ramanujan Graphs|volume=55|series=London Mathematical Society Student Texts|first1=Giuliana|last1=Davidoff|first2=Peter|last2=Sarnak|first3=Alain|last3=Valette|publisher=Cambridge University Press|year=2003|isbn=9780521531436|contribution=2.6 The Arithmetic of Integer Quaternions|pages=59–70|url=https://books.google.com/books?id=AlvfFDJOGZ8C&pg=PA59}}</ref>

A legtöbb alkalmazás működik a nem kommutatív esetben is. A Bézout-lemma szerint a jobb és a bal legnagyobb közös osztó kifejezhető lineáris kombinációként, azaz vannak σ és τ gyűrűelemek, hogy a jobb legnagyobb közös osztó<ref>{{cite book|title=Classical Theory of Algebraic Numbers|series=Universitext|publisher=Springer-Verlag|first=Paulo|last=Ribenboim|year=2001|isbn=9780387950709|page=104|url=https://books.google.com/books?id=u5443xdaNZcC&pg=PA104}}</ref>
:Γ<sub>right</sub> = σα + τβ
vagy a legnagyobb bal közös osztó
:Γ<sub>left</sub> = ασ + βτ&nbsp;.
Ezek felhasználhatók a diofantoszi egyenletek és a szimultán kongruenciarendszerek megoldásához. Ezen alapszik a [[négynégyzetszám-tétel]] egy bizonyítása kvaterniókkal.<ref name="entgtrg"/>

== Története ==
[[Fájl:Euklid.jpg|bélyegkép|alt="A kép Eukleidészt szakállas férfiként ábrázolja, kezében körzőt tart egy fatáblához."|Eukleidész körzővel és fatáblával. A róla elnevezett algoritmus már valószínűleg előtte is ismert volt]]

Az euklideszi algoritmus az egyik legrégebb óta használt algoritmus.{{refhely|Knuth 1997|318. o.}} Eukleidész ''Elemek'' című művében a 7. és a 10. könyv tartalmazza. A 7. könyvben a pozitív egész számok, a 10. kötetben a szakaszok euklideszi algoritmusát tárgyalja. Mai szóhasználattal ez a valós számokra vonatkozó algoritmus, azonban akkoriban csak a racionális számokkal foglalkoztak. A valós számokkal területet, térfogatot és egyebeket is jelölnek, amelyek nem válthatók át egymásba, és amelyekkel nem végezhető el az algoritmus. A szakaszok euklideszi algoritmusa geometriai, és a leghosszabb közös mértékegységet találja meg, ha van olyan.

Az algoritmust valószínűleg nem Eukleidész találta ki. Az ''Elemek''ben korának matematikai ismereteit gyűjtötte össze.<ref name="Weil_1983">{{cite book | authorlink = André Weil|last=Weil|first=A. | year = 1983 | title = Number Theory | publisher = Birkhäuser | location = Boston | isbn = 0-8176-3141-0 | pages = 4–6}}</ref><ref name="Jones_1994">{{cite book | last = Jones|first= A. | year = 1994 | chapter = Greek mathematics to AD 300 | title = Companion encyclopedia of the history and philosophy of the mathematical sciences | publisher = Routledge | location = New York | isbn = 0-415-09238-8 | pages = 46–48}}</ref> B. L. van der Waerden matematikus és történész szerint a 7. könyv számelméleti részei a [[pitagoreus]]októl származnak.<ref name="van_der_Waerden_1954">{{cite book | authorlink = Bartel Leendert van der Waerden|last=van der Waerden|first= B. L. | year = 1954 | title = Science Awakening | url = https://archive.org/details/scienceawakening00waer| series = translated by Arnold Dresden | publisher = P. Noordhoff Ltd | location = Groningen | pages = [https://archive.org/details/scienceawakening00waer/page/114 114]–115}}</ref> Az algoritmus helyességét valószínűleg [[Knidoszi Eudoxosz]] bizonyította először Kr. e. 375 körül.{{refhely|Knuth 1997|318. o.}}<ref>{{cite journal | last = von Fritz|first= K. | year = 1945 | title = The Discovery of Incommensurability by Hippasus of Metapontum | url = https://archive.org/details/sim_annals-of-mathematics_1945-04_46_2/page/242| journal = Annals of Mathematics | volume = 46 | pages = 242–264 | doi = 10.2307/1969021 | jstor = 1969021 | issue = 2}}</ref> Az algoritmus valószínűleg Eudoxosz előtt is ismert volt,<ref>{{cite book | authorlink = T. L. Heath | last = Heath |first = T. L. | year = 1949 | title = Mathematics in Aristotle | url = https://archive.org/details/mathematicsarist00heat | publisher = Oxford Press | pages = [https://archive.org/details/mathematicsarist00heat/page/n92 80]–83}}</ref><ref>{{cite book | authorlink = David Fowler (mathematician)|last=Fowler|first=D. H. | year = 1987 | title = The Mathematics of Plato's Academy: A New Reconstruction | url = https://archive.org/details/mathematicsofpla0000fowl_h9l3| publisher = Oxford University Press | location = Oxford | isbn = 0-19-853912-6 | pages = [https://archive.org/details/mathematicsofpla0000fowl_h9l3/page/31 31]–66}}</ref> az ἀνθυφαίρεσις szakkifejezés (anthyphairesis, kölcsönös kivonás) szakkifejezés alapján. Ez Arisztotelész és Eukleidész műveiben is megtalálható.<ref>{{cite journal | last = Becker | first = O. | year = 1933 | title = Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid | volume = 2 | pages = 311–333 | journal = Quellen und Studien zur Geschichte der Mathematik B}}</ref>

Néhány évszázaddal később Kínában és Indiában is felfedezték az euklideszi algoritmust,{{refhely|Stillwell 1997|31. o.}} és használták diofantoszi egyenletek megoldására, amelyek a csillagászatból adódtak, hogy pontosabb naptárt készíthessenek. [[Árjabhata]] indiai csillagász és matematikus írta le az 5. század végén{{refhely|Tattersall 2005|70. o.}} a diofantoszi egyenletek megoldására.{{refhely|Rosen 2000|86–87. o.}} A kínai maradéktétel egy speciális esetét a [[Szunce Szuancsing|{{kínai|Sūnzĭ Suànjīng|Szunce szuancsing}}]] című mű írta le,{{refhely|Ore 1948|247–248. o.}} de a tétel általános leírását {{kínai|Qin Jiushao|Csin Csiu-sao}} adta 1247-es könyvében, amelynek címe {{kínai|Shushu Jiuzhang|Susu csiucsang}} (數書九章, Értekezés a matematikáról kilenc részben).{{refhely|Tattersall 2005|72, 184–185. o.}}

Európában sokáig csak az ''Elemek'' című műből ismerték az algoritmust. Bachet 1624-ben írt róla (''Problèmes plaisants et délectables'', második kiadás).{{refhely|Tattersall 2005|70. o.}} Leírta, hogy lánctörtbe fejtéshez és diofantoszi egyenletek megoldásához használják. A kibővített euklideszi algoritmusról az angol matematikus Nicholas Saunderson írt először, aki Roger Cotesnak tulajdonította, mint a lánctörtbe fejtés hatékony eszközét.{{refhely|Tattersall 2005|72–76. o.}}

A 19. században újabb számköröket vezettek be. Az euklideszi algoritmus hatékony eszköznek bizonyul a [[Gauss-egész]]ek és az [[Eisenstein-egész]]ek körében is. 1815-ben Carl Gauss az euklideszi algoritmussal bizonyította a Gauss-egészek egyértelmű felbontását, habár az eredményt csak 1832-ben jelentette meg.<ref name="Gauss_1832" /> Az 1801-ben kiadott Disquisitiones Arithmeticae csak a lánctörtekkel kapcsolatban említi meg az algoritmust.{{refhely|Stillwell 1997|31. o.}} Peter Gustav Lejeune Dirichlet-től származik az a kijelentés, hogy az euklideszi algoritmus a számelmélet nagy részének alapja.{{refhely|Stillwell 1997|31–32. o.}} Kimutatta, hogy az egyértelmű faktorizáció minden olyan számkörben teljesül, ahol az euklideszi algoritmus alkalmazható.{{refhely|Lejeune Dirichlet 1894|29–31. o.}} Számelméleti előadásait Richard Dedekind szerkesztette össze és bővítette ki. Dedekind az algoritmus segítségével tanulmányozta az [[Algebrai egész szám|algebrai egészeket]], a számok új általános típusát. A [[Gauss-egész]]ek egyértelmű felbontására alapozva bizonyította be a [[kétnégyzetszám-tétel]]t.{{hely|Lejeune Dirichlet 1894}} Definiálta az euklideszi gyűrű fogalmát. Az euklideszi gyűrűben nemcsak az igaz, hogy a faktorizáció egyértelmű, hanem van norma is. Ez biztosítja, hogy az euklideszi algoritmus véges. A 19. század végén Dedekind [[ideál (algebra)|ideáljai]] háttérbe szorították az euklideszi algoritmust.{{refhely|Stillwell 2003|41–42. o.}}

Az algoritmus további alkalmazási lehetőségeit is feltárták a 19. században. Charles Sturm 1829-ben megmutatta, hogy a Sturm-láncok módszerében is hasznos a polinomok adott intervallumba eső valós gyökeinek kiszámításában.<ref>{{cite journal | last = Sturm |first = C. | authorlink = Jacques Charles François Sturm | year = 1829 | title = Mémoire sur la résolution des équations numériques | journal = Bull. des sciences de Férussac | volume = 11 | pages = 419–422}}</ref>

Az euklideszi algoritmus volt az első egészrelációs algoritmus, amellyel összemérhető számok közötti arányokat lehetett egészek közötti arányként meghatározni. Ezt később továbbiak követték, mint Helaman Ferguson és R.W. Forcade (1979) algoritmusa,<ref>{{MathWorld|urlname=IntegerRelation|title=Integer Relation}}</ref> illetve a Lenstra–Lenstra–Lovász-algoritmus.<ref>{{cite journal | last = Peterson |first = I. | date = 12 August 2002 | title = Jazzing Up Euclid's Algorithm | journal = ScienceNews | url=http://www.sciencenews.org/view/generic/id/172/title/Math_Trek__Jazzing_Up_Euclids_Algorithm}}</ref><ref>{{cite journal | last = Cipra | first = B. A. | title = The Best of the 20th Century: Editors Name Top 10 Algorithms | journal = SIAM News | volume = 33 | date = 16 May 2000 | publisher = [[Society for Industrial and Applied Mathematics]] | issue = 4 | url = https://www.siam.org/pdf/news/637.pdf | accessdate = 2016-08-13 | archiveurl = https://web.archive.org/web/20160922144038/https://www.siam.org/pdf/news/637.pdf | archivedate = 2016-09-22 }}</ref>

1969-ben Cole és Davie egy kétszemélyes játékot alkotott az euklideszi algoritmusra alapozva, ez a The Game of Euclid.<ref>{{cite journal | last1 = Cole | first1 = A. J. | last2 = Davie | first2 = A. J. T. | year = 1969 | title = A game based on the Euclidean algorithm and a winning strategy for it | url = https://archive.org/details/sim_mathematical-gazette_1969-12_53_386/page/354 | journal = Math. Gaz. | volume = 53 | pages = 354–357 | doi = 10.2307/3612461 | jstor = 3612461 | issue = 386}}</ref> Lényege, hogy a két kupac közül a kisebb többszöröseinek megfelelő számú követ lehet elvenni. Az nyer, akinek sikerül az egyik kupacot kiürítenie.{{refhely|Rosen 2000|95. o.}}<ref>{{cite book | last = Roberts | first = J. | year = 1977 | title = Elementary Number Theory: A Problem Oriented Approach | url = https://archive.org/details/Elementary_00_Robe | publisher = [[MIT Press]] | location = Cambridge, MA | isbn = 0-262-68028-9 | pages = [https://archive.org/details/Elementary_00_Robe/page/n46 1]–8}}</ref> A játéknak van nyerő stratégiája.<ref>{{cite journal | doi = 10.2307/2689037 | last = Spitznagel | first = E. L. | year = 1973 | title = Properties of a game based on Euclid's algorithm | jstor = 2689037 | journal = Math. Mag. | volume = 46 | issue = 2 | pages = 87–92}}</ref>

== Jegyzetek ==
{{jegyzetek}}

== Források ==
* {{hely|Knuth 1994}}[[Donald Knuth|D. E. Knuth]]: A számítógépprogramozás művészete 1. Alapvető algoritmusok, Műszaki Könyvkiadó, Budapest, 2. kiadás, [[1994]], {{ISBN|963 1600750}}, 25–34. o.
* {{hely|Cohen 1993}}{{cite book |last=Cohen |first=H. |author-link=Henri Cohen (number theorist) |year=1993 |title=A Course in Computational Algebraic Number Theory |url=https://books.google.com/?id=hXGr-9l1DXcC |publisher=Springer-Verlag |location=New York |isbn=0-387-55640-0 |ref=harv |doi=}}
* {{hely|Cohn 1962}}{{cite book |last=Cohn |first=H. |year=1962 |title=Advanced Number Theory |url=https://books.google.com/?id=yMGeElJ8M0wC |publisher=Dover |location = New York |isbn=0-486-64023-X |ref=harv |doi= }}
* {{hely|Cox-Little-O'Shea 1997}}{{cite book |last1=Cox |first1=D. |last2=Little |first2=J. |last3=O'Shea |first3=D. |year=1997 |title=Ideals, Varieties, and Algorithms: An Introduction to Computational Algebraic Geometry and Commutative Algebra |url=https://books.google.com/?id=7eLkq0wQytAC |edition=2nd |publisher = Springer-Verlag |isbn=0-387-94680-2 |doi= |ref=harv }}
* {{hely|Crandall-Pomerance 2001}}{{cite book | last1 = Crandall | first1 = R. |last2= Pomerance |first2 = C. | author2-link = Carl Pomerance | year = 2001 | title = Prime Numbers: A Computational Perspective | url = https://archive.org/details/primenumberscomp0000cran | edition = 1st | publisher = Springer-Verlag | location = New York | isbn = 0-387-94777-9 | ref=harv}}
* {{hely|Lejeune Dirichlet 1894}}{{cite book |last=Lejeune Dirichlet |first=P. G. |author-link=Peter Gustav Lejeune Dirichlet |year=1894 |title=Vorlesungen über Zahlentheorie (Lectures on Number Theory) |editor-last=Dedekind |editor-first=Richard |editor-link=Richard Dedekind |publisher=Vieweg |location=Braunschweig |language=német |url=https://books.google.com/?id=WZIKAAAAYAAJ&printsec=frontcover#v=onepage&q&f=false |lccn=03005859 |oclc=490186017 |doi= |ref=harv }}. See also [[Vorlesungen über Zahlentheorie]]
* {{hely|Knuth 1997}}{{cite book|authorlink=Donald Knuth|last=Knuth|first= D. E.|year=1997|title=[[The Art of Computer Programming]], Volume 2: Seminumerical Algorithms|edition=3rd|publisher=Addison–Wesley| isbn=0-201-89684-2|ref=harv}}
* {{hely|LeVeque 1996}}{{cite book | last=LeVeque |first=W. J. |author-link=William J. LeVeque |origyear=1977 |year=1996 |title=Fundamentals of Number Theory | url=https://archive.org/details/fundamentalsofnu0000leve |publisher=Dover |location=New York |isbn=0-486-68906-9 |ref=harv }}
* {{hely|Mollin 2008}}{{cite book |last=Mollin |first=R. A. |year=2008 |title=Fundamental Number Theory with Applications |edition=2nd |publisher=Chapman & Hall/CRC |location=Boca Raton |isbn=978-1-4200-6659-3 |ref=harv }}
* {{hely|Ore 1948}}{{cite book |last=Ore |first=O. |author-link=Øystein Ore |year=1948 |title=Number Theory and Its History |url=https://archive.org/details/numbertheoryitsh00ore |publisher=McGraw–Hill |location=New York |ref=harv |doi= }}
* {{hely|Rosen 2000}}{{cite book |last=Rosen |first=K. H. |year=2000 |title=Elementary Number Theory and its Applications |edition=4th |publisher=Addison–Wesley |location=Reading, MA |isbn=0-201-87073-8 |ref=harv |doi= }}
* {{hely|Schroeder 2005}}{{cite book |last=Schroeder |first=M. |author-link=Manfred R. Schroeder |year=2005 |title=Number Theory in Science and Communication |edition=4th |publisher=Springer-Verlag |isbn= 0-387-15800-6 |ref=harv |doi= }}
* {{hely|Stark 1978}}{{cite book |last=Stark |first=H. |author-link=Harold Stark |year=1978 |title=An Introduction to Number Theory |url=https://archive.org/details/introductiontonu00star_0 |publisher=MIT Press |isbn=0-262-69060-8 |ref=harv }}
* {{hely|Stillwell 1997}}{{cite book |last=Stillwell |first=J. |author-link=John Stillwell |year=1997 |title=Numbers and Geometry |publisher=Springer-Verlag |location=New York |isbn=0-387-98289-2 |doi= |ref=harv }}
* {{hely|Stillwell 2003}}{{cite book |last=Stillwell |first=J. |author-link=John Stillwell |year=2003 |title=Elements of Number Theory |publisher=Springer-Verlag |location=New York |isbn=0-387-95587-9 |doi= |ref=harv }}
* {{hely|Tattersall 2005}}{{cite book |last=Tattersall |first=J. J. |year=2005 |title=Elementary Number Theory in Nine Chapters |url=https://archive.org/details/elementarynumber0000jame |publisher=[[Cambridge University Press]] |location=Cambridge |isbn = 978-0-521-85014-8 |ref=harv }}

== Fordítás ==
* {{fordítás|en|Euclidean algorithm}}

{{Portál|Matematika||Informatika|i }}
{{kiemelt}}

[[Kategória:Algoritmusok]]
[[Kategória:Számelmélet]]