Eukleidész, a „geometria atyja”
kezében körzővel és fatáblával.Az euklideszi algoritmus címben a névadó 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 szerepel. (Lásd például Püthagorasz, de Pitagorasz-tétel stb.) Az euklideszi algoritmus olyan számelméleti algoritmus, amellyel meghatározható két szám legnagyobb közös osztója. Nevét az ókori görög matematikusról, Eukleidészről kapta — ő (Kr. e. 300 körül) az Elemekben írta le. 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ó a két kiinduló szám lineáris kombinációjaként kifejezhető.
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 a kivonások helyett maradékos osztással. Ez azért célszerű, mert ha a nagyobb szám sokkal nagyobb, mint a kisebb, akkor sok kivonás kell 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 válik arányossá (sohasem nagyobb, mint a tízes számrendszerbeli jegyek számának ötszöröse). A 20. században tovább optimalizálták.
Az algoritmusnak számos alkalmazása van. A törtek egyszerűsítése mellett a
moduláris aritmetika osztás műveletében 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..
_(35347486494).jpg)
_(29827835706).jpg)
.jpg)
