Euklidov algoritam

Animacija Euklidovog 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 nulu. Ostatak je NZD polaznih brojeva.

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 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 = 21 × 12; 105 = 21 × 5); pošto je 252 − 105 = 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 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.

Istorija

Euklidov algoritam je verovatno bio poznat vekovima pre Euklidovog rođenja. Deo Rafaelove freske Atinska škola na kome je prikazan Euklid sa učenicima.

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 (kin: 數書九章, 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 (lat. Disquisitiones Arithmeticae) 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.

„Euklidov algoritam je deka svih algoritama, pošto je to najstariji netrivijalni algoritam koji je preživeo do danas.“

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. Š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 = 0, drugom k = 1, i tako dalje.

Svaki korak počinje sa dva nenegativna ostatka r_k−1 i r_k−2. Kako algoritam osigurava da se ostaci svakim korakom neprekidno smanjuju, r_k−1 je manje od svog prethodnika r_k−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 < r_k−1. Drugim rečima, umnošci manjeg broja r_k−1 se oduzimaju od većeg broja r_k−2 sve dok je dobijeni ostatak manji od r_k−1.

U prvom koraku (k = 0), ostaci r₋₂ ir₋₁ su jednaki a i b respektivno, a to su upravo brojevi za koje se traži NZD. U sledećem koraku (k = 1), ostaci postaju jednaki b i ostaku početnog koraka r₀... Na osnovu toga, algoritam se može predstaviti nizom jednakosti

a = q₀ b + r₀

b = q₁ r₀ + r₁

r₀ = q₂ r₁ + r₂

r₁ = q₃ r₂ + r₃

…

Ukoliko je a manje od b, u prvom koraku algoritma treba zameniti brojeve, odnosno, za a < b, početni količnik q₀ je jednak nuli, a ostatak r₀ je jednak a. Na taj način, r_k je manji od svog prethodnika r_k−1 za sve k ≥ 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₀ 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 = 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 ≤ 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 = mc i b = nc, pri čemu su m i n prirodni brojevi. Odatle sledi da c deli prvi ostatak r₀, jer važi sledeći niz jednakosti:

r₀ = a − q₀b = mc − q₀nc = (m − q₀n)c.

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

g = NZD(a, b) = NZD(b, r₀) = NZD(r₀, r₁) = … = NZD(r_N−2, r_N−1) = r_N−1

Primer upotrebe algoritma

Animacija algoritma u kojoj se sve manjim kvadratima početni pravougaonik pokriva u potpunosti. Dimenzije zelenog pravougaonika su a = 1071 i b = 462. On se pokriva narandžastim kvadratima stranice 462 sve dok je to moguće, posle čega ostane zeleni pravougaonik dimezija 462×147. On se zatim pokriva plavim kvadratima dužine stranica 147, i kao višak ostaje zeleni pravougaonik dimenzija 21×147. Njega je moguće bez ostatka pokriti crvenim kvadratima čija je stranica dužine 21. To znači da je 21 NZD brojeva 1071 i 462.

Kao ilustracija, Euklidovim algoritmom se može odrediti najveći zajednički delilac brojeva a = 1071 i b = 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₀ = 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₁ = 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₂ = 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:

Korak k	Jednakost	Količnik i ostatak
0	1071 = q0×462 + r0	q0 = 2 i r0 = 147
1	462 = q1×147 + r1	q1 = 3 i r1 = 21
2	147 = q2×21 + r2	q2 = 7 i r2 = 0; algoritam se završava

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₀ puta b“, pri čemu je r₀<b. Zatim se korišćenjem kvadrata stranice r₀ prekriva višak. U tom postupku se dobija novi nepokriveni pravougaonik dimenzija „r₁ puta r₀“. Za njegovo prekrivanje se koriste kvadrati stranice r₁, 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

Vidi još: Celobrojno deljenje i Algoritam deljenja

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 ≡ 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 = 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, 0) = r_N−1.

function nzd(a, b)
    if b = 0
       return a
    else
       return nzd(b, a mod b)

Na primer, NZD(1071, 462) se dobija pomoću njemu ekvivalentnog NZD(462, 1071 mod 462) = NZD(462, 147). Taj NZD se određuje pomoću NZD(147, 462 mod 147) = NZD(147, 21), koji se izračunava preko NZD(21, 147 mod 21) = NZD(21, 0) = 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 > r_k > 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| < |r_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 = sa + tb.

Naznačeni brojevi s i t se mogu izračunati pomoću količnika q₀, q₁, 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₂ = r₀ − q₂ r₁

r₁ = b − q₁ r₀

