Преглед на кодот на Евклидов алгоритам

[[Податотека:Euclidean_algorithm_252_105_animation_flipped.gif|мини|325x325пкс| Анимација на [[Евклид]]овиот [[алгоритам]] за броевите 252 и 105. Единичните сегменти се всушност со должина 21, што е најголемиот заеднички делител (НЗД) на дадените броеви. Во секој чекор, помалиот број се одзема од поголемиот, додека еден од нив не се сведе на [[0 (број)|нула]]. Останатите се појдовни броеви на НЗД.]]
'''Евклидов алгоритам''' {{Нав одбележувач|a|a|none}} — ефикасен начин во [[математика]]та, за одредување на [[Најголем заеднички делител|најголемиот заеднички делител]] (НЗД) на дадените броеви. [[Алгоритам|Алгоритмот]] е именуван по [[Стара Грција|старогрчкиот]] математичар [[Евклид]], кој го спомнал во својата книга ''[[Елементи (Евклид)|Елементи]]''.<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. Бидејќи на овој начин се намалува поголемиот од двата почетни броја, со повторување на постапката ќе се добијат сè помали и помали броеви, додека еден од нив не се сведе на нула. Во тој момент, вториот број е еднаков на најголемиот заеднички делител на двата почетни броја. Ако [[Проширен Евклидов алгоритам|редоследот на чекорите во Евклидовиот алгоритам е обратен]], НЗД може да се изрази како [[Линеарна комбинација|збир]] од два почетни броја, од кои секој се множи со [[цел број]], во претходниот пример е 21 = 5 × 105 + (−2) × 252. Оваа важна особина е позната како [[Безуов идентитет]].

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

Евклидовиот алгоритам има широка теоретска и практична примена. Претставува клучен елемент на РСА алгоритам, метод на [[асиметрична криптографија]] што е широко користен во [[Е-бизнис|електронското деловно работење]]. Се користи при решавање на [[диофантски равенки]], на пример при определување на броеви кои задоволуваат повеќекратни конгруенции ([[Кинеска теорема о остацима|Кинеска теорема на остатоци]]) или при определување на [[Мултипликативни инверз|мултипликативната инверзна]] [[Конечно поле|на конечно поле]]. Може да се користи за конструирање на [[верижна дропка|верижни дропки]], во [[Жак Шарл Франсоа Штурм|Штурмовиот]] метод за одредување на реалните нули на полиномите и неколку други современи алгоритми за [[Факторизација на природни броеви|факторизација]] на [[Природен број|природни броеви]]. Конечно, Евклидовиот алгоритам е основната алатка за докажување на [[Теорема|теоремите]] на модерната [[Теорија на броевите|теорија на броеви]], како што е [[Лагранжова теорема за четири квадрати|Лагранжовата теорема за четири квадрати]] и [[Основна теорема на аритметиката|основната теорема на аритметиката]] за уникатната факторизација на природните броеви.

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

