Euklideszi algoritmus

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 példája a 49 és 21 számokkal; a legnagyobb közös osztó a 7 (Heath 1908:300)

Az euklideszi algoritmusA 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.). egy számelméleti algoritmus, amellyel két szám legnagyobb közös osztója határozható meg. Nevét az ókori görög matematikusról, Eukleidészről kapta, aki az Elemekben í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á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á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 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 egyenletek megoldására, mint amilyen például a kínai maradéktételben szereplő szimultán kongruenciarendszer. Alkalmas lánctörtbe 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észekre és egyváltozós polinomokra.

Háttere

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), – habár ez utóbbival más matematikai objektumokat is szoktak jelölni, például vektorokat.

Ha lnko(a, b) = 1, akkor a két szám relatív prím. Ebből nem következik, hogy a két szám prím, 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). 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.

A legnagyobb közös osztó megjeleníthető a következőképpen:

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ő. 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. Az euklideszi algoritmusnak az az előnye, hogy enélkül képes meghatározni a legnagyobb közös osztót.

A legnagyobb közös osztó egy másik definíciója a felsőbb matematikában, közelebbről a gyűrűelméletben hasznos. 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ő. 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. 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 rk−1 és rk−2 maradékokat használja. Mivel a maradékok folyamatosan csökkennek, azért rk−1 kisebb, mint rk−2. A cél az, hogy találjunk egy qk hányadost és egy rk maradékot, amellyel az

egyenlőség teljesül. Szavakkal, a nagyobb rk−2 számból a kisebb rk−1 többszöröseit vonja le, amíg egy még kisebb rk számhoz nem jut.

A (k = 0) kezdőlépésben az r−2 és r−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 kapott r0 maradékot használja, és így tovább. Így az algoritmus írható mint az

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 < b, akkor az első q0 hányados nulla lesz, és a maradék r0 = a. Ettől kezdve az rk maradék mindig kisebb lesz, mint az előző rk−1 maradék minden k ≥ 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 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ő r0 maradék között. Bizonyítás Az algoritmus érvényessége két lépésben bizonyítható.

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 euklideszi 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:

Mivel osztója -nek és -nek is, ezért a lineáris kombinációjuknak is. Az eljárást végigkövetve kapjuk, hogy és .

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

Példa 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 = 1071 és b = 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.

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:

kEgyenletHányados és maradék 0 1 2 ; az algoritmus befejeződik

Megjelenítése Az algoritmus megjeleníthető a legnagyobb közös osztó fent részletezett tulajdonsága alapján. 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 × r0 méretű téglalap marad. Ezután ezt r0 méretű négyzetekkel, majd a kimaradt területet r1 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 rk−2 = qk rk−1 + rk, ahol a maradék szigorúan kisebb, mint az osztó. A maradék és a hányados egyértelmű.

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 mod rk−1.

Az abszolút értékben legkisebb maradék módszere