Euklidov algoritam

Iz Wikipedije, slobodne enciklopedije
Idi na navigaciju Idi na pretragu
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[a] 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.[1]

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[uredi - уреди | uredi izvor]

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.[2] U pisanom obliku, prvi put se pojavljuje u Euklidovim Elementima u 3. veku p. n. e., i to u VII (tvrđenja 1[3] i 2[4]) i X knjizi (tvrđenja 2[5] i 3[6]). U VII knjizi, algoritam je formulisan za cele brojeve, dok je u X knjizi data primena na duži, pa je on geometrijske prirode.[b] 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.[7] 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.[8] Postoje indicije da je sam algoritam bio poznat još Eudoksu sa Knida (oko 375. p. n. e.),[9][10] a moguće je i da je stariji,[11][12] sudeći po upotrebi tehničkog termina ἀνθυφαίρεσις (anthyphairesis, recipročno oduzimanje) u delima Euklida i Aristotela.[13]

Vekovima kasnije, Euklidov algoritam je ponovo nezavisno otkriven u Indiji i Kini,[14] 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“,[15] možda zbog njegove efikasnosti u rešavanju diofantskih jednačina.[16] Iako je poseban slučaj Kineske teoreme o ostacima naveo već kineski matematičar i astronom Sun Tzu[17] 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).[18]

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),[15] 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.[19]

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[20], 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.[14]

Čini se da je Dirihle bio prvi autor koji je smatrao Euklidov algoritam za jedan od osnovnih elemenata teorije brojeva.[21] 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.[22] 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.[23] 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.[24]

„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.[25]

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[26][27], na primer Ferguson-Forkejd algoritam,[28] i njemu srodni, LLL algoritam[29], HJLS algoritam[30], i PSLQ algoritam.[31]

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

Algoritam[uredi - уреди | uredi izvor]

Princip[uredi - уреди | uredi izvor]

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.[35] 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.[36] 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[uredi - уреди | uredi izvor]

Validnost Euklidovog algoritma se može dokazati u dva koraka.[37] 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:[38][39]

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

Primer upotrebe algoritma[uredi - уреди | uredi izvor]

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

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[uredi - уреди | uredi izvor]

Euklidov algoritam se može i vizuelno prikazati korišćenjem analogije sa prekrivanjem pravougaonika kvadratima.[40] 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[uredi - уреди | uredi izvor]

Vista-xmag.png Za više informacija videti Celobrojno deljenje i Algoritam deljenja

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.[41]

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[uredi - уреди | uredi izvor]

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

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 rkrk−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.[43]

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[44] 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[uredi - уреди | uredi izvor]

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.[45][46] 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.[45][46]

Drugi brojevni sistemi[uredi - уреди | uredi izvor]

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[uredi - уреди | uredi izvor]

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[uredi - уреди | uredi izvor]

Bezuov identitet[uredi - уреди | uredi izvor]

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.[47] To znači da je uvek moguće odrediti cele brojeve s i t da važi jednakost g = sa + tb.[48][49]

Naznačeni brojevi s i t se mogu izračunati pomoću količnika q0, q1, itd. promenom redosleda jednačina u Euklidovom algoritmu.[50] 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−3qN−1 rN−2

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

rN−2 = rN−4qN−2 rN−3
rN−3 = rN−5qN−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 = r0q2 r1
r1 = bq1 r0
r0 = aq0 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[uredi - уреди | uredi izvor]

