Euklidov algoritam

Euklidov algoritam je osnovni postupak pronalaženja najvećeg zajedničkog djelitelja ili najveće zajedničke mjere dvaju prirodnih brojeva u elementarnoj teoriji brojeva.

Ovaj je teorem i njegov dokaz prvi naveo Euklid u sedmoj knjizi čuvenih Elemenata. Algoritam je unatoč svojoj jednostavnosti i danas vrlo koristan te se i dalje uspješno primjenjuje.

Ako imamo neka dva prirodna broja [math]\displaystyle{ a \gt b }[/math] naći ćemo [math]\displaystyle{ M(a, b) = d }[/math] tako da uzastopno oduzimamo [math]\displaystyle{ r = a - qb }[/math] dok ne dođemo do prvog pozitivnog broja [math]\displaystyle{ r }[/math] manjeg od [math]\displaystyle{ b. }[/math] Zatim oduzimamo višekratnike broja [math]\displaystyle{ r }[/math] od [math]\displaystyle{ b }[/math] i dobivamo [math]\displaystyle{ b = q_1r + r_1, 0 \leq r_1 \lt r }[/math] Sada računamo [math]\displaystyle{ r = q_2r_1 + r_2 }[/math] na sličan način, itd. Uočimo da [math]\displaystyle{ d }[/math] dijeli svaku razliku [math]\displaystyle{ r_{n - 1} - q_{n + 1}r_n }[/math] pa zato postupak ponavljamo konačno mnogo puta sve dok ne dođemo do [math]\displaystyle{ d - d = 0. }[/math]

U dokazima Euklidova algoritma, često se koristi sljedeća važna lema.

Neka je [math]\displaystyle{ a = bq + r }[/math] za prirodne brojeve [math]\displaystyle{ a \gt b, 0 \leq r \lt b }[/math]. Tada vrijedi [math]\displaystyle{ M(a, b) = M(b, r) }[/math].

Naime, ako je [math]\displaystyle{ M(a, b) = d, M(b, r) = e }[/math] tada iz gornje jednakosti slijedi [math]\displaystyle{ d \vert r }[/math]. No, onda mora biti [math]\displaystyle{ d \leq e. }[/math] Analogno, [math]\displaystyle{ e \vert a }[/math] pa je [math]\displaystyle{ e \leq d }[/math].

Dobivamo [math]\displaystyle{ e = d }[/math], tj. [math]\displaystyle{ M(a, b) = M(b, r) }[/math].

Geometrijski dokaz

Zamislimo da imamo dvije dužine [math]\displaystyle{ a, b }[/math] prirodnih duljina [math]\displaystyle{ |a| \gt |b| }[/math] te neka je [math]\displaystyle{ M(|a|, |b|) = |d|. }[/math] Dakle, zamišljamo da je [math]\displaystyle{ d }[/math] najdulja dužina od svih onih dužina koje možemo nanijeti prirodan broj puta, dakle bez ostatka, na obje dužine [math]\displaystyle{ a, b. }[/math] Tada je naravno [math]\displaystyle{ a = kd, b = md, k \gt m. }[/math] Uočimo da ovdje znamo najveću zajedničku mjeru dužina [math]\displaystyle{ a, b }[/math] pa ćemo tako lagano pokazati valjanost algoritma.

Napomena. Ako je moguće neku duljinu [math]\displaystyle{ l' }[/math] nanijeti prirodan broj puta i pokriti cijelu dužinu [math]\displaystyle{ l }[/math] te vrijedi [math]\displaystyle{ |l|, |l'| \in \mathbb{N} }[/math], reći ćemo da [math]\displaystyle{ l' }[/math] ulazi u [math]\displaystyle{ l. }[/math]

Očito [math]\displaystyle{ d }[/math] ulazi i u razliku [math]\displaystyle{ 0 \leq a - qb \lt b, }[/math] tj. od dužine [math]\displaystyle{ a }[/math] oduzimamo dužinu [math]\displaystyle{ b }[/math] onoliko puta dok ne dođemo do dijela dužine [math]\displaystyle{ a }[/math] koja nije duža od [math]\displaystyle{ b }[/math] i dobivamo dužinu [math]\displaystyle{ r. }[/math] Očito [math]\displaystyle{ d }[/math] ulazi u [math]\displaystyle{ r, }[/math] ali manji ili jednak broj puta nego u [math]\displaystyle{ b }[/math] jer je [math]\displaystyle{ |r| \leq |b|. }[/math] Sada oduzimamo [math]\displaystyle{ r_1 = b - q_1r, }[/math] i tako dalje.

Svakim korakom od veće dužine oduzimamo kraću za onoliko puta koliko treba da od dulje dužine dobijemo dužinu kraću (ili jednako dugu) od dužine koja je u koraku prije bila dulja. Te su dužine zapravo uvijek višekratnici dužine [math]\displaystyle{ d. }[/math] Ovaj postupak mora imati konačno mnogo koraka pa ćemo, prema tome, u nekom trenutku doći do dužina duljina [math]\displaystyle{ 1 \cdot d, 1 \cdot d, }[/math] što zaista jest najveća zajednička mjera dužina [math]\displaystyle{ a, b. }[/math] Time je algoritam opravdan.

Dodajmo još da je sličan dokaz ovome naveo i sam Euklid.

Učinkovitost algoritma

Neka imamo dva prirodna broja [math]\displaystyle{ a \gt b }[/math]. Nije teško pokazati da za broj koraka [math]\displaystyle{ j }[/math] Euklidovog algoritma za brojeve [math]\displaystyle{ a, b }[/math] vrijedi [math]\displaystyle{ j \lt 2\log_{2}{b}. }[/math]