Изворни код странице Еуклидов алгоритам

[[Датотека:Euclidean algorithm 252 105 animation flipped.gif|мини|100п|Анимација [[Еуклид]]овог [[Алгоритам|алгоритма]] за бројеве 252 и 105. Јединични сегменти су заправо дужине 21, што је [[највећи заједнички делилац]] датих бројева (НЗД). У сваком кораку, мањи број се одузима од већег, све док се један од њих не сведе на [[0 (број)|нулу]]. Остатак је НЗД полазних бројева.]]

У [[Математика|математици]], '''Еуклидов алгоритам'''{{ref_label|a|a|none}} је ефикасан начин за одређивање [[Највећи заједнички делилац|највећег заједничког делиоца]] (НЗД) датих бројева. [[Алгоритам]] носи име по [[Античка Грчка|старогрчком]] [[математичар]]у [[Еуклид]]у, који га је навео у -{VII}- и -{X}- књизи својих ''[[Еуклидови Елементи|Елемената]]''.<ref>Heath, ''-{A History Of Greek Mathematics, volume I}-''. стр. 399, 404</ref>

НЗД два броја је највећи број који истовремено дели оба без остатка. Еуклидов алгоритам је заснован на принципу да се највећи заједнички делилац два броја не мења уколико се мањи број одузме од већег, па се затим одреди НЗД новодобијеног броја и мањег од претходна два. На пример, 21 је НЗД за 252 и 105 (252&nbsp;=&nbsp;21&nbsp;×&nbsp;12; 105&nbsp;=&nbsp;21&nbsp;×&nbsp;5); пошто је 252&nbsp;−&nbsp;105&nbsp;=&nbsp;147, НЗД за 147 и 105 је такође 21. Како је већи од два полазна броја на овај начин смањен, понављањем поступка добијаће се све мањи бројеви, док се један од њих не сведе на нулу. У том тренутку, други број је једнак највећем заједничком делиоцу два полазна броја. Уколико се [[Проширени Еуклидов алгоритам|обрне редослед корака у Еуклидовом алгоритму]], НЗД се може изразити као [[Линеарна комбинација|збир]] два полазна броја од којих је сваки помножен неким [[Цео број|целим бројем]], у претходном примеру је {{nowrap begin}}21 = 5 × 105 + (−2) × 252.{{nowrap end}} Ова важна особина је позната као [[Безуов идентитет]].

Први познати сачувани опис Еуклидовог алгоритма се налази у ''[[Еуклидови Елементи|Елементима]]'' (око [[3. век п. н. е.|300. п. н. е.]]), што га чини најстаријим нумеричким алгоритмом који се још увек активно користи. У оригиналу, објашњен је само за [[Природан број|природне бројеве]] и геометријске дужине ([[реалан број|реалне бројеве]]), али је у [[19. век]]у уопштен на [[полином]]е једне променљиве и на [[Карл Фридрих Гаус|Гаусове]] [[Гаусови цели бројеви|целе бројеве]], што је довело до развоја нових појмова [[Апстрактна алгебра|апстрактне алгебре]] као што је [[Еуклидски домен]]. Еуклидов алгоритам је даље уопштаван на другим математичким структурама, попут [[чвор (математика)|чворова]] и полинома више променљивих.

Еуклидов алгоритам има широку теоријску и практичну примену. Представља кључан елемент [[RSA (алгоритам)|-{RSA}- алгоритма]], методе [[Асиметрична криптографија|асиметричне криптографије]] која се у значајној мери примењује у [[Електронско пословање|електронском пословању]]. Користи се при решавању [[Диофантске једначине|диофантских једначина]], на пример код одређивања бројева који задовољавају вишеструке конгруенције ([[Кинеска теорема о остацима]]) или при одређивању [[Мултипликативни инверз|мултипликативног инверза]] [[Коначно поље|коначног поља]]. Може се употребити за конструисање [[Верижни разломак|верижних разломака]], у [[Жак Шарл Франсоа Штурм|Штурмовој]] методи за одређивање реалних нула полинома, и још неколико савремених алгоритама за [[Факторизација природних бројева|факторизацију]] [[природан број|природних бројева]]. На крају, Еуклидов алгоритам је основно средство за доказивање [[теорема]] модерне [[Теорија бројева|теорије бројева]], као што су [[Лагранжова теорема о четири квадрата]] и [[основна теорема аритметике]] о јединственој факторизацији природних бројева.

Еуклидов алгоритам је ефикасан начин за одређивање НЗД великих бројева због тога што му не треба више корака од петоструког броја цифара мањег броја записаног са основом 10, што је доказао [[Габријел Ламе]] [[1844]]. године и тиме означио почетак [[Теорија комплексности|теорије комплексности]]. У [[20. век]]у су развијене методе за побољшање ефикасности Еуклидовог алгоритма.

== Историја ==
[[Датотека:Euclid.jpg|мини|150п|Еуклидов алгоритам је вероватно био познат вековима пре [[Еуклид]]овог рођења. Део [[Рафаело Санти|Рафаелове]] [[Фреска|фреске]] ''[[Атинска школа]]'' на коме је приказан Еуклид са ученицима.]]

Еуклидов алгоритам је један од најстаријих алгоритама који се још увек употребљава.<ref>-{Knuth, ''The Art of Computer Programming, Volume 2''}-. стр. 318.</ref> У писаном облику, први пут се појављује у [[Еуклидови Елементи|Еуклидовим ''Елементима'']] у [[3. век п. н. е.|3. веку п. н. е.]], и то у -{VII}- (тврђења 1<ref>Еуклид, ''Елементи'', [http://poincare.matf.bg.ac.rs/nastavno/zlucic/EUKLID07_T_1.HTML књига -{VII}-, тврђење -{I}-]</ref> и 2<ref>Еуклид, ''Елементи'', [http://poincare.matf.bg.ac.rs/nastavno/zlucic/EUKLID07_T_2.HTML књига -{VII}-, тврђење -{II}-]</ref>) и -{X}- књизи (тврђења 2<ref>Еуклид, ''Елементи'', [http://poincare.matf.bg.ac.rs/nastavno/zlucic/EUKLID10_T_2.HTML књига -{X}-, тврђење -{II}-]</ref> и 3<ref>Еуклид, ''Елементи'', [http://poincare.matf.bg.ac.rs/nastavno/zlucic/EUKLID10_T_2.HTML књига -{X}-, тврђење -{III}-]</ref>). У -{VII}- књизи, алгоритам је формулисан за целе бројеве, док је у -{X}- књизи дата примена на дужи, па је он геометријске природе.{{ref_label|b|b|none}} НЗД за дате дужи ''-{a}-'' и ''-{b}-'' одговара дужи ''-{g}-'' која је највећа могућа дуж којом се могу измерити ''-{a}-'' и ''-{b}-'' подједнако. Другим речима, дужи ''-{a}-'' и ''-{b}-'' се могу добити множењем дужи ''-{g}-'' неким целим бројем.

Врло је вероватно да [[Еуклид]] није оригинални творац алгоритма, јер је он у [[Еуклидови Елементи|''Елементима'']] сабрао до тада позната математичка знања.<ref name="Weil_1983">{{harvnb|Weil|1994|pp=46–48}}</ref> Математичар и историчар [[Бартел Лендерт ван дер Варден|ван дер Варден]] сматра да је седма књига ''Елемената'' заснована на уџбенику [[Теорија бројева|теорије бројева]] који су написали математичари из [[Питагорејци|питагорејске школе]].<ref name="van_der_Waerden_1954">{{Cite book| author = Bartel Leendert van der Waerden |year=1954|title=Science Awakening |series=translated by Arnold Dresden |publisher= P. Noordhoff Ltd|location = -{Groningen}-|pages=114–115}}</ref> Постоје индиције да је сам алгоритам био познат још [[Еудокс|Еудоксу са Книда]] (око 375. п. н. е.),<ref>-{Knuth, ''The Art of Computer Programming, Volume 2''}-, pp. 318.</ref><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=Ann. Math. |volume=46|doi=10.2307/1969021 |pages=242–264}}</ref> а могуће је и да је старији,{{sfn|Heath|1949|pp=80–83}}{{sfn|Fowler|1987|pp=31–66}} судећи по употреби техничког термина -{ἀνθυφαίρεσις (''anthyphairesis''}-, реципрочно одузимање) у делима Еуклида и Аристотела.<ref>{{cite journal|last=Becker|first=O|year=1933|title=Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid |journal=Quellen und Studien zur Geschichte der Mathematik B|volume=2|pages=311–333}}</ref>

