Euklidov algoritam

U matematici, **Euklidov algoritam** je efikasan način za određivanje najvećeg zajedničkog delioca (NZD) datih brojeva. Algoritam nosi ime po starogrčkom matematičaru Euklidu, koji ga je naveo u VII i X knjizi svojih *[[Euklidovi Elementi|Elemenata]]*.

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 obrne redosled koraka u Euklidovom algoritmu, NZD se može izraziti kao zbir dva polazna broja od kojih je svaki pomnožen nekim celim brojem, u prethodnom primeru je 21 = 5 × 105 + (−2) × 252. Ova važna osobina je poznata kao Bezuov identitet.

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

Euklidov algoritam ima široku terijsku i praktičnu primenu. Predstavlja ključan element RSA algoritma, metode asimetrične kriptografije koja se u značajnoj meri primenjuje u elektronskom poslovanju. Koristi se pri rešavanju diofantskih jednačina, na primer kod određivanja brojeva koji zadovoljavaju višestruke kongruencije (Kineska teorema o ostacima) ili pri određivanju multiplikativnog inverza konačnog polja. Može se upotrebiti za kostruisanje verižnih razlomaka, u Šturmovoj metodi za određivanje realnih nula polinoma, i još nekoliko savremenih algoritama za faktorizaciju prirodnih brojeva. Na kraju, Euklidov algoritam je osnovno sredstvo za dokazivanje teorema moderne 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 teorije kompleksnosti. U 20. veku su razvijene metode za poboljšanje efikasnosti Euklidovog algoritma.

## Historija

Euklidov algoritam je jedan od najstarijih algoritama koji se još uvek upotrebljava. U pisanom obliku, prvi put se pojavljuje u Euklidovim ''Elementima'' u 3. veku p. n. e., i to u VII (tvrđenja 1 i 2) i X knjizi (tvrđenja 2 i 3). U VII knjizi, algoritam je formulisan za cele brojeve, dok je u X knjizi data primena na duži, pa je on geometrijske prirode. 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 ''Elementima'' sabrao do tada poznata matematička znanja. Matematičar i istoričar van der Varden smatra da je sedma knjiga *Elemenata* zasnovana na udžbeniku teorije brojeva koji su napisali matematičari iz pitagorejske škole. Postoje indicije da je sam algoritam bio poznat još Eudoksu sa Knida (oko 375. p. n. e.), a moguće je i da je stariji, sudeći po upotrebi tehničkog termina ἀνθυφαίρεσις (*anthyphairesis*, recipročno oduzimanje) u delima Euklida i Aristotela.

Vekovima kasnije, Euklidov algoritam je ponovo nezavisno otkriven u Indiji i Kini, prvenstveno kao sredstvo za određivanje rešenja diofantskih jednačina koje su se pojavljivale pri rešavanju astronomskih problema i pravljenju preciznih kalendara. U drugoj polovini petog veka, indijski matematičar i astronom Ariabhata opisao je algoritam kao „drobilicu“, možda zbog njegove efikasnosti u rešavanju diofantskih jednačina. Iako je poseban slučaj Kineske teoreme o ostacima naveo već kineski matematičar i astronom Sun Tzu u 5. veku nove ere, opšte rešenje je 1247. godine objavio Cin Czu-šao u svojom delu *Czju čžan suan šu* (, Devet knjiga o matematičkoj veštini).

U Evropi, Euklidov algoritam je prvi put opisao Baše u drugom izdanju svog dela *Problèmes plaisants et délectables* (*Prijatni problemi za uživanje*, 1624), a pretpostavlja se da je korišćen u rešavanju diofantskih jednačina i pri konstrukciji 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žeru Koutsu.

U 19. veku, zahvaljujući Euklidovom algoritmu, došlo je do razvoja novih brojevnih sistema, kao što su Gausovi i Ejzenštajnovi celi brojevi. Gaus je 1815. godine upotrebio Euklidov algoritam da pokaže jedinstvenu faktorizaciju svojih celih brojeva, iako je taj rad objavljen tek skoro dve decenije kasnije, 1832. godine, a sam algoritam je prvi put spomenut u njegovoj knjizi *Aritmetička istraživanja* () objavljenoj 1801. godine, ali samo kao metoda za rad sa verižnim razlomcima.

