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 oldalonNikomakhosz példája a 49 és 21 számokkal; a legnagyobb közös osztó a 7 (Heath 1908:300)
Alapötlete az, hogy alegnagyobb 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 amaradékos osztások 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ámlogaritmusá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 amoduláris aritmetika osztás műveletének megvalósításában is szerepel. Ehhez azax ≡c modb kongruenciát kell megoldani, ezt aLineáris diofantoszi egyenletek szakasz írja le részletesebben. Használhatódiofantoszi egyenletek megoldására, mint amilyen például akínai maradéktételben szereplő szimultán kongruenciarendszer. Alkalmaslánctörtbe fejtéshez ésirracioná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 anégynégyzetszám-tétel ésa számelmélet alaptétele.
Eredetileg egész számokra és szakaszokra használták, de a 19. században általánosítottákGauss-egészekre és egyváltozóspolinomokra.
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, egya-szorb-s téglalap akkor és csak akkor fedhető lec oldalú négyzetekkel, hac közös osztójaa-nak ésb-nek.
Az algoritmus alapesetbentermé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. Aza ésb számok legnagyobb közös osztójának jelölése lnko(a,b) vagy egyszerűbben (a,b),[2] – habár ez utóbbival más matematikai objektumokat is szoktak jelölni, példáulvektorokat.
Ha lnko(a,b) = 1, akkor a két számrelatív prím.[3] Ebből nem következik, hogy a két szám prím,[4] vagy egyikük prím, habár két különböző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). Mivela ésb többszöröseg-nek, azért ezek felírhatók, minta =mg, ésb =ng. Azm és azn 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 aza ésb számoknak vang-nél nagyobb közös osztójuk, tehátg nem legnagyobb közös osztó. A legnagyobb közös osztó a közös osztók többszöröse.[5]
A legnagyobb közös osztó megjeleníthető a következőképpen:[6]
Legyenek egy téglalap oldalaia ésb hosszúak. Ekkor a téglalap feloszthatóc oldalhosszú négyzetrácsra, hac közös osztójaa-nak ésb-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ő.[7] 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 akriptográfia ki is használ.[8] Az euklideszi algoritmusnak az az előnye, hogy enélkül képes meghatározni a legnagyobb közös osztót.[9][10]
A legnagyobb közös osztó egy másik definíciója a felsőbb matematikában, közelebbről agyűrűelméletben hasznos.[11] 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 ésb legnagyobb közös osztója felírható, mintua +vb, aholu ésv 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áltfőideál elemei, amely így megegyezik aza és ab á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 hogya ésb minden közös osztójag-nek is osztója, hiszenua +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ő.[12] 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.[13] 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ó.
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 ak index számolja nullától kezdődően. Így a kezdőlépés ak = 0, a következő lépés ak = 1 indexet használja, és így tovább.
Minden lépés azrk−1 ésrk−2 maradékokat használja. Mivel a maradékok folyamatosan csökkennek, azértrk−1 kisebb, mintrk−2. A cél az, hogy találjunk egyqk hányadost és egyrk maradékot, amellyel az
egyenlőség teljesül. Szavakkal, a nagyobbrk−2 számból a kisebbrk−1 többszöröseit vonja le, amíg egy még kisebbrk számhoz nem jut.
A (k = 0) kezdőlépésben azr−2 ésr−1 számok megfeleltethetők a kiindulási számoknak. A következő lépésben (k = 1) a kisebb kezdőszám és a nulladik lépésben kapottr0 maradékot használja, és így tovább. Így az algoritmus írható mint az
egyenlőségek sorozata.
Ha a kisebb szám aza, akkor az első lépésben az algoritmus felcseréli a számokat. Például, haa < b, akkor az elsőq0 hányados nulla lesz, és a maradékr0 =a. Ettől kezdve azrk maradék mindig kisebb lesz, mint az előzőrk−1 maradék mindenk ≥ 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,rN = 0[14] Az utolsó nem nulla maradék lesz a legnagyobb közös osztó. AzN nem lehet végtelen, mert csak véges sok egész van a nulla és az elsőr0 maradék között.
Az algoritmus érvényessége két lépésben bizonyítható.[15]
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 azeuklideszi osztás során a maradék kisebb, mint az osztóabszolút értéke, 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):
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:
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, 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ó. Ekkor, mivel is közös osztó,. 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:
.
.
Mivel a feltételünk az volt, hogy osztója-nek, ezért az oszthatóság definíciója miatt. QED
Az euklideszi algoritmus megjelenítése. A kiindulási téglalap méreteia = 1071 ésb = 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:
Tehát a legnagyobb közös osztó a 45.
Aza = 1071 ésb = 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:
Az algoritmus megjeleníthető a legnagyobb közös osztó fent részletezett tulajdonsága alapján.[18] Aza ×b méretű téglalapot megpróbáljuk lefedni a kisebb számnak megfelelő méretű négyzetekkel, amelyből a kisebb szám ×r0 méretű téglalap marad. Ezután eztr0 méretű négyzetekkel, majd a kimaradt területetr1 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ódszerben a maradékos osztás definíciója alapján vannak olyan számok, hogyrk−2 =qkrk−1 +rk, ahol a maradék szigorúan kisebb, mint az osztó. A maradék és a hányados egyértelmű.[19]
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:rk =rk−2 modrk−1.
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.[20][21] Az általános algoritmus felteszi, hogy az
rk−2 =qkrk−1 +rk
egyenletben |rk−1| > rk > 0. Ezzel szemben kiszámítható egy negatív maradék is:
rk−2 = (qk + 1)rk−1 +ek
hark−1 > 0, vagy
=rk−2 = (qk − 1)rk−1 +ek,
hark−1 < 0.
Hark helyett az algoritmusek-t veszi, ha |ek| < |rk|, akkor teljesülni fog, hogy:|rk| ≤ |rk−1| / 2
Leopold Kronecker belátta, hogy az összes változat közül ennek a lépésszáma a legkisebb,[22][21] mindena,b kiinduló számpárra akkor és csak akkor minimális a lépésszám, haqk-t úgy választja, hogy, ahol azaranymetszés.[23]
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 azy = Φx, vonalát követik, ahol Φ azaranymetszés.
Az algoritmus a leggyorsabban akkor ér véget, ha.
Az algoritmus a szomszédosFibonacci-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
ami megfelel a maradékos osztás definíciójának. Ez Émile Léger eredménye (1837).[24]
Szakaszok esetén is értelmezhető amaradé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[25] 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ámoka,b, ésb <a, akkor a korlátb. Később jobb becslést is adott:b/2 + 2.,[26] P.-J.-E. Finck 1841-ben megmutatta, hogy az osztások száma legfeljebb,[27] így az algoritmus polinomiális a bemenet méretében.[24]Ezt 1844-ben Gabriel Lamé finomította azzal,[28] 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.[29][30]
Az egységes költség modellben Lamé eredménye szerint a költségO(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(h2) lesz.[31] Ekkor a lépésszámra egyteleszkopikus összeget kaphatunk, amely szintén ezt a becslést adja. A modern gyors egészszorzásosSchönhage–Strassen algoritmussal felgyorsítható, így az algoritmuskvázilineáris lehet.[32][33]
Két természetes szám,a ésb legnagyobb közös osztójának kiszámításához szükséges lépések számátT(a, b) jelöli.[34] Haa ésb legnagyobb közös osztójag, akkora = mg,b = ng, és azn ésm természetes számok relatív prímek. Ekkor
T(a,b) =T(m,n)
ami belátható, ha az algoritmusban mindenütt végigosztunkg-vel.[35] Hasonló teljesül, ha végigszorzunk egy közös tényezővel:
w:T(a,b) =T(wa,wb).
Így aT 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
Ha az algoritmus egya > b > 0 számpárraN lépést tesz meg, akkor a legkisebb ilyen számpár aFibonacci-sorozat két szomszédos tagja,FN+2 ésFN+1.[37] Ez teljes indukcióval látható be.[38] HaN = 1, akkorb osztójaa-nak.[39] A legkisebb ilyen pozitív számpárb = 1 ésa = 2, amelyek rendre megegyeznekF2-vel ésF3-mal.
Most tegyük fel, hogy az állítás már be van bizonyítva mindenN-re egészenM − 1-ig. Az első lépésa = q0b + r0, és a másodikb = q1r0 + r1. Az algoritmus rekurzív természete miattM − 1 lépés kell lnko(b, r0) megtalálásához, és legkisebb értékükFM+1 ésFM. Emiatta legkisebb lehetséges értékeq0 = 1, innena = b + r0 = FM+1 + FM = FM+2. Ezt a bizonyítástGabriel Lamé adta 1844-ben, ami abonyolultságelmélet kezdetét jelenti,[40] továbbá az első példa a Fibonacci-számok gyakorlati felhasználására.[41]
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.[42] Ha az algoritmusN lépést tesz meg, akkorb legalábbFN+1, amelynek alsó becsléseφN−1, aholφ az aranymetszés. Mivelb ≥ φN−1, azértN − 1 ≤ logφb. Mivelhogy log10φ > 1/5, (N − 1)/5 < log10φ logφb = log10b. EzértN ≤ 5 log10b. Tehát az euklideszi algoritmus mindig legfeljebbO(h) osztást igényel, aholh a kisebb szám jegyeinek száma.
Az átlagos lépésszám többféleképpen is definiálható. Az egyik definíció szerint aT(a) átlagos időt úgy mérjük, hogy aza 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.[43]
Azonban, mivelT(a, b) erősen változik a legnagyobb közös osztóval együtt, aT(a) függvény is ennek megfelelően zajos.[44] Emiatt vezették be azt az átlagot, amely csak a relatív prímekkel számol:
Aza-nál kisebb relatív prímek számaφ(a), aholφ azEuler-függvény. Ez már elég jól becsülhető:[45][46]
A hibataga−(1/6) + ε, ahol ε tetszőlegesen kicsi. A képletben aC (Porter-konstans[47]):
ahol γ az Euler–Mascheroni-konstans és ζ' a Riemann-féle zétafüggvény deriváltja.[48][49] A főegyüttható, (12/π2) ln 2 két, egymástól független módszerrel határozható meg.[50][51]
Az első átlagfüggvény aza szám osztóinak tau átlagával számítható ki:[52]
A harmadik átlag azY(n), amely a várható lépésszámot adja meg, ha a két számot az 1-tőln-ig terjedő számok közül egyenletes valószínűséggel sorsolják.[53]
Behelyettesítve aT(a)-ra vonatkozó approximációt adódikY(n) approximációja:[55]
Az algoritmus mindenk-adik lépésében aqk hányados és azrk maradékot számítja ki azrk−2 ésrk−1 számokból kiindulva:
rk−2 =qkrk−1 +rk.
A költséget inkább aqk hányados kiszámítása jelenti, mert a maradék gyorsan megkapható:
rk =rk−2 −qkrk−1.
Kéth bites szám osztásának költségeO(h(ℓ+1)), aholℓ a hányados hossza.[56]
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 adottq szám hányados, megközelítőleg ln|u/(u − 1)|, aholu = (q + 1)2.[57] 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,[58] így a kivonásos módszer versenyképes az osztásossal.[59]
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 (h2). Reprezentáljákh0, :h1, …,hN−1 azr0, r1, …, rN−1 maradékok jegyeinek számát! Mivel a lépésekN száma lineárisan nőh-val, a futási idő korlátja:
Egyszerűsége miatt az euklideszi algoritmus széles körben használt, különösen kis számokra.[60] 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.[61] 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á.[62]
Abiná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.[63][64] Ennek a műveletigénye szinténO(h²). Mindazonáltal a gyorsabb műveletek miatt gyorsabban fut, mint az euklideszi algoritmus, azonban ugyanúgy skálázódik.[65] A hatékonyság tovább javítható, ha a számoknak csak az első jegyét tekintik.[66][67] Az algoritmus más számrendszerekre is kiterjeszthető, amivel a sebesség ötszörösére növelhető.[68] 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.[69] Ezek közé tartoznak Schönhage,[70][71] és Stehlé és Zimmermann módszere.[72] Ezek az euklideszi algoritmus mátrixos alakját használják fel. SebességükO(h (logh)2 (log logh)).[73][33]
A k-adik iterációban ab változó tartalmazzark−1-et, míg aza a megelőzőt,rk−2-t. A b = a%b; lépés megfelel a fentirk ≡rk−2 modrk−1 formulának. Atemp változó ark−1 értékét tartalmazza azrk kiszámítása közben. A ciklus végénb tartalmazzark-t, ésa az előző maradékot,rk−1-et.[74]
A rekurzió azt használja ki,[75] hogy a maradékképzés során megmarad a legnagyobb közös osztó, és a megállási feltétel lnko(rN−1, 0) = rN−1. Például az lnko(1071, 462) kiszámítható azzal, hogy lnko(462, 1071 mod 462) = lnko(462, 147). Ez ugyanaz, mint lnko(147, 462 mod 147) = lnko(147, 21), azaz lnko(21, 147 mod 21) = lnko(21, 0) = 21.
A kivonásos változatban maradékképzés helyett ismételt kivonás szerepel.[76] Az osztásos módszerrel szemben ez csak pozitív számokra működik, és megáll, haa =b. Pszeudokódja:
function gcd(a, b)while a ≠ bif a > b a := a − b;else b := b − a;return a;
Aza ésb változók felváltva tárolják a maradékokat. Feltéve, hogy az elején aza a nagyobb,a =rk−2, mivelrk−2 >rk−1. Az adott iterációban aza változót az előző maradék többszöröseivel csökkenti, amíga kisebbé nem válik, mintb. Ekkora =rk, és a szerepek megcserélődnek, amivel azrk+1 maradékot számolja ki, majd újabb szerepcsere, és így tovább.
defLnko(a,b):ifa==b:returnaifb<a:a,b=b,awhile(0<a):a,b=b%a,areturnba=int(input("Adjon meg egy szamot: "))b=int(input("Adjon meg egy masik szamot: "))print(Lnko(a,b))
ABézout-lemma szerint aza és ab számok legnagyobb közös osztója előállítható, mintg = sa + tb, ahols ést egész számok.[77] Másképpen szólva mindig lehetséges olyans ést egészeket találni, hogyg = sa + tb.[78][79]
Azs és at aq0,q1, … hányadosokból számítható, az algoritmus megfordításával.[80] Elindulva visszafelé,g kifejezhető aqN−1 hányadossal és a két korábbirN−2 ésrN−3 maradékkal:
g =rN−1 =rN−3 −qN−1rN−2 .
Ezek a maradékok hasonlóan írhatók fel:
rN−2 =rN−4 −qN−2rN−3 és
rN−3 =rN−5 −qN−3rN−4 .
Visszahelyettesítve kapjuk ag legnagyobb közös osztót mintrN−4 ésrN−5 lineáris kombinációját. Ezt folytatjuk, amíg el nem érünk az első két számhoz:
r2 =r0 −q2r1
r1 =b −q1r0
r0 =a −q0b.
Az összesr0,r1, … maradék helyettesítése után kifejezzükg-t, minta ésb lineáris összegét:g = sa + tb. A Bézout-lemma és az euklideszi algoritmus általánosítható az euklideszi tartományokra (normált, nullosztómentes, nem nullgyűrű).
A Bézout-lemma egy újabb definíciót ad a legnagyobb közös osztóra.[81] Tekintsük azokat a számokat, amelyek kifejezhetőkua + vb alakban, aholu,v egészek. Mivela ésb is oszthatóg-vel, azért ezek a számok is oszthatók lesznekg-vel. Más szavakkal, a halmaz minden eleme többszöröseg-nek, amia ésb összes közös osztójára igaz, de ag 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 legyeng-vel. Továbbá a legnagyobb közös osztó minden többszöröse kifejezhető lineáris kombinációként,u = ms ésv = mt választással, ahols ést a Bézout-lemma által megadott egészek. Ez látható, ha a lemma egyenletét megszorozzukm-mel:
mg =msa +mtb.
Ezért azua + vb alakú számok halmaza megegyezikg 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ó.[82] Az öntögetési feladatokban adva van két edény,a ésb űrtartalommal. Egy harmadik, elég nagy térfogatú edényben hozzátöltéssel és elvétellel bármelyua + vb űrtartalom kimérhető. Ezek mindg = lnko(a, b) többszörösei.
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:[83]
sk =sk−2 −qksk−1
tk =tk−2 −qktk−1
ahol a kezdőértékek:
s−2 = 1,t−2 = 0
s−1 = 0,t−1 = 1.
A rekurzióval azs = sN ést = tN, aholN+1 az algoritmus utolsó lépése, amikorrN+1 = 0.
A megközelítés helyessége teljes indukcióval bizonyítható. Feltesszük, hogy az algoritmus helyesen működik ak − 1. lépésig, azaz
rj =sja +tjb
mindenk-nál kisebbj-re. Ak-adik lépésből adódik, hogy
rk =rk−2 −qkrk−1.
Mivel a rekurziós képlet korrektrk−2 ésrk−1 esetén, ez kifejezhetős ést segítségével:
A kiterjesztett algoritmusban szereplős ést megtalálható az ekvivalens mátrixmódszerrel is.[84]
Az algoritmus egyenletei
a =q0b +r0
b =q1r0 +r1
…
rN−2 =qNrN−1 + 0
írhatók úgy is, hogy egy kétszer kettes mátrixot megszorozzuk a két dimenziós maradékvektorral:
Reprezentáljuk az összes hányadosmátrix szorzatátM-mel:
ezzel az algoritmus a következő alakra egyszerűsödik:
Ahhoz, hogy ag legnagyobb közös osztót kifejezzük, az egyenlet mindkét oldalát meg kell szorozniM inverzével.[84][85] AzM inverze létezik, hiszen determinánsa (−1)N+1, mivel megegyezik a hányadosmátrixok determinánsainak szorzatával, amelyek mindegyike mínusz egy. Ekkor az egyenlet megoldása:
Az első egyenlet szerint
=g = (−1)N+1 (m22a −m12b),
ígys = (−1)N+1m22 ést = (−1)Nm12. 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.[86] Ennek bemutatására: Legyen azL szám két tényező szorzata,L =uv. Ekkor, haL osztható egyw számmal, és ez relatív prímu-hoz, akkor osztójav-nek. Ez a következő gondolatmenettel belátható: Hau ésw relatív prímek, akkor vans ést, hogy
1 =su +tw
a Bézout-egyenlőség miatt. Az egyenletetv-vel szorozva:
v =suv +twv =sL +twv
Mivelw a jobb oldal minden tagjának osztója, azért osztója kell, hogy legyen a bal oldalnak.[87]
Speciálisan, ha egy prímszám osztójaL-nek, akkorL valamelyik tényezőjének is osztója kell, hogy legyen. Egy másik megfordítás szerint, haa1,a2, …,an relatív prímekw-hez, akkor szorzatuk is relatív prímw-hez.[88]
Mindezekkel már könnyen belátható a prímtényezős felbontás egyértelműsége.[89] Tegyük fel indirekt, hogy azL egész számnak két lényegileg különböző prímtényezős felbontásábanm, illetven tényező szerepel, azaz
L =p1p2…pm =q1q2…qn .
Mivel mindenp osztójaL-nek, azért legalább egyq-nak osztójának kell lennie; de mivel prím, ezért lényegében meg kell vele egyeznie. Mindenp-t ésq-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.
A 9x + 12y = 483 diofantoszi egyenlet megoldásai. A megoldásokat kék körök jelzik
Adiofantoszi egyenletek azok, amelyek megoldásaként csak egész számok fogadhatók el. A név a Kr. e. 3. századiDiofantoszra utal.[90] A lineáris két ismeretlenes alakja
ax +by =c
A diofantoszi egyenletbena,b,c,x ésy egész számok, ésa,b ésc adottak.[91] Moduláris aritmetikával:
ax ≡c modb.
Legyeng aza és ab legnagyobb közös osztója. Ekkorax + by mindkét tagja oszthatóg-vel, így az egyenlet csak akkor oldható meg, hac is oszthatóg-vel. Ekkor mindkét oldalt leosztvac/g-vel visszajutunk a Bezout-egyenlethez:
sa +tb =g
ahols ést a kiterjesztett euklideszi algoritmussal található meg.[92] Innen kapunk egy megoldást:x1 = s (c/g) ésy1 = t (c/g).
Egy lineáris diofantoszi egyenletnek vagy nincs megoldása, vagy végtelen sok megoldása van.[93] Ennek belátására legyen két megoldás az (x1, y1) és az (x2, y2), ahol
ax1 +by1 =c =ax2 +by2
vagy ekvivalenesen
a(x1 −x2) =b(y2 −y1).
Emiatt a kétx közötti legkisebb különbségb/g, és azy megoldások közötti legkisebb különbséga/g. Ezzel a megoldások:
x =x1 −bu/g
y =y1 +au/g
Ha megengedett, hogyu 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.[94] Ez különbözik attól az esettől, amikor a megengedett megoldások nemcsak egészek lehetnek.
Az euklideszi algoritmus használatával lineáris diofantoszi egyenletrendszerek oldhatók meg.[95] 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:
aholmi-k[96] az egyes modulusok, ésxi a hozzájuk tartozó maradékok.
Az egyenletrendszer megoldásához ki kell számítani azx egész számot, illetve maradékosztályt moduloM, aholM a modulusok szorzata. Legyen mostMi a következő:
Ekkor mindenMi a modulusok szorzata, kivéve azmi modulust. A megoldás azon múlik, hogy találjunkhi számokat, hogy
Ezekkel ahi számokkal minden,M-nél kisebb egészx rekonstruálható maradékaiból az
egyenlet alapján. Definíciójuk szerint ahi számok azMi inverzei, amelyek kiszámíthatók az euklideszi algoritmussal.
Az euklideszi algoritmussal a pozitív racionális számok halmaza végtelen bináris keresőfába rendezhető; eztStern–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.[97] 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.
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:
Az euklideszi algoritmusnak hasonló a kapcsolata aCalkin–Wilf-fával, de ott az irány fordított: a számtól elindulva kell eljutni az egyhez.
Az euklideszi algoritmus kapcsolatba hozható alánctörtekkel.[98] Az egyenletek írhatók úgy is, mint
Megfigyelhető, hogy a jobb oldal utolsó tagja a bal oldal inverze. Így az első két egyenlet írható úgy is, mint
A harmadik egyenletben behelyettesítve azr1/r0 hányadossal:
Azrk/rk−1 végső arány helyettesíthető a következő egyenlet szerint, egészen az utolsó egyenletig. A végeredmény egy lánctört:
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:
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, mintracionális számok,polinomok,[105]kvadratikus egészek,[106] ésHurwitz-kvaterniók.[107]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.
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áma, a másikb, akkor vanm ésn egész szám, amellyela =mg ésb =ng.[108] Ezek ugyanúgy találhatók meg, mint az egészeknél azs és at együtthatók, amelyekkelsa +tb = 0. Eukleidész ezt az algoritmust használta a nem összemérhető szakaszok tanulmányozására.[109][110]
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 isrk jelöli, a hányadosokqk-k. Aza/b =mg/ng =m/n tört lánctört alakja: [q0;q1,q2, …,qN]. Ha aza/b arány irracionális, akkor végtelen lánctörtet kapunk, amelynek lánctört alakja [q0;q1,q2, …].[111] Például az aranymetszés arányszámaφ = [1; 1, 1, …], és a 2 négyzetgyöke [1; 2, 2, …].[112]
Valós számokon az algoritmus leállása nulla valószínűségű, ugyanis majdnem minden valós szám irracionális..[113] A lánctörtek kezdeti szakaszai (k lépés után [q0;q1,q2, …,qk]) 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 éppenmk/nk, 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:
mk =qkmk−1 +mk−2 és
nk =qknk−1 +nk−2
aholm−1 =n−2 = 1 ésm−2 =n−1 = 0 arekurzió kezdőértékei. Azmk/nk konvergens sorozat a legjobb racionális számokból álló közelítő sorozat aza/b-hez aznk nevezővel:[114]
Az egy változós polinomok adottgyű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) ésb(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.[105]
Az eljárás hasonlít az egészekéhez. Ak-adik lépésben aqk(x) hányados és azrk(x) maradék polinom eleget tesz az
rk−2(x) =qk(x)rk−1(x) +rk(x)
rekurzív egyenletnek, aholr−2(x) = a(x) ésr−1(x) = b(x). A hányados polinomqk(x)rk−1 együtthatóját úgy választják, hogy megegyezzenrk−2(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.[115]
Például vegyük a következő, másodfokú polinomok szorzatára bomló polinomokat:
Az első maradék aza(x) /b(x) osztást elvégezver0(x) =x3 + (2/3)x2 + (5/3)x − (2/3). A következő lépésbenb(x)-et osztjukr0(x)-szel, és maradékkéntr1(x) =x2 +x + 2 adódik. Végül azr0(x) osztásr1(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,[116] í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 aSturm-láncok egy adott intervallumban keresik a polinom gyökeit.[117] Ennek további felhasználási területei vannak avezérléselméletben aRouth–Hurwitz stabilitási kritérium.[118]
A fentiek akkor is alkalmazhatók, ha az együtthatók a véges testek elemei, vagy lehetnek más, általánosabb testből.[105]
AGauss-egészek α = u + vi alakú komplex számok, aholu ésv valós egészek, ési a képzetes egység.[119]Az euklideszi algoritmus bevezetésével megmutatható, hogy egyértelműen bomlanak fel, ahogy azt a fenti Bézout-egyenlőség is mutatja.[120] Ezt aztán több alkalmazásban is felhasználják, mint a pitagoraszi számhármasok előállítása.[121] 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.[122] Itt aqk hányadost és azrk maradékot úgy választják, hogy
rk =rk−2 −qkrk−1,
ahol α, β kiindulási Gauss-egészek, ésrk−2 = α,rk−1 = β. A maradékok nagyságának csökkenését a komplex abszolút értékben mérik, tehát |rk| < |rk−1| valós nem negatív egészek, ami ahhoz kell, hogy bizonyítható legyen az algoritmus végessége.[123] A maradékok és a hányadosok Gauss-egészek. Aqk 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.[122]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.[124]
Több alkalmazás is átvihető Gauss-egészekre, például a lineáris diofantoszi egyenletek és a szimultán kongruenciarendszerek megoldása.[125] A lánctörtbe fejtés is elvégezhető.[122]
Azeuklideszi gyűrűkkommutatív gyűrűk, amelyekben euklideszi norma biztosítja, hogy elvégezhető az euklideszi algoritmus.[126][127] Ez egyf 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 haa ésb a gyűrű nullától különböző elemei, akkor van olyanq ésr elem, hogya =qb +r ésf(r) <f(b).[128] Ilyen norma a polinomoknál a fok[129] és a Gauss-egészeknél az abszolút érték négyzete.[130]
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űkegyértelmű faktorizációs gyűrűk. Megfordítva azonban nem minden egyértelmű faktorizációs gyűrű euklideszi.[131] 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.[132] Az euklideszi gyűrűkfőideáltartományok[forrás?], azazintegritási tartományok, ahol minden ideál főideál. A főideálgyűrűk azonban nem biztos, hogy euklideszi gyűrűk.[133]
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 apitagoraszi számhármasok.[134] Ezen felbuzdulvaGabriel 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.[135] Bizonyítása azon a feltevésen alapult, hogy azx + ωy alakú számok egyértelműen faktorizálhatók, aholx,y egészek, és ω =e2iπ/nn-edik komplex egységgyök, azaz ωn = 1. Az alapfeltevés azonban nem igaz mindenn-re, ígyErnst Kummer az ideális számok bevezetésével próbálta javítani a hibát, ami alapjánRichard Dedekind megalapozta azideálok fogalmát.[136]
Akvadratikus testek egészgyűrűi segítenek bemutatni az euklideszi gyűrűket.
A kvadratikus testek a racionális számtest alakú másodfokú bővítései, aholD négyzetmentes egész szám.
Egy adott kvadratikus test egészgyűrűjének elemeit kvadratikus egészeknek nevezzük. AdottD-re a kvadratikus egészek tehát azalgebrai egészek gyűrűjének részgyűrűjét alkotják. Az egészgyűrű elemeitD = −1 esetbenGauss-egészeknek,D = −3 esetbenEisenstein-egészeknek nevezzük. Minden kvadratikus egész felírható alakban, aholu ésv egész vagyfélegész. (Az utóbbi csak akkor fordulhat elő, haD 4-gyel osztva egyet ad maradékul, ésu ésv csak egyszerre lehet félegész.)
AGauss-egészek normafogalma kézenfekvő módon általánosítható a kvadratikus egészek körében: normája. Kimutatható, hogy a kvadratikus egész gyűrűkezzel a normával pontosan akkor euklidesziek, haD = −11, −7, −3, −2, −1, 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57 vagy 73.[137][138]
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 melyD-kre található ilyen euklideszi norma,[139] de egy 1994-es eredmény szerintD = 69-re a kvadratikus egészek euklideszi gyűrűt alkotnak.[139] 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.[106]
Nem kommutatív gyűrűkben is alkalmazható az euklideszi algoritmus, például aHurwitz-kvaternióknál.[140] 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.[141]
A jobb oldali változat első lépése:
ρ0 = α − ψ0β = (ξ − ψ0η)δ
ahol ψ0 a hányados, és ρ0 a maradék. Az egyenlet szerint α és β jobb oldali közös osztói a ρ0 maradéknak is osztói.
A bal oldali változat hasonlóan kezdődik:
ρ0 = α − βψ0 = δ(ξ − ηψ0) .
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.[142]
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ó[143]
Γright = σα + τβ
vagy a legnagyobb bal közös osztó
Γleft = ασ + βτ .
Ezek felhasználhatók a diofantoszi egyenletek és a szimultán kongruenciarendszerek megoldásához. Ezen alapszik anégynégyzetszám-tétel egy bizonyítása kvaterniókkal.[142]
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.[144] EukleidészElemek 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. AzElemekben korának matematikai ismereteit gyűjtötte össze.[108][145] B. L. van der Waerden matematikus és történész szerint a 7. könyv számelméleti részei apitagoreusoktól származnak.[146] Az algoritmus helyességét valószínűlegKnidoszi Eudoxosz bizonyította először Kr. e. 375 körül.[147][148] Az algoritmus valószínűleg Eudoxosz előtt is ismert volt,[149][150] 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ó.[151]
Néhány évszázaddal később Kínában és Indiában is felfedezték az euklideszi algoritmust,[152] é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[153] a diofantoszi egyenletek megoldására.[154] A kínai maradéktétel egy speciális esetét aSzunce szuancsing(Sūnzĭ Suànjīng) című mű írta le,[155] de a tétel általános leírásátCsin Csiu-sao(Qin Jiushao) adta 1247-es könyvében, amelynek címeSusu csiucsang(Shushu Jiuzhang) (數書九章, Értekezés a matematikáról kilenc részben).[156]
Európában sokáig csak azElemek 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).[157] 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.[158]
A 19. században újabb számköröket vezettek be. Az euklideszi algoritmus hatékony eszköznek bizonyul aGauss-egészek és azEisenstein-egészek 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.[120] Az 1801-ben kiadott Disquisitiones Arithmeticae csak a lánctörtekkel kapcsolatban említi meg az algoritmust.[159] 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.[160] Kimutatta, hogy az egyértelmű faktorizáció minden olyan számkörben teljesül, ahol az euklideszi algoritmus alkalmazható.[161] Számelméleti előadásait Richard Dedekind szerkesztette össze és bővítette ki. Dedekind az algoritmus segítségével tanulmányozta azalgebrai egészeket, a számok új általános típusát. AGauss-egészek egyértelmű felbontására alapozva bizonyította be akétnégyzetszám-tételt.↑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 Dedekindideáljai háttérbe szorították az euklideszi algoritmust.[162]
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.[163]
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,[164] illetve a Lenstra–Lenstra–Lovász-algoritmus.[165][166]
1969-ben Cole és Davie egy kétszemélyes játékot alkotott az euklideszi algoritmusra alapozva, ez a The Game of Euclid.[167] 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.[168][169] A játéknak van nyerő stratégiája.[170]
↑A matematikus nevének szabatos átírásaEukleidész volna, tehát a szerkezeteukleidészi algoritmus, de ebben a kifejezésben hagyományosan rögzülteuklideszi alakban (lásd példáulPüthagorasz, dePitagorasz-tétel stb.).
↑Reynaud, A.-A.-L..Traité d'arithmétique à l'usage des élèves qui se destinent à l'École Polytechnique, 6th, Paris: Courcier (1811) As cited by (Shallit 1994).
↑Finck, P.-J.-E..Traité élémentaire d'arithmétique à l'usage des candidats aux écoles spéciales. Derivaux (1841)
↑Lamé, G. (1844). „Note sur la limite du nombre des divisions dans la recherche du plus grand commun diviseur entre deux nombres entiers”.Comptes Rendus Acad. Sci.19, 867–870. o.
↑Dixon, J. D. (1970). „The Number of Steps in the Euclidean Algorithm”.J. Number Theory2 (4), 414–422. o.DOI:10.1016/0022-314X(70)90044-2.
↑Heilbronn, H. A..szerk.: Paul Turán: On the Average Length of a Class of Finite Continued Fractions,Number Theory and Analysis. New York: Plenum, 87–96. o. (1969)
↑abNorton, G. H. (1990). „On the Asymptotic Analysis of the Euclidean Algorithm”.Journal of Symbolic Computation10, 53–58. o.DOI:10.1016/S0747-7171(08)80036-3.
↑Sorenson, Jonathan P..High primes and misdemeanours: lectures in honour of the 60th birthday of Hugh Cowie Williams, Fields Institute Communications. Providence, RI: American Mathematical Society, 327–340. o. (2004) „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 thek-ary GCD algorithm for larger numbers.”
↑Stein, J. (1967). „Computational problems associated with Racah algebra”.Journal of Computational Physics1 (3), 397–405. o.DOI:10.1016/0021-9991(67)90047-2.
↑Cesari, G..szerk.: G. Buhler: Parallel implementation of Schönhage's integer GCD algorithm,Algorithmic Number Theory: Proc. ANTS-III, Portland, OR, Lecture notes in Computer Science. New York: Springer-Verlag, 64–76. o. (1998)
↑Shor, P. W. (1997). „Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”.SIAM Journal on Scientific and Statistical Computing26, 1484. o.DOI:10.1137/s0097539795293172.
↑Jones, A.. Greek mathematics to AD 300,Companion encyclopedia of the history and philosophy of the mathematical sciences. New York: Routledge, 46–48. o. (1994).ISBN 0-415-09238-8
↑Becker, O. (1933). „Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid”.Quellen und Studien zur Geschichte der Mathematik B2, 311–333. o.
↑Knuth 1994: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.
Ez a szócikk részben vagy egészben azEuclidean algorithm című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
