Izvorni kod stranice Euklidov algoritam

[[Datoteka:Euclidean algorithm 252 105 animation flipped.gif|mini|100px|Animacija [[Euklid]]ovog [[Algoritam|algoritma]] za brojeve 252 i 105. Jedinični segmenti su zapravo dužine 21, što je [[najveći zajednički delilac]] datih brojeva (NZD). U svakom koraku, manji broj se oduzima od većeg, sve dok se jedan od njih ne svede na [[0 (broj)|nulu]]. Ostatak je NZD polaznih brojeva.]]

U [[Matematika|matematici]], '''Euklidov algoritam'''{{Ref_label|a|a|none}} je efikasan način za određivanje [[Najveći zajednički delilac|najvećeg zajedničkog delioca]] (NZD) datih brojeva. [[Algoritam]] nosi ime po [[Antička Grčka|starogrčkom]] [[matematičar]]u [[Euklid]]u, koji ga je naveo u VII i X knjizi svojih ''[[Euklidovi Elementi|Elemenata]]''.<ref>Heath, ''A History Of Greek Mathematics, volume I'', str. 399, 404</ref>

NZD dva broja je najveći broj koji istovremeno deli oba bez ostatka. Euklidov algoritam je zasnovan na principu da se najveći zajednički delilac dva broja ne menja ukoliko se manji broj oduzme od većeg, pa se zatim odredi NZD novodobijenog broja i manjeg od prethodna dva. Na primer, 21 je NZD za 252 i 105 (252&nbsp;=&nbsp;21&nbsp;×&nbsp;12; 105&nbsp;=&nbsp;21&nbsp;×&nbsp;5); pošto je 252&nbsp;−&nbsp;105&nbsp;=&nbsp;147, NZD za 147 i 105 je takođe 21. Kako je veći od dva polazna broja na ovaj način smanjen, ponavljanjem postupka dobijaće se sve manji brojevi, dok se jedan od njih ne svede na nulu. U tom trenutku, drugi broj je jednak najvećem zajedničkom deliocu dva polazna broja. Ukoliko se [[Prošireni Euklidov algoritam|obrne redosled koraka u Euklidovom algoritmu]], NZD se može izraziti kao [[Linearna kombinacija|zbir]] dva polazna broja od kojih je svaki pomnožen nekim [[Ceo broj|celim brojem]], u prethodnom primeru je {{nowrap begin}}21 = 5 × 105 + (−2) × 252.{{nowrap end}} Ova važna osobina je poznata kao [[Bezuov identitet]].

Prvi poznati sačuvani opis Euklidovog algoritma se nalazi u ''[[Euklidovi Elementi|Elementima]]'' (oko [[3. vek p. n. e.|300. p. n. e.]]), što ga čini najstarijim numeričkim algoritmom koji se još uvek aktivno koristi. U originalu, objašnjen je samo za [[Prirodan broj|prirodne brojeve]] i geometrijske dužine ([[realan broj|realne brojeve]]), ali je u [[19. vek]]u uopšten na [[polinom]]e jedne promenljive i na [[Karl Fridrih Gaus|Gausove]] [[Gausovi celi brojevi|cele brojeve]], što je dovelo do razvoja novih pojmova [[Apstraktna algebra|apstraktne algebre]] kao što je [[Euklidski domen]]. Euklidov algoritam je dalje uopštavan na drugim matematičkim strukturama, poput [[čvor (matematika)|čvorova]] i polinoma više promenljivih.

Euklidov algoritam ima široku terijsku i praktičnu primenu. Predstavlja ključan element [[RSA (algoritam)|RSA algoritma]], metode [[Asimetrična kriptografija|asimetrične kriptografije]] koja se u značajnoj meri primenjuje u [[Elektronsko poslovanje|elektronskom poslovanju]]. Koristi se pri rešavanju [[Diofantske jednačine|diofantskih jednačina]], na primer kod određivanja brojeva koji zadovoljavaju višestruke kongruencije ([[Kineska teorema o ostacima]]) ili pri određivanju [[Multiplikativni inverz|multiplikativnog inverza]] [[Konačno polje|konačnog polja]]. Može se upotrebiti za kostruisanje [[Verižni razlomak|verižnih razlomaka]], u [[Žak Šarl Fransoa Šturm|Šturmovoj]] metodi za određivanje realnih nula polinoma, i još nekoliko savremenih algoritama za [[Faktorizacija prirodnih brojeva|faktorizaciju]] [[prirodan broj|prirodnih brojeva]]. Na kraju, Euklidov algoritam je osnovno sredstvo za dokazivanje [[teorema]] moderne [[Teorija brojeva|teorije brojeva]], kao što su [[Lagranžova teorema o četiri kvadrata]] i [[osnovna teorema aritmetike]] o jedinstvenoj faktorizaciji prirodnih brojeva.

Euklidov algoritam je efikasan način za određivanje NZD velikih brojeva zbog toga što mu ne treba više koraka od petostrukog broja cifara manjeg broja zapisanog sa osnovom 10, što je dokazao [[Gabrijel Lame]] [[1844]]. godine i time označio početak [[Teorija kompleksnosti|teorije kompleksnosti]]. U [[20. vek]]u su razvijene metode za poboljšanje efikasnosti Euklidovog algoritma.

== Historija ==
[[Datoteka:Euclid.jpg|mini|150px|Euklidov algoritam je verovatno bio poznat vekovima pre [[Euklid]]ovog rođenja. Deo [[Rafael]]ove [[Freska|freske]] ''[[Atinska škola]]'' na kome je prikazan Euklid sa učenicima.]]

