Største felles divisor og Euklids algoritme
Største felles divisor
Tallene 12 og 18 kan faktoriseres som
- Største felles divisor
- Dersom vi har to heltall
og og er det største tallet som er sånn at og så sier vi at er største felles divisor mellom og , og vi skriver
- Noen norske bøker skriver i stedet
der sff er en forkortelse for "største felles faktor", mens andre skriver 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
.
- Vi starter med å faktorisere hvert tall. Vi får da:
- Vi ser at 2 og 7 er faktorer i begge tallene. Da må
.
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
og er resten vi får når vi deler på så er
.
- Bevis
- Vi har fra divisjonsalgoritmen at
, der er et naturlig tall.
- La
. Da er og , eller med andre ord kan vi finne to hele tall og slik at og . Men da har vi at
, - altså er
også en faktor i . Da må . Nå gjenstår det å vise at er den største felles faktoren mellom og . Vi kan gjøre det med et motsigelsesbevis. Anta at , der . Vi antar altså at i tillegg til har og også en faktor felles. Nå ser vi hva det vil føre til. Vi har at
. - Dette er umulig, for da må
, slik at . Det strider i mot vårt valg av at . - Resultatet blir at
er største felles faktor mellom og , eller sagt med andre ord:
.
Nå kan vi bruke Euklids algoritme til å finne største felles faktor mellom to tall.