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

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 naći ćemo tako da uzastopno oduzimamo dok ne dođemo do prvog pozitivnog broja manjeg od Zatim oduzimamo višekratnike broja od i dobivamo Sada računamo na sličan način, itd. Uočimo da dijeli svaku razliku pa zato postupak ponavljamo konačno mnogo puta sve dok ne dođemo do

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

Neka je za prirodne brojeve . Tada vrijedi .

Naime, ako je tada iz gornje jednakosti slijedi . No, onda mora biti Analogno, pa je .

Dobivamo , tj. .

Geometrijski dokazUredi

Zamislimo da imamo dvije dužine   prirodnih duljina   te neka je   Dakle, zamišljamo da je   najdulja dužina od svih onih dužina koje možemo nanijeti prirodan broj puta, dakle bez ostatka, na obje dužine   Tada je naravno   Uočimo da ovdje znamo najveću zajedničku mjeru dužina   pa ćemo tako lagano pokazati valjanost algoritma.

Napomena. Ako je moguće neku dužinu   nanijeti prirodan broj puta i pokriti cijelu dužinu   te vrijedi  , reći ćemo da   ulazi u  

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

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

Učinkovitost algoritmaUredi

Neka imamo dva prirodna broja  . Nije teško pokazati da za broj koraka   Euklidovog algoritma za brojeve   vrijedi  

IzvoriUredi

  1. Andrej Dujella, Teorija brojeva, Školska knjiga, Zagreb, 2019.
  2. https://mathcs.clarku.edu/~djoyce/elements/bookVII/propVII1.html