Største felles divisor

**Største felles divisor** (forkortet *SFD* eller *sfd*, engelsk **gcd** for *greatest common divisor* ), er det største tallet som deler to tall. På norsk er dette aritmetiske begrepet også omtalt som **største felles faktor** (forkortet *sff*&thinsp;).

I dag er det mest vanlig å bruke den engelske forkortelsen **gcd**. Største felles faktor til to tall *a* og *b* skrives derfor vanligvis som gcd(*a*,*b*) eller noen ganger ganske enkelt som (*a*,*b*). Den kan benyttes ved forkorting av brøker. For eksempel, da 5 er det største hele tallet som deler 15 og 50 uten rest, så  er gcd(15,50)&nbsp;=&nbsp;5. Derfor har man også 15/50 = (5&sdot;3)/(5&sdot;10) = 3/10.

Noen spesielle verdier er gcd(*a*,*a*) = *a* og gcd(*a*,1) = 1 som begge følger fra definisjonen. I tillegg må man ha at  fordi tallet  0 er delelig med alle tall da 

Hvis *a* og *b* ikke har felles faktorer, det vil si at gcd(*a*,*b*)&nbsp;=&nbsp;1, sier man at *a* og *b* er relativt primiske. Det er for eksempel tilfelle med 21 og 64 slik at gcd(64,21) = 1.

For store tall regnes den største felles faktor raskest ut ved bruk av Euklids algoritme.  Den viser at svaret  alltid kan skrives som

:  d = sa + tb 

hvor *s* og *t* er heltall som kan bestemmes. To relativt primiske tall *a* og *b* kan derfor kombineres slik at *1 = sa + tb*. Den samme metoden kan også benyttes i andre tallsystem som er euklidske ringer. I moderne kryptografi benyttes slike ringer hvor elementene består av polynomer.

## Beregning ved faktorisering

Som et eksempel kan man betrakte tallene 12 og 18. Mens 12 har divisorene 1, 2, 3, 4, 6, 12, er de 1, 2, 3, 6, 9, 18 for tallet 18. De felles divisorene er derfor  1, 2, 3, 6. Av disse er 6 den største og derfor gcd(12,18) = 6.

Et mer komplisert eksempel er tallene 3528  og 3780. Disse kan faktoriseres i deres enkelte primtallsfaktorer som gir  og . Største felles divisor kan nå beregnes ved å ta hvert primtall som opptrer i hver faktorisering med den minste av de to eksponentene. I dette eksemplet gir det  = 252.

Mer generelt kan man på samme måte alltid skrive de to gjeldende tallene som

: a = 2^{a_1}3^{a_2}5^{a_3}\cdots p_k^{a_k} = \prod_{i=1}^{k}p_i^{a_i} 
: b = 2^{b_1}3^{b_2}5^{b_3}\cdots p_k^{b_k} = \prod_{i=1}^{k}p_i^{b_i} 

hvor *k* angir det største primtallet som inngår i faktoriseringen. Største felles divisor for disse to tallene følger derfor fra den kompakte formelen

:\gcd(a,b) = \prod_{i=1}^k p_i^{\min(a_i, b_i)}\;

når min(*a<sub>i</sub>,&thinsp;b<sub>i</sub>*&thinsp;) angir det minste av de to eksponentene. Med denne notasjonen kan dermed også minste felles multiplum av de to samme tallene skrives på den tilsvarende formen

:\operatorname{lcm}(a,b) = \prod_{i=1}^k p_i^{\max(a_i, b_i)}.\;

hvor nå max(*a<sub>i</sub>,&thinsp;b<sub>i</sub>*&thinsp;) er det største av de to samme tallene. Hvis man nå benytter at  finner man den viktige sammenhengen

: \gcd(a,b)\cdot\operatorname{lcm}(a,b) = a\cdot b\; .

Som et eksempel kan man igjen betrakte tallene 12 og 18. Da lcm(12,18) = 36 og 12&sdot;18 = 216, er derfor gcd(12,18) = 216/36 = 6 som ble funnet tidligere.

