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å noen egenskaper ved største felles divisor som gjør oss i stand til å forstå hvorfor algoritmen fungerer.