== Историја ==
[[Податотека:Euclid.jpg|мини|150x150пкс| Евклидовиот алгоритам веројатно бил познат со векови пред раѓањето на [[Евклид]]. Дел од [[Фрескопис|фреската]] на [[Рафаело Санти|Рафаеловата]] ''[[Атинска школа (слика)|Атинска школа]]'' на која е прикажан Евклид со неговите ученици.]]
Евклидовиот алгоритам е еден од најстарите алгоритми кои сè уште се користат.<ref>. стр. 318.</ref> Во писмена форма, првпат се појавува во [[Евклидови Елементи|Евклидовите ''Елементи'']] во [[3 век п.н.е.|3 век пр.н.е.]], и тоа во книгите VII (тврдења 1<ref>Еуклид, ''Елементи'', [http://poincare.matf.bg.ac.rs/nastavno/zlucic/EUKLID07_T_1.HTML књига, тврђење ]</ref> и 2<ref>Еуклид, ''Елементи'', [http://poincare.matf.bg.ac.rs/nastavno/zlucic/EUKLID07_T_2.HTML књига, тврђење ]</ref>) и X (тврдењата 2<ref name="књига, тврђење">Еуклид, ''Елементи'', [http://poincare.matf.bg.ac.rs/nastavno/zlucic/EUKLID10_T_2.HTML књига, тврђење ]</ref> и 3<ref name="књига, тврђење"/>). Во книгата, алгоритмот е формулиран за цели броеви, додека во книгата е дадена примената на подолги броеви, па тој е со геометриска природа.{{Нав одбележувач|b|b|none}} НЗД за дадени должини ''a'' и ''b'' одговара должината ''g'' која e најдолгата можна должина со која може да се измерат подеднакво должините ''a'' и ''b''. Со други зборови, должините ''a'' и ''b'' може да се добијат со множење со должината ''g'' со некој цел број.

Многу е веројатно дека [[Евклид]] не е изворниот творец на алгоритмот, бидејќи претходно познатото математичко знаење го собрал во „Елементите“.<ref name="Weil_1983">{{Harvnb|Weil|1994}}</ref> Математичарот и историчар [[Бартел Лендерт ван дер Варден|Ван дер Варден]] верува дека седмата книга ''Елементи'' е заснована на учебник за [[Теорија на броевите|теорија на броеви,]] напишан од математичари од [[Питагорејци|Питагоровата школа]].<ref name="van_der_Waerden_1954">{{Наведена книга|title=Science Awakening|last=Bartel Leendert van der Waerden|publisher=P. Noordhoff Ltd|year=1954|series=translated by Arnold Dresden|location=-{Groningen}-|pages=114–115}}</ref> Постојат индиции дека самиот алгоритам бил познат уште во [[Евдокс|Евдокс од Книд]] (околу 375 г.пр.н.е.),<ref>, pp. 318.</ref><ref>{{Наведено списание|last=K|first=von Fritz|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|pages=242–264|doi=10.2307/1969021}}</ref> и можно е да е постар,{{Sfn|Heath|1949}} {{Sfn|Fowler|1987}} судејќи според неговата употреба технички термин, реципрочно одземање во делата на Евклид и [[Аристотел]].<ref>{{Наведено списание|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, стр. 247–248</ref> во [[5 век|5 век од нашата ера]], општото решение во [[1247]] година го објавил [[Чин Чу-шао]] во неговото дело ''Цзју чжан суан шу'' ({{Lang-zh|數書九章}}, [[Девет књига о математичкој вештини|Девет книги за математичката вештина]]).<ref>Tattersall, ''Elementary number theory in nine chapters''. стр. 72, 184–185.</ref>

Во [[Европа]], Евклидовиот алгоритам за првпат бил опишан од [[Клод Гаспар Баше де Мезирјак|Баше]] во второто издание на неговото дело (''Пријатни проблеми за уживање'', [[1624]]),<ref name="autogenerated2"/> и се претпоставува дека се користел при решавањето на диофантските равенки и при конструкцијата на [[верижна дропка|верижни дропки]]. [[Проширен Евклидов алгоритам|Проширениот Евклидов алгоритам]], како метод за ефикасно пресметување на верижните дропки, го објавил англискиот математичар [[Николас Саундерсон|Николас Сандерсон]], припишувајќи му го на [[Роџер Коутс]].<ref>Tattersall, ''Elementary number theory in nine chapters''. стр. 72–76</ref>

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

Се чини дека [[Густав Лежен Дирихле|Дирихле]] бил првиот автор кој го сметал Евклидовиот алгоритам како еден од основните елементи на теоријата на броеви.<ref>Stillwell, ''Numbers and Geometry''. стр. 31–32</ref> Тој забележал дека многу од резултатите од теоријата на броеви (на пример, единствена факторизација) би биле вистинити во кој било друг броен систем каде што може да се примени Евклидовиот алгоритам.<ref>Dirichlet,. стр. 29–31</ref> Предавањата на Дирихле за теоријата на броеви биле дополнети и ревидирани од [[Јулиус Вилхелм Рихард Дедекинд|Рихард Дедекинд]], кој го користел Евклидовиот алгоритам за проучување на нов општ вид на броеви - [[алгебарски цели броеви]]. Тој бил првиот што ја докажал теоремата на [[Пјер де Ферма|Ферма]] за [[Фермаова теорема за збир на два квадрати|збир на два квадрати]] користејќи ја единствената факторизација на Гаусови цели броеви.<ref>{{Наведена книга|url=https://archive.org/details/vorlesungenber00lejeuoft|title=Vorlesungen über Zahlentheorie|last=Дедекинд|first=Рихард|year=1894|editor-last=Peter Gustav Lejeune Dirichlet|chapter=Supplement XI|author-link=Рихард Дедекинд}}</ref> Дополнително, Дедекинд го дефинирал и концептот на [[Евклидов домен|Евклидовиот домен]], броен систем во кој е можно да се дефинира обопшувањето на Евклидовиот алгоритам. На крајот на 19 век, Евклидовиот алгоритам бил постепено занемарен во корист на поопштата теорија за [[Идеал (теорија на прстени)|идеалите]] на Дедекинд.<ref>Stillwell, ''Numbers and Geometry''. стр. 41-42</ref>
{| class="toccolours" cellspacing="5" style="float: left; margin-left: 1em; margin-right: 1em; font-size: 85%; background:#c6dbf7; color:black; width:23em; max-width: 25%;"
| style="text-align: left;" | „Евклидовиот алгоритам е покривката на сите алгоритми, бидејќи е најстариот преживеан нетривијален алгоритам. "
|-
| style="text-align: left;" | [[Доналд Кнут]], (1981). стр. 318.
|}
Процесот на наоѓање апликации на Евклидовиот алгоритам, кој започнал во 19 век, продолжил до ден-денес. [[Жак Шарл Франсоа Штурм|Шарл Штурм]] во [[1829|1829 година]] покажал дека алгоритмот може да се користи во [[Штурмова теорема|Штурмовата верига]], што се користи за броење на реалните нули на [[полином]] во произволно избран интервал.<ref>{{Наведено списание|last=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 век|20]] [[20 век|век]], биле развиени неколку нови алгоритми кои можат да ја проверуваат целобројната поврзаност<ref>[http://www.sciencenews.org/view/generic/id/172/title/Math_Trek__Jazzing_Up_Euclids_Algorithm]</ref><ref>[http://mathworld.wolfram.com/IntegerRelation.html Integer Relation]</ref>, на пример [[Фергусон-Форкејд алгоритам|Фергусон-Форкејдовиот алгоритам]] <ref>{{cite web | url=http://mathworld.wolfram.com/Ferguson-ForcadeAlgorithm.html | title=Ferguson-Forcade Algorithm }}</ref> и и нему сродни, алгоритам LLL <ref>{{cite web | url=http://mathworld.wolfram.com/LLLAlgorithm.html | title=LLL Algorithm }}</ref>, алгоритам HJLS<ref>{{cite web | url=http://mathworld.wolfram.com/HJLSAlgorithm.html | title=HJLS Algorithm }}</ref> и алгоритам PSLQ  <ref>{{cite web | url=http://mathworld.wolfram.com/PSLQAlgorithm.html | title=PSLQ Algorithm }}</ref>

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

== Алгоритам ==

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

Секој чекор започнува со два ненегативни остатоци ''r<sub>k−1</sub> и r<sub>k−2</sub>.'' ''Бидејќи алгоритмот осигурува дека со секој чекор остатоците постојано се намалуваат, тој е помал од неговиот претходник.'' ''Целта'' на  ''k''-тиот чекор е да се определи [[Делење|количникот]] и [[Остаток (математика)|остатокот]] на таков начин што важи еднаквоста:

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

при што ''r<sub>k</sub>'' < ''r<sub>k</sub>''<sub>−1</sub>. Со други зборови, множителите на помалиот број ''r<sub>k</sub>''<sub>−1</sub> се одземаат од поголемиот број ''r<sub>k</sub>''<sub>−2</sub> сè додека добиениот остаток е помал од  ''r<sub>k</sub>''<sub>−1</sub>.

Во првиот чекор (&nbsp;=&nbsp;0), остатоците <sub>−2</sub> и <sub>−1</sub> се еднакви и соодветно, и тоа се токму броевите за кои се бара НЗД. Во следниот чекор (&nbsp;=&nbsp;1), остатоците стануваат еднакви на остатокот од почетниот чекор... Врз основа на ова, алгоритмот може да биде претставен со низа еднаквости:
: ''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">Старк, ''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>≤''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|десно|мини| Анимација на [[Алгоритам|алгоритмот]] во кој почетниот [[правоаголник]] е целосно покриен со сè помали [[квадрат]]и. Димензиите [[Зелена боја|на зелениот]] правоаголник се&nbsp;=&nbsp;1071 и&nbsp;=&nbsp;462. Го покриваат [[Портокалова боја|портокаловите]] квадрати на страница 462 што е можно подолго, по што останува зелен правоаголник со димензии 462×147. Потоа е покриен [[Сина боја|со сини]] квадрати со должина на страна 147, а зелениот правоаголник со димензии 21×147 останува како вишок. Може да биде целосно покриен [[Црвена боја|со црвени]] квадрати чија должина на страна е 21. Тоа значи дека 21 е [[Најголем заеднички делител|НЗД]] броевите 1071 и 462.]]

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

: 1071 = 2 × 462 + 147.

Потоа постапката се повторува за броевите 462 и 147 додека новиот остаток не стане помал од 147, што ќе се случи по [[3 (број)|третото]] одземање (<sub>1</sub>&nbsp;=&nbsp;3), а добиениот остаток ќе биде 21:

: 462 = 3 × 147 + 21.

Во третиот чекор, 21 се одзема од 147 додека новиот остаток не биде помал од 21. Постапката може да се повтори [[7 (број)|седум]] пати ( <sub>2</sub>&nbsp;=&nbsp;7) без остаток.

: 147 = 7 × 21 + 0.

Бидејќи последниот остаток [[0 (број)|е нула]], алгоритмот завршува, при што 21 е најголемиот заеднички делител на броевите 1071 и 462. Добиениот резултат се совпаѓа со НЗД (1071, 462) определен со факторизација на [[Прост број|прости броеви]]. Опишаната постапка може да се прикаже и во табела:
{| class="wikitable" style="margin-left:auto; margin-right:auto; text-align:center"
!Чекор
! Еднаквост
! Количник и остаток
|-
| 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">{{Наведено списание|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> Претпоставката е дека е потребно целосно да се покрие правоаголникот со димензии „пати“ со квадрати, со подолгата страна. Прво, се обидува да ја покрие страницата со квадрати; оваа постапка дава непокриен правоаголен вишок од димензии „ <sub>0</sub> пати“, каде што <sub>0</sub> <. Потоа, користејќи го квадратот на страница <sub>0</sub>, покријте го вишокот. Во овој процес се добива нов непокриен правоаголник со димензии „ <sub>1</sub> на <sub>0</sub> “. За да го покриете, користете ги квадратите од страница <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, ''Напредна теорија на броеви'' . стр. 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 > мод ''r''<sub>''k''−1</sub>

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

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

 '''function''' НЗД(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'' е мод ''b'' одговара на [[Рекурзија|рекурзивна]] [[формула]] ''r''<sub>''k''</sub> ≡ ''r''<sub>''k''−2</sub> мод ''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'' мод ''b'') се заменува со повторено одземање.<ref>Knuth, ''The Art of Computer Programming, Volume 2'', Том 2''. стр. 318–319</ref>

 '''function''' НЗД(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''' НЗД(a, b)
     '''if''' b = 0
        '''return''' a
     '''else'''
        '''return''' НЗД(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><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>
:: '''1а.''' <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>
:: '''2а.''' <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>{{Наведена книга|url=https://archive.org/details/elementarynumber00jone|title=Elementary Number Theory|last=Jones, G. A.|last2=Jones, J. M.|publisher=Springer-Verlag|year=1998|location=New York|pages=[https://archive.org/details/elementarynumber00jone/page/n21 7]–11|chapter=Bezout's Identity|last-author-amp=yes}}</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''. Со самото тоа, Безуовиот идентитет, и претходната постапка можат да бидат обопштени во контекст на Евклидовите домени.

=== Верижни дропки ===
Евклидовиот алгоритам е тесно поврзан со [[Верижни дропки|верижните дропки]]. во облик:

:''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}} Во некои широко прифатени учебници на англиски јазик, како што е Херштајн ({{lang-en|Israel Nathan Herstein}}) ''Topics in Algebra'', или Ланговиот ({{lang-en|Serge Lang}}) ''Algebra'', поимот „Евклидов алгоритам“ се користи за означување [[алгоритам за делење]]. Сепак, тоа е [[теорема]], а не [[алгоритам]].

'''b.''' {{Note_label|b|b|none}} Во модерната употреба, би се рекло дека е формулирано за [[реален број|реални броеви]]. Но, бидејќи должините, плоштините и зафатнините, иако во денешно време се претставени со реални броеви, не се изразуваат во исти мерни единици, ниту пак постои природна единица за должина, површина и зафатнина, идејата за реални броеви тогаш не постоела. време.

== Наводи ==
{{наводи}}

== Литература ==
{{refbegin|2}}
* {{Cite book| 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|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| 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|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|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|last=Дедекинд|first=Рихард|authorlink=Рихард Дедекинд|year=1894|chapter=Supplement XI|title= Vorlesungen über Zahlentheorie|publisher=Braunschweig F. Vieweg | url=https://archive.org/details/vorlesungenber00lejeuoft|editor=Peter Gustav Lejeune Dirichlet}}
* {{Cite book|author=Roberts J.|year=1977|title=Elementary Number Theory: A Problem Oriented Approach|publisher=MIT Press|location=Cambridge, MA|pages=1–8|isbn=0-262-68028-0 }}
* {{Cite book|last1=Lovasz|first1=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|last=Stewart|first=B.M.|year=1964|title=Theory of Numbers| url=https://archive.org/details/theorynumbers00stew|edition=2|publisher=Macmillan|location=New York|id=|pages=[https://archive.org/details/theorynumbers00stew/page/n53 43]–44}}
* {{Cite book|author=Jones, G. A.  |author2=Jones, J. M.  |name-list-style=amp |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|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|last=Дирихле|first=Јохан Петер Густав Лежен|authorlink=Јохан Петер Густав Лежен Дирихле|year=1894|title=Vorlesungen über Zahlentheorie| url=https://archive.org/details/vorlesungenber00lejeuoft|editor=[[Јулијус Вилхелм Рихард Дедекинд|Richard Dedekind]]|publisher=Vieweg| location=Braunschweig}}
* {{Cite book|title=A History of Greek Mathematics, vol. I|last=Heath|first=Sir Thomas|year=1921|publisher=At the Clarendon Press|location= Oxford |id=}}
* {{Cite book|title=Number Theory and Its History| url=https://archive.org/details/numbertheoryitsh00ore|last=Ore|first=Øystein|year=1948|publisher=McGraw–Hill|location=New York}}
* {{Cite book|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|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|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|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|title=Elementary Number Theory and its Applications|last=Rosen|first=Kenneth H. |year=2000|edition= 4|publisher=Addison–Wesley|location=Reading, MA|isbn=978-0-201-87073-2|pages=}}
* {{Cite book|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|title=Elementary number theory in nine chapters| url=https://archive.org/details/elementarynumber0000jame|last=Tattersall|first=James J. |year=2005| publisher=Cambridge University Press|location=Cambridge|isbn=978-0-521-85014-8|pages=}}
* {{Cite book|last=Weil|first=André|year=1983|title = Number Theory|publisher = Birkhäuser|location = Boston|isbn=978-0-8176-3141-3|pages=4–6}}
{{refend}} 

== Надворешни врски ==
* [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] {{En}}

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

[[Категорија:Алгебра]]
[[Категорија:Страници со непрегледан превод]]