Največji skupni delitelj in najmanjši skupni večkratnik, Evklidov algoritem

Pojasnjuje vam: Inštruktorica Eva

Največji skupni delitelj (D)

Izberimo si poljubni števili in ju označimo z $a$ in $b$ . Največji skupni delitelj števil $a$ in $b$ je število, ki deli tako število $a$ kot tudi število $b$ .
Če je največji skupni delitelj dveh števil enak 1, pravimo, da sta to tuji si števili. Npr. D(3,7)=1.

Primer iskanja največjega skupnega delitelja dveh naravnih števil:

Vzemimo na primer števili 24 in 36. Tukaj največji skupni delitelj števil lahko poiščemo kar na pamet in dobimo 12.

Če tega ne vidimo takoj, si lahko pomagamo s tem, da posebaj zapišemo delitelje obeh števil:
$D(24)=\lbrace 1, 2, 3, 4, 6, 8, 12, 24 \rbrace$
$D(36)=\lbrace 1, 2, 3, 4, 6, 12, 18, 36 \rbrace$
Nato pogledamo, katere delitelje imata števili skupne in kot rezultat napišemo največjega med njimi; torej 12.

Drug način bi bil, da števili 24 in 36 razstavimo na prafaktorje:
$24=2^3\cdot3$
$36=2^2\cdot3^2$
Največji skupni delitelj dobimo tako, da vzamemo najmanjše potence skupnih prafaktorjev; v tem primeru torej $2^2\cdot3$ . Če to izračunamo, vidimo, da dobimo ravno 12.

Primer iskanja največjega skupnega delitelja, če imamo podana dva izraza:

Vzemimo na primer izraza $x^2-3x-4$ in $x^3-16x$ . Da si olajšamo delo, dani števili najprej razstavimo (pri tem lahko uporabljamo izpostavljanje, Vietovo pravilo, razliko kvadratov ali kubov …).
Števili, ki ju obravnavamo v tem primeru, razstavimo tako:
$x^2-3x-4=(x-4)(x+1)$ in $x^3-16x=x(x-4)(x+4)$
Podobno kot pri prejšnjem primeru (ko smo obravnavali števili 24 in 36) bomo tudi tukaj za največji skupni delitej vzeli najmanjše potence skupnih prafaktorjev; torej $D=(x-4)$

Najmanjši skupni večkratnik (v)

Izberimo si poljubni števili in ju označimo z $a$ in $b$ . Najmanši skupni večkratnik števil $a$ in $b$ je število, ki je tako večkratnik števila $a$ kot tudi večkratnik števila $b$ .
Če iščemo najmanjši skupni večkratnik števil, ki sta si tuji, ga dobimo tako, da števili med seboj kar zmnožimo. Npr. v(3,7)=21.

Primer iskanja najmanjšega skupnega večkratnika dveh naravnih števil:

Vzemimo na primer števili 24 in 36.
En način, da poiščemo najmanjši skupni večkratnik je, da posebaj zapišemo večkratnike obeh števil:
$D(24)=\lbrace 24, 48, 72, 96, 120, \ldots \rbrace$
$D(36)=\lbrace 36, 72, 108, 144, \ldots \rbrace$
Nato pogledamo, katere večkratnike imata števili skupne in kot rezultat napišemo najmanjšega med njimi; torej 72.
Slaba stran takega načina reševanja je, da je za velika števila zelo zamudno.

Boljši način bi bil, da števili 24 in 36 zopet razstavimo na prafaktorje:
$24=2^3\cdot3$
$36=2^2\cdot3^2$
Najmanjši skupni večkratnik dobimo tako, da vzamemo največje potence skupnih prafaktorjev; v tem primeru torej $2^3\cdot3^2$ . Če to izračunamo, vidimo, da dobimo ravno 72.

Obstaja pa še en način; in sicer, da uporabimo formulo, ki povezuje D in v:
$a\cdot b= D(a,b)\cdot v(a,b)$
$v(a,b)=\frac{a\cdot b}{D(a,b)}$
$v(a,b)=\frac{24\cdot36}{12}=72$

Primer iskanja najmanjšega skupnega večkratnika, če imamo podana dva izraza:

Vzemimo na primer izraza $x^2-3x-4$ in $x^3-16x$ . Da si olajšamo delo, dani števili najprej razstavimo (pri tem lahko uporabljamo izpostavljanje, Vietovo pravilo, razliko kvadratov ali kubov …).
Števili, ki ju obravnavamo v tem primeru, razstavimo tako:
$x^2-3x-4=(x-4)(x+1)$ in $x^3-16x=x(x-4)(x+4)$
Podobno kot pri prejšnjem primeru (ko smo obravnavali števili 24 in 36) bomo tudi tukaj za najmanjši skupni večkratnik vzeli največje potence skupnih prafaktorjev; torej $D=x(x-4)(x+4)$ .

Evklidov algoritem

S pomočjo Evklidovega algoritma lahko poiščemo največji skupni delitelj dveh naravnih (ali celih) števil. Osnovni izrek o deljenju pravi: $a=k\cdot b+o$ , pri čemer sta $a$ in $b$ naravni (ali celi) števili, katerih največji skupni delitelj iščemo, $k$ je količnik, $o$ pa ostanek.
$a_1=k_1\cdot b_1+o_1$
$b_1=k_2\cdot o_1+o_2$ ( $b_1$ premaknemo tja, kjer je bil prej $a_1$ , $o_1$ pa tja kjer je bil $b_1$ )
$o_1=k_3\cdot o_2+o_3$ ( $o_1$ premaknemo tja, kjer je bil prej $b_1$ , $o_2$ pa tja, kjer je bil $o_1$ )
$\ \ \ \ \ \ \vdots$
Postopek ponavljamo, dokler ostanek pri deljenju ni enak 0.

Primer iskanja največjega skupnega delitelj z Evklidovim algoritem:

Recimo, da iščemo največji skupni delitelj števil 765 in 567. Števili sta precej veliki, najlažje bomo njun D poiskali z Evklidovim algoritmom:
$765=1\cdot 567+198$
$567=2\cdot 198+171$
$198=1\cdot 171+27$
$171=6\cdot 27+9$
$27=3\cdot 9+0$
Največji skupni delitelj števil 765 in 567 je torej 9 (zadnji ostanek, ki ni bil enak 0).