WikiSysop: Bot: Automatski unos stranica

2021-12-10T22:13:06Z

Bot: Automatski unos stranica

Nova stranica

'''Euklidov algoritam''' je osnovni postupak pronalaženja [[Najveća zajednička mjera|najvećeg zajedničkog djelitelja]] ili najveće zajedničke mjere dvaju [[Prirodni broj|prirodnih brojeva]] u [[Teorija brojeva|elementarnoj teoriji brojeva]].<ref>Andrej Dujella, Teorija brojeva, Školska knjiga, Zagreb, 2019.</ref>

Ovaj je [[teorem]] i njegov [[dokaz]] prvi naveo [[Euklid]] u sedmoj knjizi čuvenih ''[[Elementi (Euklid)|Elemenata]]''. Algoritam je unatoč svojoj jednostavnosti i danas vrlo koristan te se i dalje uspješno primjenjuje.

Ako imamo neka dva prirodna broja <math> a > b </math> naći ćemo <math> M(a, b) = d</math> tako da uzastopno oduzimamo <math> r = a - qb </math> dok ne dođemo do prvog pozitivnog broja <math> r </math> manjeg od <math> b. </math> Zatim oduzimamo višekratnike broja <math> r </math> od <math> b </math> i dobivamo <math> b = q_1r + r_1, 0 \leq r_1 < r </math> Sada računamo <math> r = q_2r_1 + r_2 </math> na sličan način, itd. Uočimo da <math> d </math> dijeli svaku razliku <math> r_{n - 1} - q_{n + 1}r_n </math> pa zato postupak ponavljamo konačno mnogo puta sve dok ne dođemo do <math> d - d = 0. </math>

U dokazima Euklidova algoritma, često se koristi sljedeća važna lema.
:Neka je <math>a = bq + r</math> za prirodne brojeve <math> a > b, 0 \leq r
< b</math>. Tada vrijedi <math> M(a, b) = M(b, r)</math>.

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

Dobivamo <math> e = d</math>, tj.
<math> M(a, b) = M(b, r)</math>.

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

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

Očito <math> d </math> ulazi i u razliku <math> 0 \leq a - qb < b, </math> tj. od dužine <math> a </math> [[Oduzimanje|oduzimamo]] dužinu <math> b </math> onoliko puta dok ne dođemo do dijela dužine <math> a </math> koja nije duža od <math> b </math> i dobivamo dužinu <math> r. </math> Očito <math> d </math> ulazi u <math> r, </math> ali manji ili jednak broj puta nego u <math> b </math> jer je <math> |r| \leq |b|. </math> Sada oduzimamo
<math> r_1 = b - q_1r, </math> 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 <math> d. </math> Ovaj postupak mora imati konačno mnogo koraka pa ćemo, prema tome, u nekom trenutku doći do dužina duljina <math> 1 \cdot d, 1 \cdot d, </math> što zaista jest najveća zajednička mjera dužina <math> a, b. </math> Time je algoritam opravdan.<ref>https://mathcs.clarku.edu/~djoyce/elements/bookVII/propVII1.html</ref>

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

== Učinkovitost algoritma ==
Neka imamo dva prirodna broja <math>a > b </math>. Nije teško pokazati da za broj koraka <math>j</math> Euklidovog algoritma za brojeve <math>a, b </math> vrijedi <math> j < 2\log_{2}{b}.</math>

==Izvori==
{{izvori}}

[[Kategorija:Matematika]]

Euklidov algoritam - Povijest promjena

WikiSysop: Bot: Automatski unos stranica