Største felles divisor og Euklids algoritme

Største felles divisor

Tallene 12 og 18 kan faktoriseres som <tex>12 = 2 \cdot 2 \cdot 2</tex> og <tex>18 = 2 \cdot 3 \cdot 3</tex>. Vi ser at begge tallene har 2 og 3 som faktorer. Produktet av dem, 6, er da også en faktor i tallene. Vi ser at 6 er den største faktoren de har felles, for faktoren som er til overs i 12 er 2, mens faktoren som er til overs i 18 er 3 -- så de har ingen andre felles faktorer. Vi ser da at 6 er største felles divisor mellom 12 og 18. Det er det største tallet vi kan dele både 12 og 18 på. Vi skriver dette som <tex>\text{gcd}(12,18) = 6</tex>. <tex>\text{gcd}</tex> er en engelsk forkortelse for "greatest common divisor".

Største felles divisor

Dersom vi har to heltall <tex>a</tex> og <tex>b</tex> og <tex>n</tex> er det største tallet som er sånn at <tex>n | a</tex> og <tex>n | b</tex> så sier vi at <tex>n</tex> er største felles divisor mellom <tex>a</tex> og <tex>b</tex>, og vi skriver

<tex>\text{gcd}(a,b) = n</tex>

Noen norske bøker skriver i stedet <tex>\text{sff}(a,b)</tex> der sff er en forkortelse for "største felles faktor", mens andre skriver <tex>\text{sfd}(a,b)</tex> 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 <tex>\text{gcd}(14,84)</tex>.

Vi starter med å faktorisere hvert tall. Vi får da:

<tex>14 = 2 \cdot 7</tex>

<tex>84 = 2 \cdot 42 = 2 \cdot 6 \cdot 7 = 2 \cdot 2 \cdot 3 \cdot 7</tex>

Vi ser at 2 og 7 er faktorer i begge tallene. Da må <tex>\text{gcd}(14,84) = 2 \cdot 7 = 14</tex>.

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.

Største felles divisor

Hvis <tex>a > b</tex> og <tex>r</tex> er resten vi får når vi deler <tex>a</tex> på <tex>b</tex> så er

<tex>\text{gcd}(a,b) = \text{gcd}(b,r)</tex>.

Bevis

Vi har fra divisjonsalgoritmen at

<tex>a = bn + r</tex>, der <tex>n</tex> er et naturlig tall.

La <tex>d = \text{gcd}(a,b)</tex>. Da er <tex>d | a</tex> og <tex>d | b</tex>, eller med andre ord kan vi finne to hele tall <tex>s</tex> og <tex>t</tex> slik at <tex>a = sd</tex> og <tex>b = td</tex>. Men da har vi at

<tex>sd = tdn + r \ \Leftrightarrow \ r = (s-nt)d</tex>,

altså er <tex>d</tex> også en faktor i <tex>r</tex>. Da må <tex>d | \text{gcd}(b,r)</tex>. Nå gjenstår det å vise at <tex>d</tex> er den største felles faktoren mellom <tex>b</tex> og <tex>r</tex>. Vi kan gjøre det med et motsigelsesbevis. Anta at <tex>\text{gcd}(b,r) = dd^\prime</tex>, der <tex>d^\prime > 1</tex>. Vi antar altså at i tillegg til <tex>d</tex> har <tex>b</tex> og <tex>r</tex> også en faktor <tex>d^\prime</tex> felles. Nå ser vi hva det vil føre til. Vi har at

<tex>a = bn + r = s^\prime dd^\prime + t^\prime dd^\prime = (s^\prime + t^\prime)dd^\prime</tex>.

Dette er umulig, for da må <tex>d d^\prime | a</tex>, slik at <tex>\text{gcd}(a,b) = d d^\prime</tex>. Det strider i mot vårt valg av at <tex>d = \text{gcd}(a,b)</tex>.

Resultatet blir at <tex>d</tex> er største felles faktor mellom <tex>b</tex> og <tex>r</tex>, eller sagt med andre ord:

<tex>d = \text{gcd}(a,b) = \text{gcd}(b,r)</tex>.

Nå kan vi bruke Euklids algoritme til å finne største felles faktor mellom to tall.