Čini se da je Dirihle bio prvi autor koji je smatrao Euklidov algoritam za jedan od osnovnih elemenata teorije brojeva. 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. Dirihleova predavanja o teoriji brojeva dopunio je i preradio Rihard Dedekind, koji je koristio Euklidov algoritam za izučavanje novog opšteg tipa brojeva - algebarskih celih brojeva. Prvi je dokazao Fermaovu teoremu o zbiru dva kvadrata koristeći jedinstvenu faktorizaciju Gausovih celih brojeva. Pored toga, Dedekind je definisao i koncept 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 ideala.

Proces iznalaženja primena Euklidovog algoritma započet u 19. veku, nastavio se do danas. Šarl Šturm je 1829. godine pokazao da se algoritam može upotrebiti u Šturmovom lancu koji se koristi za prebrojavanje realnih nula polinoma u proizvoljno izabranom intervalu.

Euklidov algoritam je bio prvi algoritam za utvrđivanje celobrojne povezanosti, odnosno za nalaženje celobrojnih odnosa između samerljivih realnih brojeva. Krajem 20. veka je razvijeno nekoliko novih algoritama koji mogu da proveravaju celobrojnu povezanost, na primer Ferguson-Forkejd algoritam, i njemu srodni, LLL algoritam, HJLS algoritam, i PSLQ algoritam.

Godine 1969. pod nazivom *Euklidova igra* pojavila se strateška igra za dva igrača zasnovana na Euklidovom algoritmu. 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.

## 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. Ukoliko je *k* ceo broj kojim su označeni koraci algoritma počevši od 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**k*&minus;1 i *r**k*&minus;2. Kako algoritam osigurava da se ostaci svakim korakom neprekidno smanjuju, *r**k*&minus;1 je manje od svog prethodnika *r**k*&minus;2. Cilj *k*-tog koraka je da se odrede količnik *q**k* i ostatak *r**k* takvi da važi jednakost

: *r**k*−2 = *q**k* *r**k*−1 + *r**k*

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

U prvom koraku (*k*&nbsp;=&nbsp;0), ostaci *r*−2 i*r*−1 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*0... Na osnovu toga, algoritam se može predstaviti nizom jednakosti

: *a* = *q*0 *b* + *r*0
: *b* = *q*1 *r*0 + *r*1
: *r*0 = *q*2 *r*1 + *r*2
: *r*1 = *q*3 *r*2 + *r*3
: …

Ukoliko je *a* manje od *b*, u prvom koraku algoritma treba zameniti brojeve, odnosno, za *a*&nbsp;0 je jednak nuli, a ostatak *r*0 je jednak *a*. Na taj način, *r**k* je manji od svog prethodnika *r**k*−1 za sve *k*&nbsp;≥&nbsp;0.

Kako se ostaci smanjuju u svakom koraku, i kako ne mogu biti negativni, ostatak *r**N* u nekom trenutku mora postati jednak nuli, pa se tada algoritam zaustavlja. Poslednji ostatak *r**N*−1 koji je različit od nule je najveći zajednički delilac brojeva *a* i *b*. Broj *N* ne može biti beskonačan pošto između nule i prvog ostatka *r*0 postoji konačan broj nenegativnih celih brojeva.

### Dokaz validnosti
Validnost Euklidovog algoritma se može dokazati u dva koraka. U prvom koraku pokazuje se da poslednji ostatak *r**N*−1 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**N*−1; odatle sledi da *g* mora biti manje ili jednako *r**N*−1. Dobijena dva zaključka su konzistentna samo u slučaju da je *r**N*−1&nbsp;=&nbsp;*g*.

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

: *r**N*−2 = *q**N* *r**N*−1

pošto je poslednji ostatak *r**N* jednak nuli. *r**N*−1 deli i *r**N*−3

:*r**N*−3 = *q**N*−1 *r**N*−2 + *r**N*−1

zato što istovremeno deli oba sabirka sa desne strane jednakosti. Razmatrajući redom ostale prethodnike, dobija se da ih *r**N*−1 deli sve, uključujući *a* i *b*. Sa druge strane, nijedan od preostalih ostataka *r**N*−2, *r**N*−3, itd. ne deli istovremeno i *a* i *b*, pošto se u jednakostima uvek javlja ostatak. Kako je *r**N*−1 zajednički delilac brojeva *a* i *b*, mora biti *r**N*−1&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**k*. 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*0, jer važi sledeći niz jednakosti:

