Školjka

%V0 Funkcije $gcd(a,b)$ i $lcm(a,b)$ su najcesci zapis za najveceg zajednickog djeljitelja ([b]G[/b]reatest [b]C[/b]ommon [b]D[/b]ivisor) i najmanjeg zajednickog visekratnika ([b]L[/b]owest [b]C[/b]ommon [b]M[/b]ultiple). Primjetimo prvo da je $gcd(a,b)=gcd(b,a)$ i $gcd(a,b)=gcd(|a|,|a|)$ (Jer predznak broja ne mijenja njegove proste djeljitelje) Funkciju $gcd(a,b)$ mozemo racunati mnogo brze nego faktorizacijom, pomocu [i]Euklidovog algoritma[/i]. Euklidov algoritam koristi svojstvo da je $gcd(a,b)=gcd(a-b,b)$ (Tvrdnja 1). Iz ove tvrdnje jasno vrijedi i da je $gcd(a,b)=gcd(a-kb,b)$, $gcd(a,b)=gcd(a+kb,b)$ za bilo koji cijeli broj $k$ Sam algoritam izgleda ovako: $gcd(a,b)=gcd(a-b,b)$ ako $a \geq b$ $gcd(a,b)=gcd(b,a)$ ako $a<b$ $gcd (a,b)=b$ ako $a=0$ Tako na primjer imamo $gcd(9,6)=gcd(9-6,6)=gcd(3,6)=gcd(6,3)=gcd(3,3)=gcd(0,3)=3$ O funkciji $lcm(a,b)$ se nema sto pametno reci osim jednakosti \break $lcm(a,b)=\dfrac{ab}{gcd(a,b)}$ (Tvrdnja 2) [b]Dokaz tvrnje 1[/b] Neka je $d$ najveci prirodni broj takav da $d|a$ i $d|b$ (dakle, $d=gcd(a,b)$). Ocito je da $d|a-b$ tako da $gcd(a-b,b)$ je barem $d$. Pretpostavimo da postoji $n$ takav da $n>d$ i $n|a-b$ i $n|b$. Tada $n|a$, $n>d$, a $d$ je naveci broj koji djeli i $a$ i $b$. Kontradikcija, dakle takav $n$ ne postoji. [b]Dokaz tvrdnje 2[/b] Zapisimo $gcd(a,b)=d$ $a=dk$ $b=dl$ s time da $gcd(k,l)=1$. Znamo da $a|lcm(a,b)$ to jest $dk|lcm(a,b)$ i $b|lcm(a,b)$ to jest $dl|lcm(a,b)$. Kako je $lcm(a,b)$ [i]najmanji[/i] zajednicki visekratnik, a znamo da je barem $dkl$, dobivamo $lcm(a,b)=dkl$ sto se i dobiva uvrstavanjem u formulu $lcm(a,b)=\dfrac{ab}{gcd(a,b)}$