Вековима касније, Еуклидов [[алгоритам]] је поново независно откривен у [[Индија|Индији]] и [[Кина|Кини]],<ref name="autogenerated1">Stillwell, ''-{Numbers and Geometry}-''. стр. 31.</ref> првенствено као средство за одређивање решења [[Диофантске једначине|диофантских једначина]] које су се појављивале при решавању [[Астрономија|астрономских]] проблема и прављењу прецизних [[календар]]а. У другој половини [[5. век|петог века]], индијски математичар и астроном [[Ариабхата]] описао је алгоритам као „дробилицу“,<ref name="autogenerated2">Tattersall, ''-{Elementary number theory in nine chapters}-''. стр. 70.</ref> можда због његове ефикасности у решавању диофантских једначина.<ref>Rosen, ''-{Elementary Number Theory and its Applications}-''. стр. 86–87</ref> Иако је посебан случај [[Кинеска теорема о остацима|Кинеске теореме о остацима]] навео већ кинески математичар и астроном [[Сун Тзу (математичар)|Сун Тзу]]<ref>Ore, ''-{Number Theory and Its History}-''. стр. 247–248</ref> у [[5. век|5. веку нове ере]], опште решење је [[1247]]. године објавио [[Цин Цзу-шао]] у својом делу ''Цзју чжан суан шу'' ({{јез-кин|數書九章}}, [[Девет књига о математичкој вештини]]).<ref>Tattersall, ''-{Elementary number theory in nine chapters}-''. стр. 72, 184–185.</ref>

У [[Европа|Европи]], Еуклидов алгоритам је први пут описао [[Клод Гаспар Баше де Мезирјак|Баше]] у другом издању свог дела ''-{Problèmes plaisants et délectables}-'' (''Пријатни проблеми за уживање'', [[1624]]),<ref name="autogenerated2" /> а претпоставља се да је коришћен у решавању диофантских једначина и при конструкцији [[Верижни разломак|верижних разломака]]. [[Проширени Еуклидов алгоритам]] је, као методу за ефикасно израчунавање верижних разломака, објавио енглески математичар [[Николас Саундерсон]], приписавши га [[Роџер Коутс|Роџеру Коутсу]].<ref>Tattersall, ''-{Elementary number theory in nine chapters}-''. стр. 72–76</ref>

У [[19. век]]у, захваљујући Еуклидовом алгоритму, дошло је до развоја нових бројевних система, као што су [[Гаусови цели бројеви|Гаусови]] и [[Ејзенштајнови цели бројеви]]. [[Карл Фридрих Гаус|Гаус]] је [[1815]]. године употребио Еуклидов алгоритам да покаже јединствену факторизацију [[Гаусови цели бројеви|својих целих бројева]], иако је тај рад објављен тек скоро две деценије касније, [[1832]]. године<ref name="Gauss_1832">{{cite journal|author=Карл Фридрих Гаус|authorlink=Карл Фридрих Гаус|year=1832|title=Theoria residuorum biquadraticorum|journal=Comm. Soc. Reg. Sci. Gött. Rec.|volume=4}}<br />Види још и ''-{Werke}-'', '''2''':67–148</ref>, а сам алгоритам је први пут споменут у његовој књизи ''Аритметичка истраживања'' ({{јез-лат|Disquisitiones Arithmeticae}}) објављеној [[1801]]. године, али само као метода за рад са [[верижни разломак|верижним разломцима]].<ref name="autogenerated1" />