:*r*0&nbsp;=&nbsp;*a*&nbsp;−&nbsp;*q*0*b*&nbsp;=&nbsp;*mc*&nbsp;−&nbsp;*q*0*nc*&nbsp;=&nbsp;(*m*&nbsp;−&nbsp;*q*0*n*)*c*.

Analogno se može dobiti da *c* deli i ostatke *r*1, *r*2, itd. Zaključak je da NZD *g* mora da deli *r**N*−1, odakle je *g*&nbsp;≤&nbsp;*r**N*−1. Kako je prema prvom koraku *r**N*−1&nbsp;≤&nbsp;*g*, mora biti *g*&nbsp;=&nbsp;*r**N*−1. Zato je *g* najveći zajednički delilac svih sledećih parova:

:*g* = NZD(*a*, *b*) = NZD(*b*, *r*0) = NZD(*r*0, *r*1) = … = NZD(*r**N*−2, *r**N*−1) = *r**N*−1

### Primer upotrebe algoritma

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 dva puta (*q*0&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 trećeg oduzimanja (*q*1&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 sedam puta (*q*2&nbsp;=&nbsp;7) bez ostatka.

: 147 = 7 × 21 + 0.

Kako je poslednji ostatak 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:

### Vizuelizacija
Euklidov algoritam se može i vizuelno prikazati korišćenjem analogije sa prekrivanjem pravougaonika kvadratima. 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*0 puta *b*“, pri čemu je *r*00 prekriva višak. U tom postupku se dobija novi nepokriveni pravougaonik dimenzija „*r*1 puta *r*0“. Za njegovo prekrivanje se koriste kvadrati stranice *r*1, 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 crvenom bojom), a 21 je NZD brojeva 1071 i 462, što su dimenzije polaznog pravougaonika (prikazanog zelenom bojom).

### Određivanje količnika i ostatka

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

: *r**k*−2 = *q**k* *r**k*−1 + *r**k*

pri čemu je *r**k* po apsolutnoj vrednosti strogo manji od *r**k*−1. Algoritam deljenja obezbeđuje da takav količnik i ostatak uvek postoje. Pored toga, algoritam deljenja za prirodne brojeve tvrdi da su *q**k* i *r**k* jedinstveni, ali taj uslov nije potreban Euklidovom algoritmu.

U Euklidovoj originalnoj verziji algoritma količnik i ostatak se određuju ponavljanjem oduzimanja: *r**k*−1 se oduzima od *r**k*−2sve dok ostatak *r**k* ne postane manji od *r**k*−1. 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**k* &equiv; *r**k*−2 mod *r**k*−1

Ostatak je ekvivalentan klasi kongruencije u modularnoj aritmetici.

### Implementacije
Implementacije algoritma mogu biti prikazane pseudokodom. Na primer, verzija zasnovana na deljenju može biti isprogramirana na sledeći način

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

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

U Euklidovoj verziji koja je zasnovana na oduzimanju, izračunavanje ostatka (*b*&nbsp;=&nbsp;*a* mod *b*) je zamenjeno oduzimanjem koje se ponavlja.

 **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**k*−1 i *r**k*−2. Ukoliko je na početku iteracije *a* veće od *b*, onda *a* dobija vrednost *r**k*−2, pošto je *r**k*−2 > *r**k*−1. 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**k*. Zatim se *b* smanjuje oduzimanjem *a* dok ne postane manje od njega, i tada postaje jednako *r**k*+1. Proces se nastavlja dok *b* ne postane jednako nuli.

Rekurzivna verzija je zasnovana na jednakosti najvećeg zajedničkog delioca sukcesivnih ostataka i rezultata uslova na osnovu koga se izlazi iz petlje NZD(*r**N*−1,&nbsp;0)&nbsp;=&nbsp;*r**N*−1.

 **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. U prethodnim slučajevima, jednakost

: *r**k*−2 = *q**k* *r**k*−1 + *r**k*

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

: *r**k*−2 = (*q**k* + 1) *r**k*−1 + *e**k*

pri čemu je *r**k*−1 po pretpostavci, pozitivan broj. Ako je |*e**k*|&nbsp;*k*|, onda se *r**k* zamenjuje sa *e**k*. Leopold Kroneker je dokazao da se ovom metodom NZD određuje u najmanjem broju koraka u odnosu na sve druge verzije Euklidovog algoritma.

## Drugi brojevni sistemi
Kao što je već objašnjeno, Euklidov algoritam se koristi za određivanje NZD dva prirodna broja. Međutim, moguće je uopštiti ga na realne brojeve, i na egzotične brojevne sisteme kao što su polinomi, 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 nesvodljive elemente koji su ekvivalenti prostih brojeva. Jedinstvena faktorizacija je ključni uslov mnogih dokaza teorije brojeva.

### Primer
NZD dva polinoma P(x)=x^5+x^4-x^3-3x^2-3x-1\, i Q(x)=x^4-2x^3-x^2-2x+1\, nalazimo na sledeći način koristeći Euklidov algoritam (uz skraćivanje i proširenje):
:**1.**  \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) )
::**1a.**  \frac{6x^3+2x^2+2x-4}{2} = 3x^3+x^2+x-2 ; (\frac{R(1)}{2} = R(1s)) 
:**2.**  \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)) 
::**2a.**  \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)) 
:**3.**  \frac{3x^3+x^2+x-2}{x^2+x+1} = 3x-2, R(3) = 0 ; (\frac{R(1s)}{R(2s)} = S(3)) 
: NZD (P(x), Q(x)) = R(2s) = x^2+x+1 \,

