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 $a>b$ naći ćemo $M(a,b)=d$ tako da uzastopno oduzimamo $r=a-qb$ dok ne dođemo do prvog pozitivnog broja $r$ manjeg od $b.$ Zatim oduzimamo višekratnike broja $r$ od $b$ i dobivamo $b=q_{1}r r_{1},0\leq r_{1}<r$ Sada računamo $r=q_{2}r_{1} r_{2}$ na sličan način, itd. Uočimo da $d$ dijeli svaku razliku $r_{n-1}-q_{n 1}r_{n}$ pa zato postupak ponavljamo konačno mnogo puta sve dok ne dođemo do $d-d=0.$

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

Neka je $a=bq r$ za prirodne brojeve $a>b,0\leq r<b$. Tada vrijedi $M(a,b)=M(b,r)$.

Naime, ako je $M(a,b)=d,M(b,r)=e$ tada iz gornje jednakosti slijedi $d\vert r$. No, onda mora biti $d\leq e.$ Analogno, $e\vert a$ pa je $e\leq d$.

Dobivamo $e=d$, tj. $M(a,b)=M(b,r)$.

Geometrijski dokaz

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

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

Očito $d$ ulazi i u razliku $0\leq a-qb<b,$ tj. od dužine $a$ oduzimamo dužinu $b$ onoliko puta dok ne dođemo do dijela dužine $a$ koja nije duža od $b$ i dobivamo dužinu $r.$ Očito $d$ ulazi u $r,$ ali manji ili jednak broj puta nego u $b$ jer je $|r|\leq |b|.$ Sada oduzimamo $r_{1}=b-q_{1}r,$ 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 $d.$ Ovaj postupak mora imati konačno mnogo koraka pa ćemo, prema tome, u nekom trenutku doći do dužina duljina $1\cdot d,1\cdot d,$ što zaista jest najveća zajednička mjera dužina $a,b.$ Time je algoritam opravdan.

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

Učinkovitost algoritma

Neka imamo dva prirodna broja $a>b$. Nije teško pokazati da za broj koraka $j$ Euklidovog algoritma za brojeve $a,b$ vrijedi $j<2\log _{2}{b}.$