Чини се да је [[Јохан Петер Густав Лежен Дирихле|Дирихле]] био први аутор који је сматрао Еуклидов алгоритам за један од основних елемената теорије бројева.<ref>Stillwell, ''-{Numbers and Geometry}-''. стр. 31–32</ref> Приметио је да би велики број резултата теорије бројева (на пример, јединствена факторизација), био тачан у било ком другом систему бројева у коме би се могао применити Еуклидов алгоритам.<ref>Dirichlet,''-{Vorlesungen über Zahlentheorie}-''. стр. 29–31</ref> Дирихлеова предавања о теорији бројева допунио је и прерадио [[Јулијус Вилхелм Рихард Дедекинд|Рихард Дедекинд]], који је користио Еуклидов алгоритам за изучавање новог општег типа бројева - [[Алгебарски цели бројеви|алгебарских целих бројева]]. Први је доказао [[Пјер де Ферма|Фермаову]] [[Фермаова теорема о збиру два квадрата|теорему о збиру два квадрата]] користећи јединствену факторизацију Гаусових целих бројева.<ref>{{Cite book|last=Дедекинд|first=Рихард|authorlink=Рихард Дедекинд|year=1894|chapter=Supplement XI|title= Vorlesungen über Zahlentheorie|url=https://archive.org/details/vorlesungenber00lejeuoft|editor=Peter Gustav Lejeune Dirichlet}}</ref> Поред тога, Дедекинд је дефинисао и концепт [[Еуклидов домен|Еуклидовог домена]], бројевног система у коме је могуће дефинисати уопштење Еуклидовог алгоритма. Крајем 19. века, Еуклидов алгоритам је постепено занемарен у корист Дедекиндове општије теорије [[Идеал (теорија прстена)|идеала]].<ref>Stillwell, ''-{Elements of Number Theory}-''. стр. 41-42</ref>

{| class="toccolours" style="float: left; margin-left: 1em; margin-right: 1em; font-size: 85%; background:#c6dbf7; color:black; width:23em; max-width: 25%;" cellspacing="5"
| style="text-align: left;" |
„Еуклидов алгоритам је дека свих алгоритама, пошто је то најстарији нетривијални алгоритам који је преживео до данас.“
|-
| style="text-align: left;" | [[Donald Knut|Доналд Кнут]], -{''The Art of Computer Programming, Vol. 2: Seminumerical Algorithms'', 2nd edition}-. {{page|year=1981|isbn=|pages=318}}.
|}

Процес изналажења примена Еуклидовог алгоритма започет у 19. веку, наставио се до данас. [[Жак Шарл Франсоа Штурм|Шарл Штурм]] је [[1829]]. године показао да се алгоритам може употребити у [[Штурмова теорема|Штурмовом ланцу]] који се користи за пребројавање реалних нула [[полином]]а у произвољно изабраном интервалу.<ref>{{cite journal|author=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>

Еуклидов алгоритам је био први алгоритам за утврђивање целобројне повезаности, односно за налажење целобројних односа између самерљивих реалних бројева. Крајем [[20. век]]а је развијено неколико нових алгоритама који могу да проверавају целобројну повезаност<ref>[http://www.sciencenews.org/view/generic/id/172/title/Math_Trek__Jazzing_Up_Euclids_Algorithm -{Jazzing Up Euclid's Algorithm}-]</ref><ref>[http://mathworld.wolfram.com/IntegerRelation.html Integer Relation]</ref>, на пример [[Фергусон-Форкејд алгоритам]],<ref>[http://mathworld.wolfram.com/Ferguson-ForcadeAlgorithm.html -{Ferguson-Forcade Algorithm}-]</ref> и њему сродни, ЛЛЛ алгоритам<ref>[http://mathworld.wolfram.com/LLLAlgorithm.html -{LLL Algorithm}-]</ref>, -{HJLS}- алгоритам<ref>[http://mathworld.wolfram.com/HJLSAlgorithm.html -{HJLS Algorithm}-]</ref>, и -{PSLQ}- алгоритам.<ref>[http://mathworld.wolfram.com/PSLQAlgorithm.html -{PSLQ Algorithm}-]</ref>

Године [[1969]]. под називом ''Еуклидова игра'' појавила се стратешка игра за два играча заснована на Еуклидовом алгоритму.<ref>{{cite journal|vauthors=Cole AJ, Davie AJ |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| doi=10.2307/3612461|pages=354–357}}</ref> На почетку, испред играча се налазе две гомиле са ''-{a}-'', односно ''-{b}-'' каменчића. Они наизменично узимају по ''-{m}-'' каменчића са веће гомиле, где је ''-{m}-'' неки умножак броја каменчића у мањој гомили. Конкретно, уколико се у неком тренутку на гомилама налази ''-{x}-'', односно ''-{y}-'' каменчића, где је ''-{x}-'' веће од ''-{y}-'', играч на потезу може смањити већу гомилу са ''-{x}-'' на ''-{x'' − ''ky}-'' каменчића, под условом да је број каменчића које одузима ненегативан [[цео број]]. Победник је први играч коме пође за руком да избаци све каменчиће из једне гомиле.<ref>Rosen, ''-{Elementary Number Theory and its Applications}-''. стр. 95.</ref><ref>{{Cite book|last=Roberts|first=J.|year=1977|title=Elementary Number Theory: A Problem Oriented Approach|publisher=MIT Press|location=-{Cambridge, MA}-|id=ISBN 0-262-68028-0 |pages=1–8}}</ref>

== Алгоритам ==
=== Принцип ===
Еуклидов алгоритам је итеративне природе, што значи да се крајњи резултат добија у низу корака, док се међурезултат произвољног корака користи у првом следећем.<ref>Stark, ''-{An Introduction to Number Theory}-''. стр. 16–20</ref> Уколико је ''-{k}-'' [[цео број]] којим су означени кораци [[Алгоритам|алгоритма]] почевши од [[0 (број)|нуле]], првом кораку одговара једнакост ''-{k}-''&nbsp;=&nbsp;0, другом ''-{k}-''&nbsp;=&nbsp;1, и тако даље.

Сваки корак почиње са два ненегативна остатка ''-{r''<sub>''k''−1</sub>}- и -{''r''<sub>''k''−2</sub>}-. Како алгоритам осигурава да се остаци сваким кораком непрекидно смањују, -{''r''<sub>''k''−1</sub>}- је мање од свог претходника -{''r''<sub>''k''−2</sub>}-. Циљ -{''k}-''-тог корака је да се одреде [[дељење|количник]] -{''q''<sub>''k''</sub>}- и [[остатак]] -{''r''<sub>''k''</sub>}- такви да важи једнакост

: -{''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>}-

где је -{''r''<sub>''k''</sub>&nbsp;<&nbsp;''r''<sub>''k''−1</sub>}-. Другим речима, умношци мањег броја -{''r''<sub>''k''−1</sub>}- се одузимају од већег броја -{''r''<sub>''k''−2</sub>}- све док је добијени остатак мањи од -{''r''<sub>''k''−1</sub>}-.

У првом кораку (''-{k}-''&nbsp;=&nbsp;0), остаци ''-{r}-''<sub>−2</sub> и''-{r}-''<sub>−1</sub> су једнаки ''-{a}-'' и ''-{b}-'' респективно, а то су управо бројеви за које се тражи НЗД. У следећем кораку (''-{k}-''&nbsp;=&nbsp;1), остаци постају једнаки ''-{b}-'' и остатку почетног корака -{''r''<sub>0</sub>}-... На основу тога, алгоритам се може представити низом једнакости

: -{''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>0</sub> = ''q''<sub>2</sub> ''r''<sub>1</sub> + ''r''<sub>2</sub>}-
: -{''r''<sub>1</sub> = ''q''<sub>3</sub> ''r''<sub>2</sub> + ''r''<sub>3</sub>}-
: …

Уколико је ''-{a}-'' мање од ''-{b}-'', у првом кораку алгоритма треба заменити бројеве, односно, за ''-{a''&nbsp;<&nbsp;''b}-'', почетни количник ''q''<sub>0</sub> је једнак нули, а остатак ''-{r''<sub>0</sub>}- је једнак -{''a}-''. На тај начин, -{''r''<sub>''k''</sub>}- је мањи од свог претходника -{''r''<sub>''k''−1</sub>}- за све -{''k''&nbsp;≥&nbsp;0}-.

Како се остаци смањују у сваком кораку, и како не могу бити негативни, остатак ''-{r''<sub>''N''</sub>}- у неком тренутку мора постати једнак нули, па се тада алгоритам зауставља.<ref name="Stark_p18">Stark, -{''An Introduction to Number Theory}-''. стр. 18.</ref> Последњи остатак ''-{r''<sub>''N''−1</sub>}- који је различит од нуле је [[највећи заједнички делилац]] бројева -{''a}-'' и ''-{b}-''. Број ''-{N}-'' не може бити [[Бесконачност|бесконачан]] пошто између нуле и првог остатка -{''r''<sub>0</sub>}- постоји коначан број ненегативних [[Цео број|целих бројева]].

=== Доказ валидности ===
Валидност Еуклидовог алгоритма се може доказати у два корака.<ref>Stark, ''-{An Introduction to Number Theory}-''. стр. 16–20.</ref> У првом кораку показује се да последњи остатак ''-{r''<sub>''N''−1</sub>}- различит од нуле дели истовремено и -{''a}-'' и ''-{b}-''. Како је у питању заједнички делилац, он мора бити мањи или једнак највећем заједничком делиоцу ''-{g}-''. У другом кораку се показује да произвољан заједнички делилац бројева ''-{a}-'' и ''-{b}-'', укључујући и ''-{g}-'', мора да дели и ''-{r''<sub>''N''−1</sub>}-; одатле следи да -{''g}-'' мора бити мање или једнако ''-{r''<sub>''N''−1</sub>}-. Добијена два закључка су конзистентна само у случају да је -{''r''<sub>''N''−1</sub>&nbsp;=&nbsp;''g}-''.

Да би се показао први корак, односно да ''-{r''<sub>''N''−1</sub>}- дели истовремено и -{''a}-'' и ''-{b}-'', најпре треба приметити да -{''r''<sub>''N''−1</sub>}- дели свог претходника -{''r''<sub>''N''−2</sub>}-

: -{''r''<sub>''N''−2</sub> = ''q''<sub>''N''</sub> ''r''<sub>''N''−1</sub>}-

пошто је последњи остатак -{''r''<sub>''N''</sub>}- једнак нули. -{''r''<sub>''N''−1</sub>}- дели и -{''r''<sub>''N''−3</sub>}-

:-{''r''<sub>''N''−3</sub> = ''q''<sub>''N''−1</sub> ''r''<sub>''N''−2</sub> + ''r''<sub>''N''−1</sub>}-

зато што истовремено дели оба сабирка са десне стране једнакости. Разматрајући редом остале претходнике, добија се да их ''-{r''<sub>''N''−1</sub>}- дели све, укључујући -{''a}-'' и ''-{b}-''. Са друге стране, ниједан од преосталих остатака ''-{r''<sub>''N''−2</sub>}-, -{''r''<sub>''N''−3</sub>}-, итд. не дели истовремено и -{''a}-'' и ''-{b}-'', пошто се у једнакостима увек јавља остатак. Како је ''-{r''<sub>''N''−1</sub>}- заједнички делилац бројева -{''a}-'' и ''-{b}-'', мора бити ''-{r''<sub>''N''−1</sub>&nbsp;≤&nbsp;''g}-''.

У другом кораку треба добити да произвољан [[природан број]] ''-{c}-'' који истовремено дели и ''-{a}-'' и ''-{b}-'' (произвољан заједнички делилац бројева ''-{a}-'' и ''-{b}-'') мора да дели и остатак ''-{r''<sub>''k''</sub>}-. По дефиницији, -{''a}-'' и ''-{b}-'' могу бити записани као умношци броја ''-{c}-'': ''-{a''&nbsp;=&nbsp;''mc}-'' и ''-{b''&nbsp;=&nbsp;''nc}-'', при чему су ''-{m}-'' и ''-{n}-'' природни бројеви. Одатле следи да ''-{c}-'' дели први остатак -{''r''<sub>0</sub>}-, јер важи следећи низ једнакости:

:''-{r''<sub>0</sub>&nbsp;=&nbsp;''a''&nbsp;−&nbsp;''q''<sub>0</sub>''b''&nbsp;=&nbsp;''mc''&nbsp;−&nbsp;''q''<sub>0</sub>''nc''&nbsp;=&nbsp;(''m''&nbsp;−&nbsp;''q''<sub>0</sub>''n'')''c}-''.

Аналогно се може добити да ''-{c}-'' дели и остатке ''-{r''<sub>1</sub>}-, -{''r''<sub>2</sub>}-, итд. Закључак је да [[Највећи заједнички делилац|НЗД]] ''g'' мора да дели -{''r''<sub>''N''−1</sub>}-, одакле је -{''g''&nbsp;≤&nbsp;''r''<sub>''N''−1</sub>}-. Како је према првом кораку -{''r''<sub>''N''−1</sub>&nbsp;≤&nbsp;''g}-'', мора бити ''-{g''&nbsp;=&nbsp;''r''<sub>''N''−1</sub>}-. Зато је -{''g}-'' [[највећи заједнички делилац]] свих следећих парова:<ref>Knuth, ''-{The Art of Computer Programming, Volume 2}-''. стр. 320.</ref><ref name="Lovasz_2003">{{harvnb|Lovasz|2003|pp=100–101}}</ref>

:''-{g}-'' = НЗД-{(''a'', ''b'')}- = НЗД-{(''b'', ''r''<sub>0</sub>)}- = НЗД-{(''r''<sub>0</sub>, ''r''<sub>1</sub>)}- = … = НЗД-{(''r''<sub>''N''−2</sub>, ''r''<sub>''N''−1</sub>)}- = -{''r''<sub>''N''−1</sub>}-

=== Пример употребе алгоритма ===
[[Датотека:Euclidean algorithm 1071 462.gif|десно|мини|Анимација [[Алгоритам|алгоритма]] у којој се све мањим [[квадрат]]има почетни [[правоугаоник]] покрива у потпуности. Димензије [[Зелена боја|зеленог]] правоугаоника су ''-{a}-''&nbsp;=&nbsp;1071 и ''-{b}-''&nbsp;=&nbsp;462. Он се покрива [[Наранџаста боја|наранџастим]] квадратима странице 462 све док је то могуће, после чега остане зелени правоугаоник димензија 462×147. Он се затим покрива [[Плава боја|плавим]] квадратима дужине страница 147, и као вишак остаје зелени правоугаоник димензија 21×147. Њега је могуће без остатка покрити [[Црвена боја|црвеним]] квадратима чија је страница дужине 21. То значи да је 21 [[Највећи заједнички делилац|НЗД]] бројева 1071 и 462.]]

Као илустрација, Еуклидовим алгоритмом се може одредити највећи заједнички делилац бројева ''-{a}-''&nbsp;=&nbsp;1071 и ''-{b}-''&nbsp;=&nbsp;462. Најпре се од броја 1071 одузима број 462 све док се не добије остатак који је мањи од 462. Тај поступак се може поновити [[2 (број)|два]] пута (''-{q}-''<sub>0</sub>&nbsp;=&nbsp;2), уз остатак 147:

: 1071 = 2 × 462 + 147.

Затим се понавља поступак за бројеве 462 и 147 све док нови остатак не постане мањи од 147, што ће се десити после [[3 (број)|трећег]] одузимања (''-{q}-''<sub>1</sub>&nbsp;=&nbsp;3), а добијени остатак ће бити 21:

: 462 = 3 × 147 + 21.

У трећем кораку, 21 се одузима од 147 све док нови остатак не постане мањи од 21. Поступак се може поновити [[7 (број)|седам]] пута (''-{q}-''<sub>2</sub>&nbsp;=&nbsp;7) без остатка.

: 147 = 7 × 21 + 0.

Како је последњи остатак [[0 (број)|нула]], алгоритам се завршава, при чему је 21 највећи заједнички делилац бројева 1071 и 462. Добијени резултат се поклапа са НЗД(1071, 462) одређеним помоћу факторизације на просте бројеве. Описани поступак се може приказати и таблично:

{| class="wikitable" id="basic_Euclidean_algorithm" style="margin-left:auto; margin-right:auto; text-align:center"
!Корак ''-{k}-''!!Једнакост!!Количник и остатак
|-
| 0 || 1071 = ''-{q}-''<sub>0</sub>×462 + ''-{r}-''<sub>0</sub> || ''-{q}-''<sub>0</sub> = 2 и ''-{r}-''<sub>0</sub> = 147
|-
| 1 || 462 = ''-{q}-''<sub>1</sub>×147 + ''-{r}-''<sub>1</sub> || ''-{q}-''<sub>1</sub> = 3 и ''-{r}-''<sub>1</sub> = 21
|-
| 2 || 147 = ''-{q}-''<sub>2</sub>×21 + ''-{r}-''<sub>2</sub> || ''-{q}-''<sub>2</sub> = 7 и ''-{r}-''<sub>2</sub> = 0; алгоритам се завршава
|}

=== Визуелизација ===
Еуклидов алгоритам се може и визуелно приказати коришћењем аналогије са прекривањем [[правоугаоник]]а [[квадрат]]има.<ref name="Kimberling_1983">{{cite journal|last=Kimberling|first=C|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> Претпоставка је да је потребно у потпуности прекрити правоугаоник димензија „''-{a}-'' пута ''-{b}-''“ квадратима, при чему је ''-{a}-'' дужа страница. Најпре се покушава прекривање квадратима странице ''-{b}-''; овај поступак даје непокривен правоугаони вишак димензија „''-{r}-''<sub>0</sub> пута ''-{b}-''“, при чему је ''-{r}-''<sub>0</sub><''-{b}-''. Затим се коришћењем квадрата странице ''-{r}-''<sub>0</sub> прекрива вишак. У том поступку се добија нови непокривени правоугаоник димензија „''-{r}-''<sub>1</sub> пута ''-{r}-''<sub>0</sub>“. За његово прекривање се користе квадрати странице ''-{r}-''<sub>1</sub>, итд. Поступак се завршава у тренутку када више нема непокривеног вишка, односно када квадрати покрију правоугаоник у потпуности. Дужина стране најмањег квадрата је НЗД за бројеве који чине странице полазног правоугаоника. На пример, најмањи квадрат на суседној слици је странице 21 (приказан [[Црвена боја|црвеном бојом]]), а 21 је [[Највећи заједнички делилац|НЗД]] бројева 1071 и 462, што су димензије полазног правоугаоника (приказаног [[Зелена боја|зеленом бојом]]).

=== Одређивање количника и остатка ===
{{Види још|Целобројно дељење|Алгоритам дељења}}

У сваком кораку ''-{k}-'', Еуклидов алгоритам израчунава количник -{''q''<sub>''k''</sub>}- и остатак -{''r''<sub>''k''</sub>}- помоћу два дата броја -{''r''<sub>''k''−1</sub>}- и -{''r''<sub>''k''−2</sub>}-

: -{''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>}-

при чему је ''-{r''<sub>''k''</sub>}- по [[апсолутна вредност|апсолутној вредности]] строго мањи од -{''r''<sub>''k''−1</sub>}-. [[Алгоритам дељења]] обезбеђује да такав количник и остатак увек постоје. Поред тога, [[Дељивост|алгоритам дељења]] за [[природан број|природне бројеве]] тврди да су -{''q''<sub>''k''</sub>}- и -{''r''<sub>''k''</sub>}- јединствени, али тај услов није потребан Еуклидовом алгоритму.<ref name="Cohn_1962">Cohn, -{''Advanced Number Theory}-''. стр. 104–110</ref>

У [[Еуклид]]овој оригиналној верзији [[Алгоритам|алгоритма]] количник и остатак се одређују понављањем одузимања: -{''r''<sub>''k''−1</sub>}- се одузима од -{''r''<sub>''k''−2</sub>}-све док остатак -{''r''<sub>''k''</sub>}- не постане мањи од -{''r''<sub>''k''−1</sub>}-. Ефикаснији приступ користи [[целобројно дељење]] (тзв. -{div}- операцију) да би израчунао количник и одређивање остатка при целобројном дељењу (тзв. -{mod}- операцију) да би израчунао остатак. Резултат -{mod}- операције је остатак при дељењу два броја; зато је,

:-{''r''<sub>''k''</sub>}- [[Модуларна аритметика|≡]] -{''r''<sub>''k''−2</sub> mod ''r''<sub>''k''−1</sub>}-

Остатак је еквивалентан класи конгруенције у [[Модуларна аритметика|модуларној аритметици]].

=== Имплементације ===
Имплементације алгоритма могу бити приказане [[псеудокод]]ом. На пример, верзија заснована на дељењу може бити [[програмирање|испрограмирана]] на следећи начин<ref>Knuth, ''-{The Art of Computer Programming, Volume 2}-''. стр. 319–320</ref>

 -{'''function''' nzd(a, b)
     '''while''' b ≠ 0
        t := b
        b := a '''mod''' b
        a := t
     '''return''' a}-

На почетку ''-{k}-''-те [[Итерација|итерације]], у променљивој ''-{b}-'' се налази последњи остатак ''-{r''<sub>''k''−1</sub>}-, док се у променљивој -{''a}-'' налази његов претходник, ''-{r''<sub>''k''−2</sub>}-. Ред кода у коме је -{''b'' := ''a'' mod ''b}-'' одговара [[Рекурзија|рекурзивној]] [[Формула|формули]] ''-{r''<sub>''k''</sub> ≡ ''r''<sub>''k''−2</sub> mod ''r''<sub>''k''−1</sub>}-. [[Помоћна променљива]] -{''t}-'' чува вредност ''-{r''<sub>''k''−1</sub>}- у тренутку у коме се израчунава следећи остатак -{''r''<sub>''k''</sub>}-. У последњем кораку итеративне петље, променљива -{''b}-'' чува остатак ''-{r''<sub>''k''</sub>}-, а променљива -{''a}-'' његовог претходника, остатак -{''r''<sub>''k''−1</sub>}-.

У [[Еуклид]]овој верзији која је заснована на [[Одузимање|одузимању]], израчунавање остатка (''-{b''&nbsp;=&nbsp;''a'' mod ''b}-'') је замењено одузимањем које се понавља.<ref>Knuth, ''-{The Art of Computer Programming, Volume 2}-''. стр. 318–319</ref>

 -{'''function''' nzd(a, b)
     '''if''' a = 0
        '''return''' b
     '''while''' b ≠ 0
         '''if''' a > b
            a := a − b
         '''else'''
            b := b − a
     '''return''' a}-

Променљиве ''-{a}-'' и ''-{b}-'' се смењују у чувању претходних остатака ''-{r''<sub>''k''−1</sub>}- и -{''r''<sub>''k''−2</sub>}-. Уколико је на почетку итерације -{''a}-'' веће од ''-{b}-'', онда ''-{a}-'' добија вредност ''-{r''<sub>''k''−2</sub>}-, пошто је -{''r''<sub>''k''−2</sub> > ''r''<sub>''k''−1</sub>}-. У току извршавања петље -{''a}-'' се смањује одузимањем претходног остатка ''-{b}-'' све док ''-{a}-'' не постане мање од ''-{b}-''. Тада је ''-{a}-'' следећи остатак ''-{r''<sub>''k''</sub>}-. Затим се -{''b}-'' смањује одузимањем ''-{a}-'' док не постане мање од њега, и тада постаје једнако ''-{r''<sub>''k''+1</sub>}-. Процес се наставља док -{''b}-'' не постане једнако [[0 (број)|нули]].

Рекурзивна верзија<ref>Stillwell, ''-{Numbers and Geometry}-''. стр. 14.</ref> је заснована на једнакости [[Највећи заједнички делилац|највећег заједничког делиоца]] сукцесивних остатака и резултата услова на основу кога се излази из петље НЗД(-{''r''<sub>''N''−1</sub>}-,&nbsp;0)&nbsp;=&nbsp;-{''r''<sub>''N''−1</sub>}-.

 -{'''function''' nzd(a, b)
     '''if''' b = 0
        '''return''' a
     '''else'''
        '''return''' nzd(b, a '''mod''' b)}-

На пример, НЗД(1071,&nbsp;462) се добија помоћу њему еквивалентног НЗД(462,&nbsp;1071&nbsp;-{mod}-&nbsp;462)&nbsp;=&nbsp;НЗД(462,&nbsp;147). Тај НЗД се одређује помоћу НЗД(147,&nbsp;462&nbsp;-{mod}-&nbsp;147)&nbsp;=&nbsp;НЗД(147,&nbsp;21), који се израчунава преко НЗД(21,&nbsp;147&nbsp;-{mod}-&nbsp;21)&nbsp;=&nbsp;НЗД(21,&nbsp;0)&nbsp;=&nbsp;21.

=== Метода најмањих апсолутних остатака ===
Постоји верзија Еуклидовог алгоритма у којој се количник у сваком кораку увећава за један уколико је резултујући негативни остатак по својој апсолутној вредности мањи од типичног позитивног остатка.<ref name="Ore_least_abs_remainders" >Ore, ''-{Number Theory and Its History}-''. стр. 43.</ref><ref name="Stewart_1964">{{harvnb|Stewart|1964|pp=43–44}}</ref> У претходним случајевима, једнакост

: -{''r''<sub>''k''−2</sub> = ''q''<sub>''k''</sub> ''r''<sub>''k''−1</sub> + ''r''<sub>''k''</sub>}-

је претпостављала да важи -{''r''<sub>''k''−1</sub>&nbsp;>&nbsp;''r''<sub>''k''</sub>&nbsp;>&nbsp;0}-. Међутим, могуће је искористити алтернативни негативни остатак -{''e''<sub>''k''</sub>}-:

: -{''r''<sub>''k''−2</sub> = (''q''<sub>''k''</sub> + 1) ''r''<sub>''k''−1</sub> + ''e''<sub>''k''</sub>}-

при чему је ''-{r''<sub>''k''−1</sub>}- по претпоставци, позитиван број. Ако је |-{''e''<sub>''k''</sub>}-|&nbsp;<&nbsp;|-{''r''<sub>''k''</sub>}-|, онда се -{''r''<sub>''k}-''</sub> замењује са -{''e''<sub>''k''</sub>}-. [[Леополд Кронекер]] је доказао да се овом методом НЗД одређује у најмањем броју корака у односу на све друге верзије Еуклидовог алгоритма.<ref name="Ore_least_abs_remainders" /><ref name="Stewart_1964" />

== Други бројевни системи ==
Као што је већ објашњено, Еуклидов алгоритам се користи за одређивање НЗД два [[природан број|природна броја]]. Међутим, могуће је уопштити га на [[реалан број|реалне бројеве]], и на егзотичне бројевне системе као што су [[полином]]и, [[квадратни цели бројеви]] и [[Хурвицови кватерниони]], те га искористити за показивање основне особине јединствене факторизације, односно чињенице да се такви бројеви моју раставити на јединствен начин на [[Несводљиви елемент|несводљиве елементе]] који су еквиваленти [[Прост број|простих бројева]]. Јединствена факторизација је кључни услов многих [[доказ]]а [[Теорија бројева|теорије бројева]].

=== Пример ===
НЗД два полинома <math>P(x)=x^5+x^4-x^3-3x^2-3x-1\,</math> и <math>Q(x)=x^4-2x^3-x^2-2x+1\,</math> налазимо на следећи начин користећи Еуклидов алгоритам (уз скраћивање и проширење):
:'''1.''' <math> \frac{x^5+x^4-x^3-3x^2-3x-1}{x^4-2x^3-x^2-2x+1} = x+3, R(1) = 6x^3+2x^2+2x-4 ; (\frac{P(x)}{Q(x)} = S(1)+R(1) )</math>
::'''1a.''' <math> \frac{6x^3+2x^2+2x-4}{2} = 3x^3+x^2+x-2 ; (\frac{R(1)}{2} = R(1s)) </math>
:'''2.''' <math> \frac{3x^4-6x^3-3x^2-6x+3}{3x^3+x^2+x-2} = x-\frac{7}{3}, R(2) = -\frac{5}{3}x^2-\frac{5}{3}x-\frac{5}{3} ; (\frac{3Q(x)}{R(1s)} = S(2)+R(2)) </math>
::'''2a.''' <math> \frac{-\frac{5}{3}x^2-\frac{5}{3}x-\frac{5}{3}}{-\frac{5}{3}} = x^2+x+1 ; (\frac{R(2)}{-\frac{5}{3}} = R(2s)) </math>
:'''3.''' <math> \frac{3x^3+x^2+x-2}{x^2+x+1} = 3x-2, R(3) = 0 ; (\frac{R(1s)}{R(2s)} = S(3)) </math>
:<math> NZD (P(x), Q(x)) = R(2s) = x^2+x+1 \,</math>

== Примене у математици ==
=== Безуов идентитет ===
Према [[Етјен Безу|Безуовом]] [[Безуов идентитет|идентитету]] [[највећи заједнички делилац]], у ознаци ''-{g}-'', два [[цео број|цела броја]] ''-{a}-'' и ''-{b}-'' може бити приказан као њихова линеарна комбинација.<ref>{{Cite book|last=Jones|first=G. A.  |last2=Jones|first2=J. M.  |lastauthoramp=yes |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> То значи да је увек могуће одредити целе бројеве ''-{s}-'' и ''-{t}-'' да важи једнакост ''-{g}-''&nbsp;=&nbsp;''-{sa}-''&nbsp;+&nbsp;''-{tb}-''.<ref>Rosen, ''-{Elementary Number Theory and its Applications}-''. стр. 81.</ref><ref>Cohn, ''-{Advanced Number Theory}-''. стр. 104.</ref>

Назначени бројеви ''-{s}-'' и ''-{t}-'' се могу израчунати помоћу количника ''-{q}-''<sub>0</sub>, ''-{q}-''<sub>1</sub>, итд. променом редоследа једначина у [[Еуклид]]овом [[Алгоритам|алгоритму]].<ref>Rosen, ''-{Elementary Number Theory and its Applications}-''. стр. 91.</ref> Почевши са претпоследњом једначином, ''-{g}-'' се може изразити помоћу количника ''-{q}-''<sub>''-{N}-''−1</sub> и два претходна остатка, ''-{r}-''<sub>''-{N}-''−2</sub> и ''-{r}-''<sub>''-{N}-''−3</sub>.

: ''-{g}-'' = ''-{r}-''<sub>''-{N}-''−1</sub> = ''-{r}-''<sub>''-{N}-''−3</sub> − ''-{q}-''<sub>''-{N}-''−1</sub> ''-{r}-''<sub>''-{N}-''−2</sub>

Наведени остаци могу, аналогно, бити приказани помоћу одговарајућих количника и остатака,

: ''-{r}-''<sub>''N''−2</sub> = ''-{r}-''<sub>''-{N}-''−4</sub> − ''-{q}-''<sub>''-{N}-''−2</sub> ''-{r}-''<sub>''-{N}-''−3</sub>
: ''-{r}-''<sub>''-{N}-''−3</sub> = ''-{r}-''<sub>''-{N}-''−5</sub> − ''-{q}-''<sub>''-{N}-''−3</sub> ''-{r}-''<sub>''-{N}-''−4</sub>

Заменом ''-{r}-''<sub>''-{N}-''−2</sub> и ''-{r}-''<sub>''-{N}-''−3</sub> са претходним једнакостима у првој једначини добиће се ''-{g}-'' као линеарна сума остатака ''-{r}-''<sub>''-{N}-''−4</sub> и ''-{r}-''<sub>''-{N}-''−5</sub>. Овај процес изражавања остатака формулама које укључују претходнике може се наставити док се не достигну полазни бројеви ''-{a}-'' и ''-{b}-'':

: ''-{r}-''<sub>2</sub> = ''-{r}-''<sub>0</sub> − ''-{q}-''<sub>2</sub> ''-{r}-''<sub>1</sub>
: ''-{r}-''<sub>1</sub> = ''-{b}-'' − ''-{q}-''<sub>1</sub> ''-{r}-''<sub>0</sub>
: ''-{r}-''<sub>0</sub> = ''-{a}-'' − ''-{q}-''<sub>0</sub> ''-{b}-''

Након што су сви остаци ''-{r}-''<sub>0</sub>, ..., ''r''<sub>''-{N}-''</sub> замењени, добијена једнакост приказује ''-{g}-'' као линеарну комбинацију бројева ''-{a}-'' и ''-{b}-'': ''-{g}-''&nbsp;=&nbsp;''-{sa}-''&nbsp;+&nbsp;''-{tb}-''. Самим тим, [[Безуов идентитет]], и претходни поступак могу бити генерализовани на контекст [[Еуклидски домен|еуклидских домена]].

=== Верижни разломци ===
Еуклидов алгоритам је у блиској вези са [[Верижни разломак|верижним разломцима]].<ref name="Vinogradov_1954">{{harvnb|Vinogradov|1954|pp=3–13}}</ref> Низ једнакости је могуће записати у облику:

:''-{a/b}-'' = ''-{q}-''<sub>0</sub> + ''-{r}-''<sub>0</sub>/''-{b}-''
:''-{b''/''r}-''<sub>0</sub> = ''-{q}-''<sub>1</sub> + ''-{r}-''<sub>1</sub>/''-{r}-''<sub>0</sub>
:''-{r}-''<sub>0</sub>/''-{r}-''<sub>1</sub> = ''-{q}-''<sub>2</sub> + ''-{r}-''<sub>2</sub>/''-{r}-''<sub>1</sub>
:…
:-{''r''<sub>''k''−2</sub>}-/-{''r''<sub>''k''−1</sub>}- = -{''q''<sub>''k''</sub>}- + -{''r''<sub>''k''</sub>}-/-{''r''<sub>''k''−1</sub>}-
:…
:-{''r''<sub>''N''−2</sub>}-/-{''r''<sub>''N''−1</sub>}- = -{''q''<sub>''N''</sub>}-

Последњи члан на десној страни сваке једнакости увек је једнак реципрочној вредности елемента са леве стране следеће једнакости. Из прве две једнакости се добија:

: ''-{a/b}-'' = ''-{q}-''<sub>0</sub> + 1/(''-{q}-''<sub>1</sub> + ''-{r}-''<sub>1</sub>/''-{r}-''<sub>0</sub>)

Ако се, затим, помоћу треће једнакости замени разломак ''-{r}-''<sub>1</sub>/''-{r}-''<sub>0</sub>, добија се:

: ''-{a/b}-'' = ''-{q}-''<sub>0</sub> + 1/(''-{q}-''<sub>1</sub> + 1/(''-{q}-''<sub>2</sub> + ''-{r}-''<sub>2</sub>/''-{r}-''<sub>1</sub>))

У сваком кораку, крајњи сабирак у облику разломка -{''r''<sub>''k''</sub>}-/-{''r''<sub>''k''−1</sub>}- се увек може заменити употребом следеће једнакости у низу, закључно са последњом. Резултат је верижни разломак

:''-{a/b}-'' = ''-{q}-''<sub>0</sub> + 1/(''-{q}-''<sub>1</sub> + 1/(''-{q}-''<sub>2</sub> + 1/(… + 1/''-{q''<sub>N</sub>}-))…) = [-{''q}-''<sub>0</sub>; ''-{q}-''<sub>1</sub>, ''-{q}-''<sub>2</sub>, …, -{''q''<sub>''N''</sub>}-]

Како је већ одређен НЗД(1071, 462), и како су израчунати количници -{''q''<sub>''k''</sub>}- били редом 2, 3 и 7, разломак 1071/462 се може записати

: 1071/462 = 2 + 1/(3 + 1/7) = [2; 3, 7]

што се може проверити рачунањем.

== Напомене ==
* '''a.''' {{Note_label|a|a|none}} У неким широко прихваћеним уџбеницима енглеског говорног подручја, као што је Херстајнов ({{јез-енгл|Israel Nathan Herstein}}) ''-{Topics in Algebra}-'', или Лангова ({{јез-енгл|Serge Lang}}) ''-{Algebra}-'', термин „Еуклидов алгоритам“ се користи да означи [[алгоритам дељења]]. Међутим, то је [[теорема]], а не [[алгоритам]].
* '''b.''' {{Note_label|b|b|none}} У савременој употреби, рекло би се да је формулисан за [[реалан број|реалне бројеве]]. Али, како се дужине, површине и запремине, иако се данас представљају реалним бројевима, не изражавају истим мерним јединицама, нити постоји природна јединица за дужину, површину и запремину, у то време није постојала идеја реалних бројева.

== Референце ==
{{reflist|30em}}

== Литература ==
{{Литература|2}}
* {{Cite book| ref=harv| author = Bartel Leendert van der Waerden |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}}
* {{Cite book| ref=harv|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=978-0-415-09238-8|pages=46–48}}
* {{Cite book| ref=harv| author = Bartel Leendert van der Waerden |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}}
* {{Cite book| ref=harv|last=Fowler|first=David|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=978-0-19-853912-4|pages=[https://archive.org/details/mathematicsofpla0000fowl_h9l3/page/31 31]–66}}
* {{Cite book| ref=harv|last=Heath|first=Sir Thomas|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}}
* {{Cite book| ref=harv|last=Дедекинд|first=Рихард|authorlink=Рихард Дедекинд|year=1894|chapter=Supplement XI|title= Vorlesungen über Zahlentheorie| url=https://archive.org/details/vorlesungenber00lejeuoft|editor=Peter Gustav Lejeune Dirichlet}}
* {{Cite book| ref=harv|last=Lovasz|first=Laszlo | last2 = Pelikan | first2 = Jozsef | last3 = Vesztergombi| first3 = Katalin L.|year=2003|title= Discrete Mathematics: Elementary and Beyond|publisher=Springer-Verlag|location=New York|isbn=978-0-387-95584-1|pages=100–101}}
* {{Cite book| ref=harv|last=Jones|first=G. A.  |last2=Jones|first2=J. M.  |lastauthoramp=yes |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}}
* {{Cite book| ref=harv|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|id=ISBN 0-262-68028-0 |pages=[https://archive.org/details/Elementary_00_Robe/page/1 1]–8}}
* {{Cite book| ref=harv|last=Stewart|first=B.M.|year=1964|title=Theory of Numbers| url=https://archive.org/details/theorynumbers00stew|edition=2nd|publisher=Macmillan|location=New York|id=|pages=[https://archive.org/details/theorynumbers00stew/page/n53 43]–44}}
* {{Cite book| ref=harv|last=Vinogradov|first=Ivan Matveyevich|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}}
* {{Cite book| ref=harv|last=Дирихле|first=Јохан Петер Густав Лежен|authorlink=Јохан Петер Густав Лежен Дирихле|year=1894|title=Vorlesungen über Zahlentheorie| url=https://archive.org/details/vorlesungenber00lejeuoft|editor=[[Јулијус Вилхелм Рихард Дедекинд|Richard Dedekind]]|publisher=Vieweg| location=Braunschweig}}
* {{Cite book| ref=harv|last=Cohn|first=Harvey|year=1962|title=Advanced Number Theory |url=https://books.google.com/books?id=yMGeElJ8M0wC |publisher=Dover|location= New York|isbn=978-0-486-64023-5|pages=}}
* {{Cite book| ref=harv|last=Heath|first=Sir Thomas|title=A History of Greek Mathematics, vol. I|year=1921|publisher=At the Clarendon Press|location= Oxford |id=}}
* {{Cite book| ref=harv|last=Ore|first=Øystein|title=Number Theory and Its History| url=https://archive.org/details/numbertheoryitsh00ore|year=1948|publisher=McGraw–Hill|location=New York}}
* {{Cite book| ref=harv|last=Stark|first=Harold|year=1978|title=An Introduction to Number Theory| url=https://archive.org/details/introductiontonu00star_0|publisher=MIT Press|isbn=978-0-262-69060-7|pages=}}
* {{Cite book| ref=harv|last=Кнут|first=Доналд|authorlink=Доналд Кнут|year=1997|title=The Art of Computer Programming, Volume 2: Seminumerical Algorithms|edition=3rd|publisher=Addison–Wesley|isbn=978-0-201-89684-8|pages=}}
* {{Cite book| ref=harv|last=Rosen|first=Kenneth H. |title=Elementary Number Theory and its Applications|year=2000|edition= 4th|publisher=Addison–Wesley|location=Reading, MA|isbn=978-0-201-87073-2|pages=}}
* {{Cite book| ref=harv|last=Stillwell|first=John|year=1997|title=Numbers and Geometry|publisher= Springer-Verlag|location=New York|isbn=978-0-387-98289-2|pages=}}
* {{Cite book| ref=harv|last=Stillwell|first=John|year=2003|title=Elements of Number Theory |publisher=Springer-Verlag|location=New York|isbn=978-0-387-95587-2|pages=}}
* {{Cite book| ref=harv|last=Tattersall|first=James J. |title=Elementary number theory in nine chapters| url=https://archive.org/details/elementarynumber0000jame|year=2005| publisher=Cambridge University Press|location=Cambridge|isbn=978-0-521-85014-8|pages=}}
* {{Cite book| ref=harv|last=Weil|first=André|year=1983|title = Number Theory|publisher = Birkhäuser|location = Boston|isbn=978-0-8176-3141-3|pages=4–6}}

{{Литература крај}}
== Спољашње везе ==
{{Commonscat|Euclidean algorithm}}
* [http://www.math.sc.edu/~sumner/numbertheory/euclidean/euclidean.html Интерактивна демонстрација Еуклидовог алгоритма] {{en}}
* [http://mathworld.wolfram.com/EuclideanAlgorithm.html Еуклидов алгоритам] {{en}}
* [http://www.cut-the-knot.org/blue/Euclid.shtml Еуклидов алгоритам] и [http://www.cut-the-knot.org/blue/EuclidAlg.shtml игра базирана на њему] {{en}}
* [http://plus.maths.org/issue40/features/wardhaugh/index.html -{Music and Euclid's algorithm}-] {{en}}

{{нормативна контрола}}

[[Категорија:Алгебра]]