мини|100п|Анимација Еуклидовог алгоритма за бројеве 252 и 105. Јединични сегменти су заправо дужине 21, што је највећи заједнички делилац датих бројева (НЗД). У сваком кораку, мањи број се одузима од већег, све док се један од њих не сведе на нулу. Остатак је НЗД полазних бројева.
У математици, Еуклидов алгоритам је ефикасан начин за одређивање највећег заједничког делиоца (НЗД) датих бројева. Алгоритам носи име по старогрчком математичару Еуклиду, који га је навео у -{VII}- и -{X}- књизи својих Елемената.
НЗД два броја је највећи број који истовремено дели оба без остатка. Еуклидов алгоритам је заснован на принципу да се највећи заједнички делилац два броја не мења уколико се мањи број одузме од већег, па се затим одреди НЗД новодобијеног броја и мањег од претходна два. На пример, 21 је НЗД за 252 и 105 (252 = 21 × 12; 105 = 21 × 5); пошто је 252 − 105 = 147, НЗД за 147 и 105 је такође 21. Како је већи од два полазна броја на овај начин смањен, понављањем поступка добијаће се све мањи бројеви, док се један од њих не сведе на нулу. У том тренутку, други број је једнак највећем заједничком делиоцу два полазна броја. Уколико се обрне редослед корака у Еуклидовом алгоритму, НЗД се може изразити као збир два полазна броја од којих је сваки помножен неким целим бројем, у претходном примеру је 21 = 5 × 105 + (−2) × 252. Ова важна особина је позната као Безуов идентитет.
Први познати сачувани опис Еуклидовог алгоритма се налази у Елементима (око 300. п. н. е.), што га чини најстаријим нумеричким алгоритмом који се још увек активно користи. У оригиналу, објашњен је само за природне бројеве и геометријске дужине (реалне бројеве), али је у 19. веку уопштен на полиноме једне променљиве и на Гаусове целе бројеве, што је довело до развоја нових појмова апстрактне алгебре као што је Еуклидски домен. Еуклидов алгоритам је даље уопштаван на другим математичким структурама, попут чворова и полинома више променљивих.
Еуклидов алгоритам има широку теоријску и практичну примену. Представља кључан елемент -{RSA}- алгоритма, методе асиметричне криптографије која се у значајној мери примењује у електронском пословању. Користи се при решавању диофантских једначина, на пример код одређивања бројева који задовољавају вишеструке конгруенције (Кинеска теорема о остацима) или при одређивању мултипликативног инверза коначног поља. Може се употребити за конструисање верижних разломака, у Штурмовој методи за одређивање реалних нула полинома, и још неколико савремених алгоритама за факторизацију природних бројева. На крају, Еуклидов алгоритам је основно средство за доказивање теорема модерне теорије бројева, као што су Лагранжова теорема о четири квадрата и основна теорема аритметике о јединственој факторизацији природних бројева.
Еуклидов алгоритам је ефикасан начин за одређивање НЗД великих бројева због тога што му не треба више корака од петоструког броја цифара мањег броја записаног са основом 10, што је доказао Габријел Ламе 1844. године и тиме означио почетак теорије комплексности. У 20. веку су развијене методе за побољшање ефикасности Еуклидовог алгоритма.
Историја мини|150п|Еуклидов алгоритам је вероватно био познат вековима пре Еуклидовог рођења. Део Рафаелове фреске Атинска школа на коме је приказан Еуклид са ученицима.
Еуклидов алгоритам је један од најстаријих алгоритама који се још увек употребљава.-{Knuth, The Art of Computer Programming, Volume 2. стр. 318. У писаном облику, први пут се појављује у Еуклидовим Елементима у 3. веку п. н. е., и то у -{VII}- (тврђења 1Еуклид, Елементи, и 2Еуклид, Елементи, књига -{VII, тврђење II ) и -{X}- књизи (тврђења 2Еуклид, Елементи, књига -{X, тврђење II и 3Еуклид, Елементи, књига -{X, тврђење III ). У -{VII}- књизи, алгоритам је формулисан за целе бројеве, док је у -{X}- књизи дата примена на дужи, па је он геометријске природе. НЗД за дате дужи -{a}- и -{b}- одговара дужи -{g}- која је највећа могућа дуж којом се могу измерити -{a}- и -{b}- подједнако. Другим речима, дужи -{a}- и -{b}- се могу добити множењем дужи -{g}- неким целим бројем.
Врло је вероватно да Еуклид није оригинални творац алгоритма, јер је он у Елементима сабрао до тада позната математичка знања. Математичар и историчар ван дер Варден сматра да је седма књига Елемената заснована на уџбенику теорије бројева који су написали математичари из питагорејске школе. Постоје индиције да је сам алгоритам био познат још Еудоксу са Книда (око 375. п. н. е.),-{Knuth, The Art of Computer Programming, Volume 2, pp. 318. а могуће је и да је старији, судећи по употреби техничког термина -{ἀνθυφαίρεσις (anthyphairesis}-, реципрочно одузимање) у делима Еуклида и Аристотела.
Вековима касније, Еуклидов алгоритам је поново независно откривен у Индији и Кини, првенствено као средство за одређивање решења диофантских једначина које су се појављивале при решавању астрономских проблема и прављењу прецизних календара. У другој половини петог века, индијски математичар и астроном Ариабхата описао је алгоритам као „дробилицу“, можда због његове ефикасности у решавању диофантских једначина. Иако је посебан случај Кинеске теореме о остацима навео већ кинески математичар и астроном Сун Тзу у 5. веку нове ере, опште решење је 1247. године објавио Цин Цзу-шао у својом делу Цзју чжан суан шу (, Девет књига о математичкој вештини).
У Европи, Еуклидов алгоритам је први пут описао Баше у другом издању свог дела -{Problèmes plaisants et délectables}- (Пријатни проблеми за уживање, 1624), а претпоставља се да је коришћен у решавању диофантских једначина и при конструкцији верижних разломака. Проширени Еуклидов алгоритам је, као методу за ефикасно израчунавање верижних разломака, објавио енглески математичар Николас Саундерсон, приписавши га Роџеру Коутсу.
У 19. веку, захваљујући Еуклидовом алгоритму, дошло је до развоја нових бројевних система, као што су Гаусови и Ејзенштајнови цели бројеви. Гаус је 1815. године употребио Еуклидов алгоритам да покаже јединствену факторизацију својих целих бројева, иако је тај рад објављен тек скоро две деценије касније, 1832. годинеВиди још и Werke, , а сам алгоритам је први пут споменут у његовој књизи Аритметичка истраживања () објављеној 1801. године, али само као метода за рад са верижним разломцима.
Чини се да је Дирихле био први аутор који је сматрао Еуклидов алгоритам за један од основних елемената теорије бројева. Приметио је да би велики број резултата теорије бројева (на пример, јединствена факторизација), био тачан у било ком другом систему бројева у коме би се могао применити Еуклидов алгоритам. Дирихлеова предавања о теорији бројева допунио је и прерадио Рихард Дедекинд, који је користио Еуклидов алгоритам за изучавање новог општег типа бројева - алгебарских целих бројева. Први је доказао Фермаову теорему о збиру два квадрата користећи јединствену факторизацију Гаусових целих бројева. Поред тога, Дедекинд је дефинисао и концепт Еуклидовог домена, бројевног система у коме је могуће дефинисати уопштење Еуклидовог алгоритма. Крајем 19. века, Еуклидов алгоритам је постепено занемарен у корист Дедекиндове општије теорије идеала.
„Еуклидов алгоритам је дека свих алгоритама, пошто је то најстарији нетривијални алгоритам који је преживео до данас.“ Доналд Кнут, -author= |title=The Art of Computer Programming, Vol. 2: Seminumerical Algorithms |location= |publisher= |year=1981 |isbn=|pages=318|edition=2nd-. .
Процес изналажења примена Еуклидовог алгоритма започет у 19. веку, наставио се до данас. Шарл Штурм је 1829. године показао да се алгоритам може употребити у Штурмовом ланцу који се користи за пребројавање реалних нула полинома у произвољно изабраном интервалу.
Еуклидов алгоритам је био први алгоритам за утврђивање целобројне повезаности, односно за налажење целобројних односа између самерљивих реалних бројева. Крајем 20. века је развијено неколико нових алгоритама који могу да проверавају целобројну повезаностJazzing Up Euclid's AlgorithmInteger Relation, на пример Фергусон-Форкејд алгоритам,Ferguson-Forcade Algorithm и њему сродни, ЛЛЛ алгоритамLLL Algorithm, -{HJLS}- алгоритамHJLS Algorithm, и -{PSLQ}- алгоритам.PSLQ Algorithm
Године 1969. под називом Еуклидова игра појавила се стратешка игра за два играча заснована на Еуклидовом алгоритму. На почетку, испред играча се налазе две гомиле са -{a}-, односно -{b}- каменчића. Они наизменично узимају по -{m}- каменчића са веће гомиле, где је -{m}- неки умножак броја каменчића у мањој гомили. Конкретно, уколико се у неком тренутку на гомилама налази -{x}-, односно -{y}- каменчића, где је -{x}- веће од -{y}-, играч на потезу може смањити већу гомилу са -{x}- на -{x − ky}- каменчића, под условом да је број каменчића које одузима ненегативан цео број. Победник је први играч коме пође за руком да избаци све каменчиће из једне гомиле.
Алгоритам Принцип Еуклидов алгоритам је итеративне природе, што значи да се крајњи резултат добија у низу корака, док се међурезултат произвољног корака користи у првом следећем. Уколико је -{k}- цео број којим су означени кораци алгоритма почевши од нуле, првом кораку одговара једнакост -{k}- = 0, другом -{k}- = 1, и тако даље.
Сваки корак почиње са два ненегативна остатка -{rk−1}- и -{rk−2}-. Како алгоритам осигурава да се остаци сваким кораком непрекидно смањују, -{rk−1}- је мање од свог претходника -{rk−2}-. Циљ -{k}--тог корака је да се одреде количник -{qk}- и остатак -{rk}- такви да важи једнакост
-{rk−2 = qk rk−1 + rk}-
где је -{rk < rk−1}-. Другим речима, умношци мањег броја -{rk−1}- се одузимају од већег броја -{rk−2}- све док је добијени остатак мањи од -{rk−1}-.
У првом кораку (-{k}- = 0), остаци -{r}-−2 и-{r}-−1 су једнаки -{a}- и -{b}- респективно, а то су управо бројеви за које се тражи НЗД. У следећем кораку (-{k}- = 1), остаци постају једнаки -{b}- и остатку почетног корака -{r0}-... На основу тога, алгоритам се може представити низом једнакости
-{a = q0 b + r0}- -{b = q1 r0 + r1}- -{r0 = q2 r1 + r2}- -{r1 = q3 r2 + r3}- …
Уколико је -{a}- мање од -{b}-, у првом кораку алгоритма треба заменити бројеве, односно, за -{a < b}-, почетни количник q0 је једнак нули, а остатак -{r0}- је једнак -{a}-. На тај начин, -{rk}- је мањи од свог претходника -{rk−1}- за све -{k ≥ 0}-.
Како се остаци смањују у сваком кораку, и како не могу бити негативни, остатак -{rN}- у неком тренутку мора постати једнак нули, па се тада алгоритам зауставља. Последњи остатак -{rN−1}- који је различит од нуле је највећи заједнички делилац бројева -{a}- и -{b}-. Број -{N}- не може бити бесконачан пошто између нуле и првог остатка -{r0}- постоји коначан број ненегативних целих бројева.
Доказ валидности Валидност Еуклидовог алгоритма се може доказати у два корака. У првом кораку показује се да последњи остатак -{rN−1}- различит од нуле дели истовремено и -{a}- и -{b}-. Како је у питању заједнички делилац, он мора бити мањи или једнак највећем заједничком делиоцу -{g}-. У другом кораку се показује да произвољан заједнички делилац бројева -{a}- и -{b}-, укључујући и -{g}-, мора да дели и -{rN−1}-; одатле следи да -{g}- мора бити мање или једнако -{rN−1}-. Добијена два закључка су конзистентна само у случају да је -{rN−1 = g}-.
Да би се показао први корак, односно да -{rN−1}- дели истовремено и -{a}- и -{b}-, најпре треба приметити да -{rN−1}- дели свог претходника -{rN−2}-
-{rN−2 = qN rN−1}-
пошто је последњи остатак -{rN}- једнак нули. -{rN−1}- дели и -{rN−3}-
-{rN−3 = qN−1 rN−2 + rN−1}-
зато што истовремено дели оба сабирка са десне стране једнакости. Разматрајући редом остале претходнике, добија се да их -{rN−1}- дели све, укључујући -{a}- и -{b}-. Са друге стране, ниједан од преосталих остатака -{rN−2}-, -{rN−3}-, итд. не дели истовремено и -{a}- и -{b}-, пошто се у једнакостима увек јавља остатак. Како је -{rN−1}- заједнички делилац бројева -{a}- и -{b}-, мора бити -{rN−1 ≤ g}-.