Tallene 12 og 18 kan faktoriseres som
og
- Største felles divisor
- Dersom vi har to heltall
$a$ $b$ og$n$ er det største tallet som er sånn at$n | a$ og$n | b$ så sier vi at$n$ er største felles divisor mellom$a$ og$b$ , og vi skriver
$\text{gcd}(a,b) = n$ der sff er en forkortelse for "største felles faktor", mens andre skriver
- Noen norske bøker skriver i stedet
$\text{sff}(a,b)$ $\text{sfd}(a,b)$ der sfd står for "største felles divisor".
Når vi skal finne største felles divisor mellom to tall gjør vi slik som innledningsvis ovenfor. Vi faktoriserer hvert tall og ser hvilke faktorer som er felles mellom de to tallene. Produktet av alle faktorene som er felles vil da være største felles divisor.
.
- Eksempel
- Finn
$\text{gcd}(14,84)$
- Vi starter med å faktorisere hvert tall. Vi får da:
$14 = 2 \cdot 7$
$84 = 2 \cdot 42 = 2 \cdot 6 \cdot 7 = 2 \cdot 2 \cdot 3 \cdot 7$ .
- Vi ser at 2 og 7 er faktorer i begge tallene. Da må
$\text{gcd}(14,84) = 2 \cdot 7 = 14$
For å regne ut største felles divisor trenger vi altså å faktorisere hvert tall. Dersom man skal finne største felles divisor til to ganske store tall, kan dette fort bli en utfordring. Under skal vi se på en algoritme som gjør det ganske enkelt for oss å finne største felles divisor uten å faktorisere. Først skal vi se på en viktig egenskap ved største felles divisor som gjør oss i stand til å forstå hvorfor algoritmen fungerer.
og
- Største felles divisor
- Hvis
$a > b$ $r$ er resten vi får når vi deler$a$ på$b$ så er.
$\text{gcd}(a,b) = \text{gcd}(b,r)$
- Bevis
- Vi har fra divisjonsalgoritmen at
, der
$a = bn + r$ $n$ er et naturlig tall.. Da er
- La
$d = \text{gcd}(a,b)$ $d | a$ og$d | b$ , eller med andre ord kan vi finne to hele tall$s$ og$t$ slik at$a = sd$ og$b = td$ . Men da har vi at,
$sd = tdn + r \ \Leftrightarrow \ r = (s-nt)d$ også en faktor i
- altså er
$d$ $r$ . Da må$d | \text{gcd}(b,r)$ . Nå gjenstår det å vise at$d$ er den største felles faktoren mellom$b$ og$r$ . Vi kan gjøre det med et motsigelsesbevis. Anta at$\text{gcd}(b,r) = dd^\prime$ , der$d^\prime > 1$ . Vi antar altså at i tillegg til$d$ har$b$ og$r$ også en faktor$d^\prime$ felles. Nå ser vi hva det vil føre til. Vi har at.
$a = bn + r = s^\prime dd^\prime + t^\prime dd^\prime = (s^\prime + t^\prime)dd^\prime$ , slik at
- Dette er umulig, for da må
$d d^\prime | a$ $\text{gcd}(a,b) = d d^\prime$ . Det strider i mot vårt valg av at$d = \text{gcd}(a,b)$ .er største felles faktor mellom
- Resultatet blir at
$d$ $b$ og$r$ , eller sagt med andre ord:.
$d = \text{gcd}(a,b) = \text{gcd}(b,r)$
Nå kan vi bruke Euklids algoritme til å finne største felles faktor mellom to tall.