## Primene u matematici
### Bezuov identitet
Prema Bezuovom identitetu najveći zajednički delilac, u oznaci *g*, dva cela broja *a* i *b* može biti prikazan kao njihova linearna kombinacija. 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*.

Naznačeni brojevi *s* i *t* se mogu izračunati pomoću količnika *q*0, *q*1, itd. promenom redosleda jednačina u Euklidovom algoritmu. Počevši sa pretposlednjom jednačinom, *g* se može izraziti pomoću količnika *q**N*−1 i dva prethodna ostatka, *r**N*−2 i *r**N*−3.

: *g* = *r**N*−1 = *r**N*−3 − *q**N*−1 *r**N*−2

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

: *r**N*−2 = *r**N*−4 − *q**N*−2 *r**N*−3
: *r**N*−3 = *r**N*−5 − *q**N*−3 *r**N*−4

Zamenom *r**N*−2 i *r**N*−3 sa prethodnim jednakostima u prvoj jednačini dobiće se *g* kao linearna suma ostataka *r**N*−4 i *r**N*−5. Ovaj proces izražavanja ostataka formulama koje uključuju prethodnike može se nastaviti dok se ne dostignu polazni brojevi *a* i *b*:

: *r*2 = *r*0 − *q*2 *r*1
: *r*1 = *b* − *q*1 *r*0
: *r*0 = *a* − *q*0 *b*

Nakon što su svi ostaci *r*0, ..., *r**N* 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 euklidskih domena.

### Verižni razlomci
Euklidov algoritam je u bliskoj vezi sa verižnim razlomcima. Niz jednakosti je moguće zapisati u obliku:

:*a/b* = *q*0 + *r*0/*b*
:*b*/*r*0 = *q*1 + *r*1/*r*0
:*r*0/*r*1 = *q*2 + *r*2/*r*1
:…
:*r**k*−2/*r**k*−1 = *q**k* + *r**k*/*r**k*−1
:…
:*r**N*−2/*r**N*−1 = *q**N*

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*0 + 1/(*q*1 + *r*1/*r*0)

Ako se, zatim, pomoću treće jednakosti zameni razlomak *r*1/*r*0, dobija se:

: *a/b* = *q*0 + 1/(*q*1 + 1/(*q*2 + *r*2/*r*1))

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

:*a/b* = *q*0 + 1/(*q*1 + 1/(*q*2 + 1/(… + 1/*q*N))…) = [*q*0; *q*1, *q*2, …, *q**N*]

Kako je već određen NZD(1071, 462), i kako su izračunati količnici *q**k* 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

## Napomene
* **a.**  U nekim široko prihvaćenim udžbenicima engleskog govornog područja, kao što je Herstajnov () *Topics in Algebra*, ili Langova () *Algebra*, termin „Euklidov algoritam“ se koristi da označi algoritam deljenja. Međutim, to je teorema, a ne algoritam.
* **b.**  U savremenoj upotrebi, reklo bi se da je formulisan za 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

* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 
* 

## Vanjske veze

* Euklidov algoritam  
* Interaktivna demostracija Euklidovog algoritma 
* Euklidov algoritam 
* Euklidov algoritam i igra bazirana na njemu 
* Music and Euclid's algorithm