r₀ = a − q₀ b

Nakon što su svi ostaci r₀, ..., r_N zamenjeni, dobijena jednakost prikazuje g kao linearnu kombinaciju brojeva a i b: g = sa + 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₀ + r₀/b

b/r₀ = q₁ + r₁/r₀

r₀/r₁ = q₂ + r₂/r₁

…

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₀ + 1/(q₁ + r₁/r₀)

Ako se, zatim, pomoću treće jednakosti zameni razlomak r₁/r₀, dobija se:

a/b = q₀ + 1/(q₁ + 1/(q₂ + r₂/r₁))

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₀ + 1/(q₁ + 1/(q₂ + 1/(… + 1/q_N))…) = [q₀; q₁, q₂, …, 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.

Napomene

• a. ^{^} U nekim široko prihvaćenim udžbenicima engleskog govornog područja, kao što je Herstajnov (engl. Israel Nathan Herstein) Topics in Algebra, ili Langova (engl. Serge Lang) 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

• Bartel Leendert van der Waerden (1954). Science Awakening. translated by Arnold Dresden. Groningen: P. Noordhoff Ltd. str. 114–115. 
• Jones, A (1994). „Greek mathematics to AD 300”. Companion encyclopedia of the history and philosophy of the mathematical sciences. New York: Routledge. str. 46—48. ISBN 978-0-415-09238-8. 
• Bartel Leendert van der Waerden (1954). Science Awakening. translated by Arnold Dresden. Groningen: P. Noordhoff Ltd. str. 114–115. 
• Fowler, David (1987). The Mathematics of Plato's Academy: A New Reconstruction. Oxford: Oxford University Press. str. 31–66. ISBN 978-0-19-853912-4. 
• Heath, Sir Thomas (1949). Mathematics in Aristotle. Oxford Press. str. 80–83. 
• Dedekind, Rihard (1894). „Supplement XI”. Ur.: Peter Gustav Lejeune Dirichlet. Vorlesungen über Zahlentheorie. 
• Lovasz, Laszlo; Pelikan, Jozsef; Vesztergombi, Katalin L. (2003). Discrete Mathematics: Elementary and Beyond. New York: Springer-Verlag. str. 100—101. ISBN 978-0-387-95584-1. 
• Jones, G. A. & Jones, J. M. (1998). „Bezout's Identity”. Elementary Number Theory. New York: Springer-Verlag. str. 7–11. 
• Roberts, J. (1977). Elementary Number Theory: A Problem Oriented Approach. Cambridge, MA: MIT Press. str. 1–8. ISBN 0-262-68028-0. 
• Stewart, B.M. (1964). Theory of Numbers (2nd izd.). New York: Macmillan. str. 43–44. 
• Vinogradov, Ivan Matveyevich (1954). Elements of Number Theory. New York: Dover. str. 3–13. 
• Dirihle, Johan Peter Gustav Ležen (1894). Richard Dedekind, ur. Vorlesungen über Zahlentheorie. Braunschweig: Vieweg. 
• Cohn, Harvey (1962). Advanced Number Theory. New York: Dover. ISBN 978-0-486-64023-5. 
• Heath, Sir Thomas (1921). A History of Greek Mathematics, vol. I. Oxford: At the Clarendon Press. 
• Ore, Øystein (1948). Number Theory and Its History. New York: McGraw–Hill. 
• Stark, Harold (1978). An Introduction to Number Theory. MIT Press. ISBN 978-0-262-69060-7. 
• Knut, Donald (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3rd izd.). Addison–Wesley. ISBN 978-0-201-89684-8. 
• Rosen, Kenneth H. (2000). Elementary Number Theory and its Applications (4th izd.). Reading, MA: Addison–Wesley. ISBN 978-0-201-87073-2. 
• Stillwell, John (1997). Numbers and Geometry. New York: Springer-Verlag. ISBN 978-0-387-98289-2. 
• Stillwell, John (2003). Elements of Number Theory. New York: Springer-Verlag. ISBN 978-0-387-95587-2. 
• Tattersall, James J. (2005). Elementary number theory in nine chapters. Cambridge: Cambridge University Press. ISBN 978-0-521-85014-8. 
• Weil, André (1983). Number Theory. Boston: Birkhäuser. str. 4—6. ISBN 978-0-8176-3141-3. 

Spoljašnje veze

• Interaktivna demostracija Euklidovog algoritma (jezik: engleski)
• Euklidov algoritam (jezik: engleski)
• Euklidov algoritam i igra bazirana na njemu (jezik: engleski)
• Music and Euclid's algorithm (jezik: engleski)