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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle a>b} naći ćemo Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle M(a,b)=d} tako da uzastopno oduzimamo Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 $M(a,b)=M(b,r)$.

Naime, ako je Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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, Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 $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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 $l$ te vrijedi Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle |l|,|l'|\in \mathbb {N} } , reći ćemo da $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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle |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 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 Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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 Obrada nije uspjela. (MathML sa SVG ili PNG za rezervu (preporučljivo za moderne preglednike i alate za pristupačnost): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a > b } . Nije teško pokazati da za broj koraka Obrada nije uspjela. (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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}.}