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

Svaki korak počinje sa dva nenegativna ostatka rk−1 i rk−2. Kako algoritam osigurava da se ostaci svakim korakom neprekidno smanjuju, rk−1 je manje od svog prethodnika rk−2. Cilj k-tog koraka je da se odrede količnik qk i ostatak rk takvi da važi jednakost

 rk−2 = qk rk−1 + rk

gde je rk < rk−1. Drugim rečima, umnošci manjeg broja rk−1 se oduzimaju od većeg broja rk−2 sve dok je dobijeni ostatak manji od rk−1.

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

 a = q0 b + r0
 b = q1 r0 + r1
 r0 = q2 r1 + r2
 r1 = q3 r2 + r3
 …

Ukoliko je a manje od b, u prvom koraku algoritma treba zameniti brojeve, odnosno, za a < b, početni količnik q0 je jednak nuli, a ostatak r0 je jednak a. Na taj način, rk je manji od svog prethodnika rk−1 za sve k ≥ 0.

Kako se ostaci smanjuju u svakom koraku, i kako ne mogu biti negativni, ostatak rN u nekom trenutku mora postati jednak nuli, pa se tada algoritam zaustavlja. Poslednji ostatak rN−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 r0 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 rN−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 rN−1; odatle sledi da g mora biti manje ili jednako rN−1. Dobijena dva zaključka su konzistentna samo u slučaju da je rN−1 = g.

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

 rN−2 = qN rN−1

pošto je poslednji ostatak rN jednak nuli. rN−1 deli i rN−3

rN−3 = qN−1 rN−2 + rN−1

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

r0 = a − q0b = mc − q0nc = (m − q0n)c.

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

g = NZD(a, b) = NZD(b, r0) = NZD(r0, r1) = … = NZD(rN−2, rN−1) = rN−1

Primer upotrebe algoritma 

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 (q0 = 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 (q1 = 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 (q2 = 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 „r0 puta b“, pri čemu je r0<b. Zatim se korišćenjem kvadrata stranice r0 prekriva višak. U tom postupku se dobija novi nepokriveni pravougaonik dimenzija „r1 puta r0“. Za njegovo prekrivanje se koriste kvadrati stranice r1, 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 qk i ostatak rk pomoću dva data broja rk−1 i rk−2

 rk−2 = qk rk−1 + rk

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

U Euklidovoj originalnoj verziji algoritma količnik i ostatak se određuju ponavljanjem oduzimanja: rk−1 se oduzima od rk−2sve dok ostatak rk ne postane manji od rk−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,

rk ≡ rk−2 mod rk−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 rk−1, dok se u promenljivoj a nalazi njegov prethodnik, rk−2. Red koda u kome je b := a mod b odgovara rekurzivnoj formuli rk ≡ rk−2 mod rk−1. Pomoćna promenljiva t čuva vrednost rk−1 u trenutku u kome se izračunava sledeći ostatak rk. U poslednjem koraku iterativne petlje, promenljiva b čuva ostatak rk, a promenljiva a njegovog prethodnika, ostatak rk−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 rk−1 i rk−2. Ukoliko je na početku iteracije a veće od b, onda a dobija vrednost rk−2, pošto je rk−2 > rk−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 rk. Zatim se b smanjuje oduzimanjem a dok ne postane manje od njega, i tada postaje jednako rk+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(rN−1, 0) = rN−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

 rk−2 = qk rk−1 + rk

je pretpostavljala da važi rk−1 > rk > 0. Međutim, moguće je iskoristiti alternativni negativni ostatak ek:

 rk−2 = (qk + 1) rk−1 + ek

pri čemu je rk−1 po pretpostavci, pozitivan broj. Ako je |ek| < |rk|, onda se rk zamenjuje sa ek. 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  i  nalazimo na sledeći način koristeći Euklidov algoritam (uz skraćivanje i proširenje):
1. 
1a. 
2. 
2a. 
3.

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 q0, q1, itd. promenom redosleda jednačina u Euklidovom algoritmu. Počevši sa pretposlednjom jednačinom, g se može izraziti pomoću količnika qN−1 i dva prethodna ostatka, rN−2 i rN−3.

 g = rN−1 = rN−3 − qN−1 rN−2

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

 rN−2 = rN−4 − qN−2 rN−3
 rN−3 = rN−5 − qN−3 rN−4

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

 r2 = r0 − q2 r1
 r1 = b − q1 r0
 r0 = a − q0 b

Nakon što su svi ostaci r0, ..., rN 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 = q0 + r0/b
b/r0 = q1 + r1/r0
r0/r1 = q2 + r2/r1
…
rk−2/rk−1 = qk + rk/rk−1
…
rN−2/rN−1 = qN

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 = q0 + 1/(q1 + r1/r0)

Ako se, zatim, pomoću treće jednakosti zameni razlomak r1/r0, dobija se:

 a/b = q0 + 1/(q1 + 1/(q2 + r2/r1))

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

a/b = q0 + 1/(q1 + 1/(q2 + 1/(… + 1/qN))…) = [q0; q1, q2, …, qN]

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

Spoljašnje veze 

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

Algebra