Euklidov algoritam je jedan od najstarijih algoritama koji se još uvek upotrebljava.<ref>Knuth, ''The Art of Computer Programming, Volume 2'', str. 318</ref> U pisanom obliku, prvi put se pojavljuje u [[Euklidovi Elementi|Euklidovim ''Elementima'']] u [[3. vek p. n. e.|3. veku p. n. e.]], i to u VII (tvrđenja 1<ref>Euklid, ''Elementi'', [http://poincare.matf.bg.ac.rs/nastavno/zlucic/EUKLID07_T_1.HTML knjiga VII, tvrđenje I]</ref> i 2<ref>Euklid, ''Elementi'', [http://poincare.matf.bg.ac.rs/nastavno/zlucic/EUKLID07_T_2.HTML knjiga VII, tvrđenje II]</ref>) i X knjizi (tvrđenja 2<ref>Euklid, ''Elementi'', [http://poincare.matf.bg.ac.rs/nastavno/zlucic/EUKLID10_T_2.HTML knjiga X, tvrđenje II]</ref> i 3<ref>Euklid, ''Elementi'', [http://poincare.matf.bg.ac.rs/nastavno/zlucic/EUKLID10_T_2.HTML knjiga X, tvrđenje III]</ref>). U VII knjizi, algoritam je formulisan za cele brojeve, dok je u X knjizi data primena na duži, pa je on geometrijske prirode.{{Ref_label|b|b|none}} NZD za date duži ''a'' i ''b'' odgovara duži ''g'' koja je najveća moguća duž kojom se mogu izmeriti ''a'' i ''b'' podjednako. Drugim rečima, duži ''a'' i ''b'' se mogu dobiti množenjem duži ''g'' nekim celim brojem.

Vrlo je verovatno da [[Euklid]] nije originalni tvorac algoritma, jer je on u [[Euklidovi Elementi|''Elementima'']] sabrao do tada poznata matematička znanja.<ref name="Weil_1983">{{harvnb|Weil|1994|pp=46-48}}</ref> Matematičar i istoričar [[Bartel Lendert van der Varden|van der Varden]] smatra da je sedma knjiga ''Elemenata'' zasnovana na udžbeniku [[Teorija brojeva|teorije brojeva]] koji su napisali matematičari iz [[Pitagorejci|pitagorejske škole]].<ref name="van_der_Waerden_1954">{{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}}</ref> Postoje indicije da je sam algoritam bio poznat još [[Eudoks|Eudoksu sa Knida]] (oko 375. p. n. e.),<ref>Knuth, ''The Art of Computer Programming, Volume 2'', str. 318.</ref><ref>{{cite journal|author=von Fritz 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> a moguće je i da je stariji,{{sfn|Heath|1949|pp=80-83}}<ref>{{Cite book| author=David Fowler|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}}</ref> sudeći po upotrebi tehničkog termina ἀνθυφαίρεσις (''anthyphairesis'', recipročno oduzimanje) u delima Euklida i Aristotela.<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>

Vekovima kasnije, Euklidov [[algoritam]] je ponovo nezavisno otkriven u [[Indija|Indiji]] i [[Kina|Kini]],<ref name=autogenerated1>Stillwell, ''Numbers and Geometry'', str. 31</ref> prvenstveno kao sredstvo za određivanje rešenja [[Diofantske jednačine|diofantskih jednačina]] koje su se pojavljivale pri rešavanju [[Astronomija|astronomskih]] problema i pravljenju preciznih [[kalendar]]a. U drugoj polovini [[5. vek|petog veka]], indijski matematičar i astronom [[Ariabhata]] opisao je algoritam kao „drobilicu“,<ref name=autogenerated2>Tattersall, ''Elementary number theory in nine chapters'', str. 70</ref> možda zbog njegove efikasnosti u rešavanju diofantskih jednačina.<ref>Rosen, ''Elementary Number Theory and its Applications'', str. 86–87</ref> Iako je poseban slučaj [[Kineska teorema o ostacima|Kineske teoreme o ostacima]] naveo već kineski matematičar i astronom [[Sun Tzu (matematičar)|Sun Tzu]]<ref>Ore, ''Number Theory and Its History'', str. 247–248</ref> u [[5. vek|5. veku nove ere]], opšte rešenje je [[1247]]. godine objavio [[Cin Czu-šao]] u svojom delu ''Czju čžan suan šu'' ({{jez-kin|數書九章}}, [[Devet knjiga o matematičkoj veštini]]).<ref>Tattersall, ''Elementary number theory in nine chapters'', str. 72, 184–185.</ref>

U [[Evropa|Evropi]], Euklidov algoritam je prvi put opisao [[Klod Gaspar Baše de Mezirjak|Baše]] u drugom izdanju svog dela ''Problèmes plaisants et délectables'' (''Prijatni problemi za uživanje'', [[1624]]),<ref name=autogenerated2 /> a pretpostavlja se da je korišćen u rešavanju diofantskih jednačina i pri konstrukciji [[Verižni razlomak|verižnih razlomaka]]. [[Prošireni Euklidov algoritam]] je, kao metodu za efikasno izračunavanje verižnih razlomaka, objavio engleski matematičar [[Nikolas Saunderson]], pripisavši ga [[Rodžer Kouts|Rodžeru Koutsu]].<ref>Tattersall, ''Elementary number theory in nine chapters'', str. 72–76</ref>

U [[19. vek]]u, zahvaljujući Euklidovom algoritmu, došlo je do razvoja novih brojevnih sistema, kao što su [[Gausovi celi brojevi|Gausovi]] i [[Ejzenštajnovi celi brojevi]]. [[Karl Fridrih Gaus|Gaus]] je [[1815]]. godine upotrebio Euklidov algoritam da pokaže jedinstvenu faktorizaciju [[Gausovi celi brojevi|svojih celih brojeva]], iako je taj rad objavljen tek skoro dve decenije kasnije, [[1832]]. godine<ref name="Gauss_1832">{{cite journal |author=[[Karl Fridrih Gaus]]|date=1832|title=Theoria residuorum biquadraticorum|journal=Comm. Soc. Reg. Sci. Gött. Rec.|volume=4}}<br />Vidi još i ''Werke'', '''2''':67–148</ref>, a sam algoritam je prvi put spomenut u njegovoj knjizi ''Aritmetička istraživanja'' ({{jez-lat|Disquisitiones Arithmeticae}}) objavljenoj [[1801]]. godine, ali samo kao metoda za rad sa [[verižni razlomak|verižnim razlomcima]].<ref name=autogenerated1 />

Čini se da je [[Johan Peter Gustav Ležen Dirihle|Dirihle]] bio prvi autor koji je smatrao Euklidov algoritam za jedan od osnovnih elemenata teorije brojeva.<ref>Stillwell, ''Numbers and Geometry'', str. 31–32</ref> Primetio je da bi veliki broj rezultata teorije brojeva (na primer, jedinstvena faktorizacija), bio tačan u bilo kom drugom sistemu brojeva u kome bi se mogao primeniti Euklidov algoritam.<ref>Dirichlet,''Vorlesungen über Zahlentheorie'', str. 29–31</ref> Dirihleova predavanja o teoriji brojeva dopunio je i preradio [[Julijus Vilhelm Rihard Dedekind|Rihard Dedekind]], koji je koristio Euklidov algoritam za izučavanje novog opšteg tipa brojeva - [[Algebarski celi brojevi|algebarskih celih brojeva]]. Prvi je dokazao [[Pjer de Ferma|Fermaovu]] [[Fermaova teorema o zbiru dva kvadrata|teoremu o zbiru dva kvadrata]] koristeći jedinstvenu faktorizaciju Gausovih celih brojeva.<ref>{{Cite book|last=Dedekind|first=Rihard|authorlink=Rihard Dedekind|year=1894|chapter=Supplement XI|title= Vorlesungen über Zahlentheorie|url=https://archive.org/details/vorlesungenber00lejeuoft|editor=Peter Gustav Lejeune Dirichlet}}</ref> Pored toga, Dedekind je definisao i koncept [[Euklidov domen|Euklidovog domena]], brojevnog sistema u kome je moguće definisati uopštenje Euklidovog algoritma. Krajem 19. veka, Euklidov algoritam je postepeno zanemaren u korist Dedekindove opštije teorije [[Ideal (teorija prstena)|ideala]].<ref>Stillwell, ''Elements of Number Theory'', str. 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;" |
„Euklidov algoritam je deka svih algoritama, pošto je to najstariji netrivijalni algoritam koji je preživeo do danas.“
|-
| style="text-align: left;" | [[Donald Knut]], ''The Art of Computer Programming, Vol. 2: Seminumerical Algorithms'', 2nd edition (1981), str. 318.
|}

Proces iznalaženja primena Euklidovog algoritma započet u 19. veku, nastavio se do danas. [[Žak Šarl Fransoa Šturm|Šarl Šturm]] je [[1829]]. godine pokazao da se algoritam može upotrebiti u [[Šturmova teorema|Šturmovom lancu]] koji se koristi za prebrojavanje realnih nula [[polinom]]a u proizvoljno izabranom intervalu.<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>

Euklidov algoritam je bio prvi algoritam za utvrđivanje celobrojne povezanosti, odnosno za nalaženje celobrojnih odnosa između samerljivih realnih brojeva. Krajem [[20. vek]]a je razvijeno nekoliko novih algoritama koji mogu da proveravaju celobrojnu povezanost<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>, na primer [[Ferguson-Forkejd algoritam]],<ref>[http://mathworld.wolfram.com/Ferguson-ForcadeAlgorithm.html Ferguson-Forcade Algorithm]</ref> i njemu srodni, LLL algoritam<ref>[http://mathworld.wolfram.com/LLLAlgorithm.html LLL Algorithm]</ref>, HJLS algoritam<ref>[http://mathworld.wolfram.com/HJLSAlgorithm.html HJLS Algorithm]</ref>, i PSLQ algoritam.<ref>[http://mathworld.wolfram.com/PSLQAlgorithm.html PSLQ Algorithm]</ref>

Godine [[1969]]. pod nazivom ''Euklidova igra'' pojavila se strateška igra za dva igrača zasnovana na Euklidovom algoritmu.<ref>{{cite journal|author=Cole AJ, Davie AJT|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> Na početku, ispred igrača se nalaze dve gomile sa ''a'', odnosno ''b'' kamenčića. Oni naizmenično uzimaju po ''m'' kamenčića sa veće gomile, gde je ''m'' neki umnožak broja kamenčića u manjoj gomili. Konkretno, ukoliko se u nekom trenutku na gomilama nalazi ''x'', odnosno ''y'' kamenčića, gde je ''x'' veće od ''y'', igrač na potezu može smanjiti veću gomilu sa ''x'' na ''x'' − ''ky'' kamenčića, pod uslovom da je broj kamenčića koje oduzima nenegativan [[ceo broj]]. Pobednik je prvi igrač kome pođe za rukom da izbaci sve kamenčiće iz jedne gomile.<ref>Rosen, ''Elementary Number Theory and its Applications'', str. 95</ref><ref>{{Cite book|author=Roberts J.|year=1977|title=Elementary Number Theory: A Problem Oriented Approach|publisher=MIT Press|location=Cambridge, MA| isbn = 0-262-68028-0|pages=1-8}}</ref>

== Algoritam ==
=== Princip ===
Euklidov algoritam je iterativne prirode, što znači da se krajnji rezultat dobija u nizu koraka, dok se međurezultat proizvoljnog koraka koristi u prvom sledećem.<ref>Stark, ''An Introduction to Number Theory'', str. 16–20</ref> Ukoliko je ''k'' [[ceo broj]] kojim su označeni koraci [[Algoritam|algoritma]] počevši od [[0 (broj)|nule]], prvom koraku odgovara jednakost ''k''&nbsp;=&nbsp;0, drugom ''k''&nbsp;=&nbsp;1, i tako dalje.

Svaki korak počinje sa dva nenegativna ostatka ''r''<sub>''k''&minus;1</sub> i ''r''<sub>''k''&minus;2</sub>. Kako algoritam osigurava da se ostaci svakim korakom neprekidno smanjuju, ''r''<sub>''k''&minus;1</sub> je manje od svog prethodnika ''r''<sub>''k''&minus;2</sub>. Cilj ''k''-tog koraka je da se odrede [[deljenje|količnik]] ''q''<sub>''k''</sub> i [[ostatak]] ''r''<sub>''k''</sub> takvi da važi jednakost

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

gde je ''r''<sub>''k''</sub>&nbsp;<&nbsp;''r''<sub>''k''&minus;1</sub>. Drugim rečima, umnošci manjeg broja ''r''<sub>''k''&minus;1</sub> se oduzimaju od većeg broja ''r''<sub>''k''&minus;2</sub> sve dok je dobijeni ostatak manji od ''r''<sub>''k''&minus;1</sub>.

U prvom koraku (''k''&nbsp;=&nbsp;0), ostaci ''r''<sub>−2</sub> i''r''<sub>−1</sub> su jednaki ''a'' i ''b'' respektivno, a to su upravo brojevi za koje se traži NZD. U sledećem koraku (''k''&nbsp;=&nbsp;1), ostaci postaju jednaki ''b'' i ostaku početnog koraka ''r''<sub>0</sub>... Na osnovu toga, algoritam se može predstaviti nizom jednakosti

: ''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>
: …

Ukoliko je ''a'' manje od ''b'', u prvom koraku algoritma treba zameniti brojeve, odnosno, za ''a''&nbsp;<&nbsp;''b'', početni količnik ''q''<sub>0</sub> je jednak nuli, a ostatak ''r''<sub>0</sub> je jednak ''a''. Na taj način, ''r''<sub>''k''</sub> je manji od svog prethodnika ''r''<sub>''k''−1</sub> za sve ''k''&nbsp;≥&nbsp;0.

Kako se ostaci smanjuju u svakom koraku, i kako ne mogu biti negativni, ostatak ''r''<sub>''N''</sub> u nekom trenutku mora postati jednak nuli, pa se tada algoritam zaustavlja.<ref name="Stark_p18">Stark, ''An Introduction to Number Theory'', str. 18</ref> Poslednji ostatak ''r''<sub>''N''−1</sub> koji je različit od nule je [[najveći zajednički delilac]] brojeva ''a'' i ''b''. Broj ''N'' ne može biti [[Beskonačnost|beskonačan]] pošto između nule i prvog ostatka ''r''<sub>0</sub> postoji konačan broj nenegativnih [[Ceo broj|celih brojeva]].

=== Dokaz validnosti ===
Validnost Euklidovog algoritma se može dokazati u dva koraka.<ref>Stark, ''An Introduction to Number Theory'', str. 16–20.</ref> U prvom koraku pokazuje se da poslednji ostatak ''r''<sub>''N''−1</sub> različit od nule deli istovremeno i ''a'' i ''b''. Kako je u pitanju zajednički delilac, on mora biti manji ili jednak najvećem zajedničkom deliocu ''g''. U drugom koraku se pokazuje da proizvoljan zajednički delilac brojeva ''a'' i ''b'', uključujući i ''g'', mora da deli i ''r''<sub>''N''−1</sub>; odatle sledi da ''g'' mora biti manje ili jednako ''r''<sub>''N''−1</sub>. Dobijena dva zaključka su konzistentna samo u slučaju da je ''r''<sub>''N''−1</sub>&nbsp;=&nbsp;''g''.

Da bi se pokazao prvi korak, odnosno da ''r''<sub>''N''−1</sub> deli istovremeno i ''a'' i ''b'', najpre treba primetiti da ''r''<sub>''N''−1</sub> deli svog prethodnika ''r''<sub>''N''−2</sub>

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

pošto je poslednji ostatak ''r''<sub>''N''</sub> jednak nuli. ''r''<sub>''N''−1</sub> deli i ''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>

zato što istovremeno deli oba sabirka sa desne strane jednakosti. Razmatrajući redom ostale prethodnike, dobija se da ih ''r''<sub>''N''−1</sub> deli sve, uključujući ''a'' i ''b''. Sa druge strane, nijedan od preostalih ostataka ''r''<sub>''N''−2</sub>, ''r''<sub>''N''−3</sub>, itd. ne deli istovremeno i ''a'' i ''b'', pošto se u jednakostima uvek javlja ostatak. Kako je ''r''<sub>''N''−1</sub> zajednički delilac brojeva ''a'' i ''b'', mora biti ''r''<sub>''N''−1</sub>&nbsp;≤&nbsp;''g''.

U drugom koraku treba dobiti da proizvoljan [[prirodan broj]] ''c'' koji istovremeno deli i ''a'' i ''b'' (proizvoljan zajednički delilac brojeva ''a'' i ''b'') mora da deli i ostatak ''r''<sub>''k''</sub>. Po definiciji, ''a'' i ''b'' mogu biti zapisani kao umnošci broja ''c'': ''a''&nbsp;=&nbsp;''mc'' i ''b''&nbsp;=&nbsp;''nc'', pri čemu su ''m'' i ''n'' prirodni brojevi. Odatle sledi da ''c'' deli prvi ostatak ''r''<sub>0</sub>, jer važi sledeći niz jednakosti:

:''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''.

Analogno se može dobiti da ''c'' deli i ostatke ''r''<sub>1</sub>, ''r''<sub>2</sub>, itd. Zaključak je da [[Najveći zajednički delilac|NZD]] ''g'' mora da deli ''r''<sub>''N''−1</sub>, odakle je ''g''&nbsp;≤&nbsp;''r''<sub>''N''−1</sub>. Kako je prema prvom koraku ''r''<sub>''N''−1</sub>&nbsp;≤&nbsp;''g'', mora biti ''g''&nbsp;=&nbsp;''r''<sub>''N''−1</sub>. Zato je ''g'' [[najveći zajednički delilac]] svih sledećih parova:<ref>Knuth, ''The Art of Computer Programming, Volume 2'', str. 320.</ref><ref name="Lovasz_2003">{{Harvnb|Lovasz|2003|pp=100-101}}</ref>

:''g'' = NZD(''a'', ''b'') = NZD(''b'', ''r''<sub>0</sub>) = NZD(''r''<sub>0</sub>, ''r''<sub>1</sub>) = … = NZD(''r''<sub>''N''−2</sub>, ''r''<sub>''N''−1</sub>) = ''r''<sub>''N''−1</sub>

=== Primer upotrebe algoritma ===
[[Datoteka:Euclidean algorithm 1071 462.gif|desno|mini|Animacija [[Algoritam|algoritma]] u kojoj se sve manjim [[kvadrat]]ima početni [[pravougaonik]] pokriva u potpunosti. Dimenzije [[Zelena boja|zelenog]] pravougaonika su ''a''&nbsp;=&nbsp;1071 i ''b''&nbsp;=&nbsp;462. On se pokriva [[Narandžasta boja|narandžastim]] kvadratima stranice 462 sve dok je to moguće, posle čega ostane zeleni pravougaonik dimezija 462&times;147. On se zatim pokriva [[Plava boja|plavim]] kvadratima dužine stranica 147, i kao višak ostaje zeleni pravougaonik dimenzija 21&times;147. Njega je moguće bez ostatka pokriti [[Crvena boja|crvenim]] kvadratima čija je stranica dužine 21. To znači da je 21 [[Najveći zajednički delilac|NZD]] brojeva 1071 i 462.]]

Kao ilustracija, Euklidovim algoritmom se može odrediti najveći zajednički delilac brojeva ''a''&nbsp;=&nbsp;1071 i ''b''&nbsp;=&nbsp;462. Najpre se od broja 1071 oduzima broj 462 sve dok se ne dobije ostatak koji je manji od 462. Taj postupak se može ponoviti [[2 (broj)|dva]] puta (''q''<sub>0</sub>&nbsp;=&nbsp;2), uz ostatak 147:

: 1071 = 2 × 462 + 147.

Zatim se ponavlja postupak za brojeve 462 i 147 sve dok novi ostatak ne postane manji od 147, što će se desiti posle [[3 (broj)|trećeg]] oduzimanja (''q''<sub>1</sub>&nbsp;=&nbsp;3), a dobijeni ostatak će biti 21:

: 462 = 3 × 147 + 21.

U trećem koraku, 21 se oduzima od 147 sve dok novi ostatak ne postane manji od 21. Postupak se može ponoviti [[7 (broj)|sedam]] puta (''q''<sub>2</sub>&nbsp;=&nbsp;7) bez ostatka.

: 147 = 7 × 21 + 0.

Kako je poslednji ostatak [[0 (broj)|nula]], algoritam se završava, pri čemu je 21 najveći zajednički delilac brojeva 1071 i 462. Dobijeni rezultat se poklapa sa NZD(1071, 462) određenim pomoću faktorizacije na proste brojeve. Opisani postupak se može prikazati i tablično:

{| class="wikitable" id="basic_Euclidean_algorithm" style="margin-left:auto; margin-right:auto; text-align:center"
!Korak ''k''!!Jednakost!!Količnik i ostatak
|-
| 0 || 1071 = ''q''<sub>0</sub>&times;462 + ''r''<sub>0</sub> || ''q''<sub>0</sub> = 2 i ''r''<sub>0</sub> = 147
|-
| 1 || 462 = ''q''<sub>1</sub>&times;147 + ''r''<sub>1</sub> || ''q''<sub>1</sub> = 3 i ''r''<sub>1</sub> = 21
|-
| 2 || 147 = ''q''<sub>2</sub>&times;21 + ''r''<sub>2</sub> || ''q''<sub>2</sub> = 7 i ''r''<sub>2</sub> = 0; algoritam se završava
|}

=== Vizuelizacija ===
Euklidov algoritam se može i vizuelno prikazati korišćenjem analogije sa prekrivanjem [[pravougaonik]]a [[kvadrat]]ima.<ref name="Kimberling_1983">{{cite journal|author=Kimberling 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> Pretpostavka je da je potrebno u potpunosti prekriti pravougaonik dimezija „''a'' puta ''b''“ kvadratima, pri čemu je ''a'' duža stranica. Najpre se pokušava prekrivanje kvadratima stranice ''b''; ovaj postupak daje nepokriven pravougaoni višak dimenzija „''r''<sub>0</sub> puta ''b''“, pri čemu je ''r''<sub>0</sub><''b''. Zatim se korišćenjem kvadrata stranice ''r''<sub>0</sub> prekriva višak. U tom postupku se dobija novi nepokriveni pravougaonik dimenzija „''r''<sub>1</sub> puta ''r''<sub>0</sub>“. Za njegovo prekrivanje se koriste kvadrati stranice ''r''<sub>1</sub>, itd. Postupak se završava u trenutku kada više nema nepokrivenog viška, odnosno kada kvadrati pokriju pravougaonik u potpunosti. Dužina strane najmanjeg kvadrata je NZD za brojeve koji čine stranice polaznog pravougaonika. Na primer, najmanji kvadrat na susednoj slici je stranice 21 (prikazan [[Crvena boja|crvenom bojom]]), a 21 je [[Najveći zajednički delilac|NZD]] brojeva 1071 i 462, što su dimenzije polaznog pravougaonika (prikazanog [[Zelena boja|zelenom bojom]]).

=== Određivanje količnika i ostatka ===
{{Vidi još|Celobrojno deljenje|Algoritam deljenja}}

U svakom koraku ''k'', Euklidov algoritam izračunava količnik ''q''<sub>''k''</sub> i ostatak ''r''<sub>''k''</sub> pomoću dva data broja ''r''<sub>''k''−1</sub> i ''r''<sub>''k''−2</sub>

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

pri čemu je ''r''<sub>''k''</sub> po [[apsolutna vrednost|apsolutnoj vrednosti]] strogo manji od ''r''<sub>''k''−1</sub>. [[Algoritam deljenja]] obezbeđuje da takav količnik i ostatak uvek postoje. Pored toga, algoritam deljenja za [[prirodan broj|prirodne brojeve]] tvrdi da su ''q''<sub>''k''</sub> i ''r''<sub>''k''</sub> jedinstveni, ali taj uslov nije potreban Euklidovom algoritmu.<ref name="Cohn_1962">Cohn, ''Advanced Number Theory'', str. 104–110</ref>

U [[Euklid]]ovoj originalnoj verziji [[Algoritam|algoritma]] količnik i ostatak se određuju ponavljanjem oduzimanja: ''r''<sub>''k''−1</sub> se oduzima od ''r''<sub>''k''−2</sub>sve dok ostatak ''r''<sub>''k''</sub> ne postane manji od ''r''<sub>''k''−1</sub>. Efikasniji pristup koristi [[celobrojno deljenje]] (tzv. div operaciju) da bi izračunao količnik i određivanje ostatka pri celobrojnom deljenju (tzv. mod operaciju) da bi izračunao ostatak. Rezultat mod operacije je ostatak pri deljenju dva broja; zato je,

:''r''<sub>''k''</sub> [[Modularna aritmetika|&equiv;]] ''r''<sub>''k''−2</sub> mod ''r''<sub>''k''−1</sub>

Ostatak je ekvivalentan klasi kongruencije u [[Modularna aritmetika|modularnoj aritmetici]].

=== Implementacije ===
Implementacije algoritma mogu biti prikazane [[pseudokod]]om. Na primer, verzija zasnovana na deljenju može biti [[programiranje|isprogramirana]] na sledeći način<ref>Knuth, ''The Art of Computer Programming, Volume 2'', str. 319–320</ref>

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

Na početku ''k''-te [[Iteracija|iteracije]], u promenljivoj ''b'' se nalazi poslednji ostatak ''r''<sub>''k''−1</sub>, dok se u promenljivoj ''a'' nalazi njegov prethodnik, ''r''<sub>''k''−2</sub>. Red koda u kome je ''b'' := ''a'' mod ''b'' odgovara [[Rekurzija|rekurzivnoj]] [[Formula|formuli]] ''r''<sub>''k''</sub> ≡ ''r''<sub>''k''−2</sub> mod ''r''<sub>''k''−1</sub>. [[Pomoćna promenljiva]] ''t'' čuva vrednost ''r''<sub>''k''−1</sub> u trenutku u kome se izračunava sledeći ostatak ''r''<sub>''k''</sub>. U poslednjem koraku iterativne petlje, promenljiva ''b'' čuva ostatak ''r''<sub>''k''</sub>, a promenljiva ''a'' njegovog prethodnika, ostatak ''r''<sub>''k''−1</sub>.

U [[Euklid]]ovoj verziji koja je zasnovana na [[Oduzimanje|oduzimanju]], izračunavanje ostatka (''b''&nbsp;=&nbsp;''a'' mod ''b'') je zamenjeno oduzimanjem koje se ponavlja.<ref>Knuth, ''The Art of Computer Programming, Volume 2'', str. 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

Promenljive ''a'' i ''b'' se smenjuju u čuvanju prethodnih ostataka ''r''<sub>''k''−1</sub> i ''r''<sub>''k''−2</sub>. Ukoliko je na početku iteracije ''a'' veće od ''b'', onda ''a'' dobija vrednost ''r''<sub>''k''−2</sub>, pošto je ''r''<sub>''k''−2</sub> > ''r''<sub>''k''−1</sub>. U toku izvršavanja petlje ''a'' se smanjuje oduzimanjem prethodnog ostatka ''b'' sve dok ''a'' ne postane manje od ''b''. Tada je ''a'' sledeći ostatak ''r''<sub>''k''</sub>. Zatim se ''b'' smanjuje oduzimanjem ''a'' dok ne postane manje od njega, i tada postaje jednako ''r''<sub>''k''+1</sub>. Proces se nastavlja dok ''b'' ne postane jednako [[0 (broj)|nuli]].

Rekurzivna verzija<ref>Stillwell, ''Numbers and Geometry'', str. 14</ref> je zasnovana na jednakosti [[Najveći zajednički delilac|najvećeg zajedničkog delioca]] sukcesivnih ostataka i rezultata uslova na osnovu koga se izlazi iz petlje NZD(''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)

Na primer, NZD(1071,&nbsp;462) se dobija pomoću njemu ekvivalentnog NZD(462,&nbsp;1071&nbsp;mod&nbsp;462)&nbsp;=&nbsp;NZD(462,&nbsp;147). Taj NZD se određuje pomoću NZD(147,&nbsp;462&nbsp;mod&nbsp;147)&nbsp;=&nbsp;NZD(147,&nbsp;21), koji se izračunava preko NZD(21,&nbsp;147&nbsp;mod&nbsp;21)&nbsp;=&nbsp;NZD(21,&nbsp;0)&nbsp;=&nbsp;21.

=== Metoda najmanjih apsolutnih ostataka ===
Postoji verzija Euklidovog algoritma u kojoj se količnik u svakom koraku uvećava za jedan ukoliko je rezultujući negativni ostatak po svojoj apsolutnoj vrednosti manji od tipičnog pozitivnog ostatka.<ref name="Ore_least_abs_remainders" >Ore, ''Number Theory and Its History'', str. 43.</ref><ref name="Stewart_1964">{{Harvnb|Stewart|1964|pp=43-44}}</ref> U prethodnim slučajevima, jednakost

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

je pretpostavljala da važi ''r''<sub>''k''−1</sub>&nbsp;>&nbsp;''r''<sub>''k''</sub>&nbsp;>&nbsp;0. Međutim, moguće je iskoristiti alternativni negativni ostatak ''e''<sub>''k''</sub>:

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

pri čemu je ''r''<sub>''k''−1</sub> po pretpostavci, pozitivan broj. Ako je |''e''<sub>''k''</sub>|&nbsp;<&nbsp;|''r''<sub>''k''</sub>|, onda se ''r''<sub>''k''</sub> zamenjuje sa ''e''<sub>''k''</sub>. [[Leopold Kroneker]] je dokazao da se ovom metodom NZD određuje u najmanjem broju koraka u odnosu na sve druge verzije Euklidovog algoritma.<ref name="Ore_least_abs_remainders" /><ref name="Stewart_1964" />

== Drugi brojevni sistemi ==
Kao što je već objašnjeno, Euklidov algoritam se koristi za određivanje NZD dva [[prirodan broj|prirodna broja]]. Međutim, moguće je uopštiti ga na [[realan broj|realne brojeve]], i na egzotične brojevne sisteme kao što su [[polinom]]i, [[kvadratni celi brojevi]] i [[Hurvicovi kvaternioni]], te ga iskoristiti za pokazivanje osnovne osobine jedinstvene faktorizacije, odnosno činjenice da se takvi brojevi moju rastaviti na jedinstven način na [[Nesvodljivi element|nesvodljive elemente]] koji su ekvivalenti [[Prost broj|prostih brojeva]]. Jedinstvena faktorizacija je ključni uslov mnogih [[dokaz]]a [[Teorija brojeva|teorije brojeva]].

=== Primer ===
NZD dva polinoma <math>P(x)=x^5+x^4-x^3-3x^2-3x-1\,</math> i <math>Q(x)=x^4-2x^3-x^2-2x+1\,</math> nalazimo na sledeći način koristeći Euklidov algoritam (uz skraćivanje i proširenje):
:'''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>

== Primene u matematici ==
=== Bezuov identitet ===
Prema [[Etjen Bezu|Bezuovom]] [[Bezuov identitet|identitetu]] [[najveći zajednički delilac]], u oznaci ''g'', dva [[ceo broj|cela broja]] ''a'' i ''b'' može biti prikazan kao njihova linearna kombinacija.<ref>{{Cite book|author=Jones, G. A. and Jones, J. M. |year=1998|chapter= Bezout's Identity |title= Elementary Number Theory |publisher=Springer-Verlag|location=New York|pages=7-11}}</ref> To znači da je uvek moguće odrediti cele brojeve ''s'' i ''t'' da važi jednakost ''g''&nbsp;=&nbsp;''sa''&nbsp;+&nbsp;''tb''.<ref>Rosen, ''Elementary Number Theory and its Applications'', str. 81</ref><ref>Cohn, ''Advanced Number Theory'', str. 104</ref>

Naznačeni brojevi ''s'' i ''t'' se mogu izračunati pomoću količnika ''q''<sub>0</sub>, ''q''<sub>1</sub>, itd. promenom redosleda jednačina u [[Euklid]]ovom [[Algoritam|algoritmu]].<ref>Rosen, ''Elementary Number Theory and its Applications'', str. 91</ref> Počevši sa pretposlednjom jednačinom, ''g'' se može izraziti pomoću količnika ''q''<sub>''N''−1</sub> i dva prethodna ostatka, ''r''<sub>''N''−2</sub> i ''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>

Navedeni ostaci mogu, analogno, biti prikazani pomoću odgovarajućih količnika i ostataka,

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

Zamenom ''r''<sub>''N''−2</sub> i ''r''<sub>''N''−3</sub> sa prethodnim jednakostima u prvoj jednačini dobiće se ''g'' kao linearna suma ostataka ''r''<sub>''N''−4</sub> i ''r''<sub>''N''−5</sub>. Ovaj proces izražavanja ostataka formulama koje uključuju prethodnike može se nastaviti dok se ne dostignu polazni brojevi ''a'' i ''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''

Nakon što su svi ostaci ''r''<sub>0</sub>, ..., ''r''<sub>''N''</sub> zamenjeni, dobijena jednakost prikazuje ''g'' kao linearnu kombinaciju brojeva ''a'' i ''b'': ''g''&nbsp;=&nbsp;''sa''&nbsp;+&nbsp;''tb''. Samim tim, [[Bezuov identitet]], i prethodni postupak mogu biti generalizovani na kontekst [[Euklidski domen|euklidskih domena]].

=== Verižni razlomci ===
Euklidov algoritam je u bliskoj vezi sa [[Verižni razlomak|verižnim razlomcima]].<ref name="Vinogradov_1954">{{harvnb|Vinogradov|1954|pp=3-13}}</ref> Niz jednakosti je moguće zapisati u obliku:

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

Poslednji član na desnoj strani svake jednakosti uvek je jednak recipročnoj vrednosti elementa sa leve strane sledeće jednakosti. Iz prve dve jednakosti se dobija:

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

Ako se, zatim, pomoću treće jednakosti zameni razlomak ''r''<sub>1</sub>/''r''<sub>0</sub>, dobija se:

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

U svakom koraku, krajnji sabirak u obliku razlomka ''r''<sub>''k''</sub>/''r''<sub>''k''−1</sub> se uvek može zameniti upotrebom sledeće jednakosti u nizu, zaključno sa poslednjom. Rezultat je verižni razlomak

:''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>]

Kako je već određen NZD(1071, 462), i kako su izračunati količnici ''q''<sub>''k''</sub> bili redom 2, 3 i 7, razlomak 1071/462 se može zapisati

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

što se može proveriti računanjem.

== Reference ==
{{reflist|2}}

== Napomene ==
* '''a.''' {{Note_label|a|a|none}} U nekim široko prihvaćenim udžbenicima engleskog govornog područja, kao što je Herstajnov ({{jez-engl|Israel Nathan Herstein}}) ''Topics in Algebra'', ili Langova ({{jez-engl|Serge Lang}}) ''Algebra'', termin „Euklidov algoritam“ se koristi da označi [[algoritam deljenja]]. Međutim, to je [[teorema]], a ne [[algoritam]].
* '''b.''' {{Note_label|b|b|none}} U savremenoj upotrebi, reklo bi se da je formulisan za [[realan broj|realne brojeve]]. Ali, kako se dužine, površine i zapremine, iako se danas predstavljaju realnim brojevima, ne izražavaju istim mernim jedinicama, niti postoji prirodna jedinica za dužinu, površinu i zapreminu, u to vreme nije postojala ideja realnih brojeva.

== Literatura ==
{{refbegin|2}}
* {{Cite book |ref= harv|author= Jones 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=Heath|first=Sir Thomas| year=1949|title=Mathematics in Aristotle|publisher=Oxford Press|pages=80-83}}
* {{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=Dedekind|first=Rihard|authorlink=Rihard Dedekind|year=1894|chapter=Supplement XI|title= Vorlesungen über Zahlentheorie|url= https://archive.org/details/vorlesungenber00lejeuoft|editor=Peter Gustav Lejeune Dirichlet}}
* {{Cite book |ref= harv|author=Roberts J.|year=1977|title=Elementary Number Theory: A Problem Oriented Approach|publisher=MIT Press|location=Cambridge, MA| isbn = 0-262-68028-0|pages=1-8}}
* {{Cite book |ref= harv|last=Lovasz|first=Laszlo |coauthors=Jozsef Pelikan, Katalin L. Vesztergombi |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=Stewart|first=B.M.|year=1964|title=Theory of Numbers|edition=2nd|publisher=Macmillan|location=New York|id=|pages=43-44}}
* {{Cite book |ref= harv|author=Jones, G. A. and Jones, J. M. |year=1998|chapter= Bezout's Identity |title= Elementary Number Theory |publisher=Springer-Verlag|location=New York|pages=7-11}}
* {{Cite book |ref= harv|last=Vinogradov|first=Ivan Matveyevich|year=1954| title=Elements of Number Theory |url= https://archive.org/details/elementsofnumber0000imvi|publisher=Dover|location=New York |pages=[https://archive.org/details/elementsofnumber0000imvi/page/3 3]-13}}
* {{Cite book |ref= harv|last=Dirihle|first=Johan Peter Gustav Ležen|authorlink=Johan Peter Gustav Ležen Dirihle|year=1894|title=Vorlesungen über Zahlentheorie|url= https://archive.org/details/vorlesungenber00lejeuoft|editor=[[Julijus Vilhelm Rihard Dedekind|Richard Dedekind]]|publisher=Vieweg| location=Braunschweig}}
* {{Cite book |ref= harv|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 |ref= harv|title=Number Theory and Its History|url= https://archive.org/details/numbertheoryitsh00ore|first=Øystein|last=Ore|year=1948|publisher=McGraw–Hill|location=New York}}
* {{Cite book |ref= harv|last=Cohn|first=Harvey|year=1962|title=Advanced Number Theory |url=http://books.google.com/books?id=yMGeElJ8M0wC |publisher=Dover|location= New York|isbn=978-0-486-64023-5}}
* {{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}}
* {{Cite book |ref= harv|last=Knut|first=Donald|authorlink=Donald Knut|year=1997|title=The Art of Computer Programming, Volume 2: Seminumerical Algorithms|edition=3rd|publisher=Addison–Wesley|isbn=978-0-201-89684-8}}
* {{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}}
* {{Cite book |ref= harv|title=Elementary Number Theory and its Applications|last=Rosen|first=Kenneth H. |year=2000|edition= 4th|publisher=Addison–Wesley|location=Reading, MA|isbn=978-0-201-87073-2}}
* {{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}}
* {{Cite book |ref= harv|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}}
* {{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}}
{{refend}}

== Vanjske veze ==
{{Commonscat|Euclidean algorithm}}
* [http://antje.users.cg.yu/eukld~alg.htm Euklidov algoritam] {{Webarchive|url=https://web.archive.org/web/20080628133831/http://antje.users.cg.yu/eukld~alg.htm |date=2008-06-28 }} {{sr}}
* [http://www.math.sc.edu/~sumner/numbertheory/euclidean/euclidean.html Interaktivna demostracija Euklidovog algoritma] {{en}}
* [http://mathworld.wolfram.com/EuclideanAlgorithm.html Euklidov algoritam] {{en}}
* [http://www.cut-the-knot.org/blue/Euclid.shtml Euklidov algoritam] i [http://www.cut-the-knot.org/blue/EuclidAlg.shtml igra bazirana na njemu] {{en}}
* [http://plus.maths.org/issue40/features/wardhaugh/index.html Music and Euclid's algorithm] {{en}}

{{Izabran}}

[[Kategorija:Algebra]]