For veldig store tall vil denne primtallsfaktoriseringen ta lang tid eller være i praksis umulig selv med de mest moderne datamaskiner. Da kan man i stedet benytte Euklids algoritme. Tiden den behøver for beregning av største felles divisor er O(log(maks(*a*,*b*)) og kan forholdsvis raskt utføres.

## Euklids algoritme

Tankegangen bak algoritmen kan lett illustreres ved et geometrisk eksempel. Man skal legge fliser på et rektangulært gulv med sidekanter 132 og  306 målt i passende enheter. Man har til disposisjon kvadratiske fliser av alle størrelser, men ønsker å bruke fliser av samme størrelse og færrest mulig. 
Det er klart at hele gulvet kunne dekkes med 1&times;1 fliser. Men det vil da trenges et stort antall, hele 132&times;306 = 40392 fliser. Største felles divisor for de to tallene 132 og 306 gir størrelsen til den største, kvadratiske flisen som kan dekke hele gulvet og som det derfor trenges færrest av.

Hvordan dette tallet i dette tilfellet kan bestemmes rent praktisk, er å først benytte to fliser av typen 132&times;132 som vist i animasjonen til høyre. De dekker en stor del av gulvet, men det er et stykke med lengde 306 - 2&sdot;132 = 42 av langsiden som forblir udekket. Denne delen av gulvet utgjør et mindre rektangel med størrelse 42&times;132. Stordelen av dette kan så dekkes med tre fliser med dimensjon 42&times;42. Dette etterlater et enda mindre rektangel med minste sidekant 132 - 3&sdot;42 = 6. Men da den største siden i dette rektanglet har sidekant 42 = 6&sdot;7, kan man dekke denne siste resten av gulvet med nøyaktig syv 6&times;6 fliser. På den måten har man funnet at gcd(132,306) = 6. Av disse behøves det 40392/6&times;6 = 1122 stykker.

### Systematisk fremgangsmåte

Beregningen består i hvert step å dele et tall med et mindre tall som også oftest gir en rest. Denne resten inngår så på tilsvarende måte i et nytt step av samme sort. Hvis man starter med de to tallene *a* og *b*  a = q_0\cdot b + r_0 

som gir kvotienten *q*0 og resten *r*0. Da vil normalt  *b* >  *r*0 slik at neste step blir  På denne måten fortsetter man videre med   Dette vil så gjenta seg etter *k* step med den generelle operasjonen

:   r_{k-2}= q_k\cdot r_{k-1} + r_k 

hvor restene  *r<sub>k</sub>*&thinsp; blir stadig mindre. Etter *n* step vil da til slutt resten  *r<sub>n</sub>* = 0 og den største felles divisor 

Som en enkel illustrasjon av algoritmen, kan man beregne gcd(1071,462). Den gir da:

Etter *n* = 3 step er den slutt med *r*2 = 2. Største felles divisor er dermed gcd(1071,462) = *r*1 = 21. Beregninger med større tall vil gå tilsvarende raskt.

### Bézouts identitet

Fra algoritmen har man at  *r*0 = *a* - *q*0&sdot;*b* slik at denne resten er en lineær kombinasjon av de gitte tallene *a* og *b*. I neste step finner man resten  *r*1 = *b* - *q*1&sdot;*r*0&thinsp; som derfor også vil være en lineær kombinasjon av *a* og *b*.  Og slik vil det fortsette med at hver rest *r<sub>k</sub>*&thinsp; blir en slik lineær kombinasjon. Etter *n* step tar beregningen slutt. Da  er den største felles faktor  som dermed også er en lineær kombinasjon av de opprinnelige tallene *a* og *b*. Kaller man dette resultatet for *d* = gcd(*a*,*b*), kan man derfor generelt skrive at

:  d = sa + tb 

hvor *s* og *t* må være heltall. De vil i alminnelighet ha motsatt fortegn da *d* er mindre enn både *a* og *b*.  Disse tallene er heller ikke entydige som man ser ved å skrive

:  d = sa + tb = (s - mb)a + (t + ma)b 

hvor *m* er et vilkårlig heltall, positivt eller negativt. Denne måten å uttrykke største felles faktor på kalles for *Bézouts identitet*. En liten utvidelse av Euklids algoritme gir begge tallene *s* og *t* sammen med største felles faktor *d*.

I det siste eksemplet med  har man at  =  slik at man får 

## Generelle egenskaper

Man kan i det følgende anta at *a*, *b* og *m* alle er positive heltall. Fra definisjonen til største felles divisor har den egenskapene

* gcd(*a,b*) = gcd(*b,a*) som man kaller en *kommutativ* egenskap.
* gcd(*a*, gcd(*b*, *c*)) = gcd(gcd(*a*, *b*), *c*)  som er en *assosiativ* egenskap.
* gcd(*a*,0) = *a* da 0 kan deles med alle tall.
* gcd(*m*·*a*, *m*·*b*) = *m*&sdot;gcd(*a*, *b*)
* gcd(*a, b + ma*) = gcd(*a,b*) som også gjelder hvis *m* er negativ såfremt at *b + ma* &ge; 0.
* gcd(*a*1·*a*2, *b*) = gcd(*a*1, *b*)·gcd(*a*2, *b*) hvis *a*1 and *a*2 er relativt primisk.

Fra denne siste egenskapen ser man at hvis et tall *b* skal være  relativt primisk til produktet *a*1·*a*2, må det være primisk relativt til hver av faktorene.

## Referanser


## Litteratur
* J. Reed og J. Aarnes, *Matematikk i vår tid*, Universitetsforlaget, Oslo (1967).
* O. Ore, *Number Theory and Its History*, Dover Publications Inc., New York (1988). ISBN 0-486-65620-9.

## Eksterne lenker
* A. Hashemi, Forkurs i matematikk for nye studenter ved UiB, Bergen (2013).
* Mathportal, gcd calculator
* Matematikk.net, Største felles divisor og Euklids algoritme