Euklidov algoritam

Izvor: Wikipedija
Prijeđi na navigaciju Prijeđi na pretraživanje

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 dokaz[uredi | uredi kôd]

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 duljinu 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 algoritma[uredi | uredi kôd]

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

Izvori[uredi | uredi kôd]

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