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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r_{n-1}-q_{n+1}r_{n}} pa zato postupak ponavljamo konačno mnogo puta sve dok ne dođemo do Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle d-d=0.}

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

Neka je $a=bq+r$ za prirodne brojeve Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a>b,0\leq r<b} . Tada vrijedi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle M(a,b)=M(b,r)} .

Naime, ako je $M(a,b)=d,M(b,r)=e$ tada iz gornje jednakosti slijedi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle d\vert r} . No, onda mora biti Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle d\leq e.} Analogno, $e\vert a$ pa je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle e\leq d} .

Dobivamo Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle e=d} , tj. $M(a,b)=M(b,r)$.

Geometrijski dokaz

Zamislimo da imamo dvije dužine $a,b$ prirodnih duljina Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle |a|>|b|} te neka je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 duljinu Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle l'} nanijeti prirodan broj puta i pokriti cijelu dužinu Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle l} te vrijedi $|l|,|l'|\in \mathbb {N}$, reći ćemo da Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle l'} ulazi u Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r.} Očito $d$ ulazi u Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle r,} ali manji ili jednak broj puta nego u $b$ jer je $|r|\leq |b|.$ Sada oduzimamo Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle j<2\log _{2}{b}.}