Euklidov algoritam je u bliskoj vezi sa verižnim razlomcima.[51] 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[uredi - уреди | uredi izvor]

  1. Heath, A History Of Greek Mathematics, volume I, str. 399, 404
  2. Knuth, The Art of Computer Programming, Volume 2, str. 318
  3. Euklid, Elementi, knjiga VII, tvrđenje I
  4. Euklid, Elementi, knjiga VII, tvrđenje II
  5. Euklid, Elementi, knjiga X, tvrđenje II
  6. Euklid, Elementi, knjiga X, tvrđenje III
  7. Weil 1994, str. 46-48
  8. Bartel Leendert van der Waerden (1954). Science Awakening. translated by Arnold Dresden. Groningen: P. Noordhoff Ltd. str. 114-115. 
  9. Knuth, The Art of Computer Programming, Volume 2, str. 318.
  10. von Fritz K (1945). "The Discovery of Incommensurability by Hippasus of Metapontum". Ann. Math. 46: 242–264. doi:10.2307/1969021. 
  11. Heath 1949, str. 80-83.
  12. David Fowler (1987). The Mathematics of Plato's Academy: A New Reconstruction. Oxford: Oxford University Press. str. 31-66. ISBN 978-0-19-853912-4. 
  13. Becker, O (1933). "Eudoxus-Studien I. Eine voreuklidische Proportionslehre und ihre Spuren bei Aristoteles und Euklid". Quellen und Studien zur Geschichte der Mathematik B 2: 311–333. 
  14. 14,0 14,1 Stillwell, Numbers and Geometry, str. 31
  15. 15,0 15,1 Tattersall, Elementary number theory in nine chapters, str. 70
  16. Rosen, Elementary Number Theory and its Applications, str. 86–87
  17. Ore, Number Theory and Its History, str. 247–248
  18. Tattersall, Elementary number theory in nine chapters, str. 72, 184–185.
  19. Tattersall, Elementary number theory in nine chapters, str. 72–76
  20. Karl Fridrih Gaus (1832). "Theoria residuorum biquadraticorum". Comm. Soc. Reg. Sci. Gött. Rec. 4. 
    Vidi još i Werke, 2:67–148
  21. Stillwell, Numbers and Geometry, str. 31–32
  22. Dirichlet,Vorlesungen über Zahlentheorie, str. 29–31
  23. Dedekind, Rihard (1894). "Supplement XI". u: Peter Gustav Lejeune Dirichlet. Vorlesungen über Zahlentheorie. 
  24. Stillwell, Elements of Number Theory, str. 41-42
  25. Jacques Charles François Sturm (1829). "Mémoire sur la résolution des équations numériques". Bull. des sciences de Férussac 11: 419–422. 
  26. Jazzing Up Euclid's Algorithm
  27. Integer Relation
  28. Ferguson-Forcade Algorithm
  29. LLL Algorithm
  30. HJLS Algorithm
  31. PSLQ Algorithm
  32. Cole AJ, Davie AJT (1969). "A game based on the Euclidean algorithm and a winning strategy for it". Math. Gaz. 53: 354–357. doi:10.2307/3612461. 
  33. Rosen, Elementary Number Theory and its Applications, str. 95
  34. Roberts J. (1977). Elementary Number Theory: A Problem Oriented Approach. Cambridge, MA: MIT Press. str. 1-8. ISBN 0-262-68028-0. 
  35. Stark, An Introduction to Number Theory, str. 16–20
  36. Stark, An Introduction to Number Theory, str. 18
  37. Stark, An Introduction to Number Theory, str. 16–20.
  38. Knuth, The Art of Computer Programming, Volume 2, str. 320.
  39. Lovasz 2003, str. 100-101
  40. Kimberling C (1983). "A Visual Euclidean Algorithm". Mathematics Teacher 76: 108–109. 
  41. Cohn, Advanced Number Theory, str. 104–110
  42. Knuth, The Art of Computer Programming, Volume 2, str. 319–320
  43. Knuth, The Art of Computer Programming, Volume 2, str. 318–319
  44. Stillwell, Numbers and Geometry, str. 14
  45. 45,0 45,1 Ore, Number Theory and Its History, str. 43.
  46. 46,0 46,1 Stewart 1964, str. 43-44
  47. Jones, G. A. and Jones, J. M. (1998). "Bezout's Identity". Elementary Number Theory. New York: Springer-Verlag. str. 7-11. 
  48. Rosen, Elementary Number Theory and its Applications, str. 81
  49. Cohn, Advanced Number Theory, str. 104
  50. Rosen, Elementary Number Theory and its Applications, str. 91
  51. Vinogradov 1954, str. 3-13

Napomene[uredi - уреди | uredi izvor]

  • 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[uredi - уреди | uredi izvor]

  • 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. 
  • Heath, Sir Thomas (1949). Mathematics in Aristotle. Oxford Press. str. 80-83. 
  • 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. 
  • Dedekind, Rihard (1894). "Supplement XI". u: Peter Gustav Lejeune Dirichlet. Vorlesungen über Zahlentheorie. 
  • Roberts J. (1977). Elementary Number Theory: A Problem Oriented Approach. Cambridge, MA: MIT Press. str. 1-8. ISBN 0-262-68028-0. 
  • Lovasz, Laszlo; Jozsef Pelikan, Katalin L. Vesztergombi (2003). Discrete Mathematics: Elementary and Beyond. New York: Springer-Verlag. str. 100-101. ISBN 978-0-387-95584-1. 
  • Stewart, B.M. (1964). Theory of Numbers (2nd izd.). New York: Macmillan. str. 43-44. 
  • Jones, G. A. and Jones, J. M. (1998). "Bezout's Identity". Elementary Number Theory. New York: Springer-Verlag. str. 7-11. 
  • 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. 
  • 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. 
  • Cohn, Harvey (1962). Advanced Number Theory. New York: Dover. ISBN 978-0-486-64023-5. http://books.google.com/books?id=yMGeElJ8M0wC. 
  • 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. 
  • Stillwell, John (1997). Numbers and Geometry. New York: Springer-Verlag. ISBN 978-0-387-98289-2. 
  • Rosen, Kenneth H. (2000). Elementary Number Theory and its Applications (4th izd.). Reading, MA: Addison–Wesley. ISBN 978-0-201-87073-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[uredi - уреди | uredi izvor]