Hopp til innhold

Største felles divisor

Fra Wikipedia, den frie encyklopedi

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

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) = 5. Derfor har man også 15/50 = (5⋅3)/(5⋅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 gcd(a,0) = a fordi tallet 0 er delelig med alle tall da 0⋅a = 0.

Hvis a og b ikke har felles faktorer, det vil si at gcd(a,b) = 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 d = gcd(a,b) alltid kan skrives som

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

[rediger | rediger kilde]

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 3528 = 23⋅32⋅72 og 3780 = 22⋅33⋅51⋅71. 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 gcd(3528,3780) = 22⋅32⋅71 = 252.

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

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

når min(ai, bi ) 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

hvor nå max(ai, bi ) er det største av de to samme tallene. Hvis man nå benytter at min(ai, bi ) + max(ai, bi ) = ai + bi, finner man den viktige sammenhengen

Som et eksempel kan man igjen betrakte tallene 12 og 18. Da lcm(12,18) = 36 og 12⋅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

[rediger | rediger kilde]
Animation in which progressively smaller square tiles are added to cover a rectangle completely.
Animert illustrasjon av Euklids algoritme ved flislegging av et 132×306 stort gulv.

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×1 fliser. Men det vil da trenges et stort antall, hele 132×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×132 som vist i animasjonen til høyre. De dekker en stor del av gulvet, men det er et stykke med lengde 306 - 2⋅132 = 42 av langsiden som forblir udekket. Denne delen av gulvet utgjør et mindre rektangel med størrelse 42×132. Stordelen av dette kan så dekkes med tre fliser med dimensjon 42×42. Dette etterlater et enda mindre rektangel med minste sidekant 132 - 3⋅42 = 6. Men da den største siden i dette rektanglet har sidekant 42 = 6⋅7, kan man dekke denne siste resten av gulvet med nøyaktig syv 6×6 fliser. På den måten har man funnet at gcd(132,306) = 6. Av disse behøves det 40392/6×6 = 1122 stykker.

Systematisk fremgangsmåte

[rediger | rediger kilde]

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, er derfor det første step i algoritmen på den matematisk form

som gir kvotienten q0 og resten r0. Da vil normalt b > r0 slik at neste step blir b = q1r0 + r1. På denne måten fortsetter man videre med r0 = q2r1 + r2. Dette vil så gjenta seg etter k step med den generelle operasjonen

hvor restene rk  blir stadig mindre. Etter n step vil da til slutt resten rn = 0 og den største felles divisor gcd(a,b) = rn - 1.

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

Step k Deling Kvotient og rest
0 1071 = q0⋅462 + r0 q0 = 2 og r0 = 147
1 462 = q1⋅147 + r1 q1 = 3 og r1 = 21
2 147 = q2⋅21 + r2 q2 = 7 og r2 = 0; slutt

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

Bézouts identitet

[rediger | rediger kilde]

Fra algoritmen har man at r0 = a - q0b slik at denne resten er en lineær kombinasjon av de gitte tallene a og b. I neste step finner man resten r1 = b - q1r0  som derfor også vil være en lineær kombinasjon av a og b. Og slik vil det fortsette med at hver rest rk  blir en slik lineær kombinasjon. Etter n step tar beregningen slutt. Da er den største felles faktor gcd(a,b) = rn - 1 = rn - 3 - qn - 1rn - 2 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

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

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 gcd(1071,462) har man at d = r1 = 462 - 3⋅r0 = 462 - 3⋅(1071 - 2⋅462) slik at man får 21 = 7⋅462 - 3⋅1071.

Generelle egenskaper

[rediger | rediger kilde]

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⋅gcd(a, b)
  • gcd(a, b + ma) = gcd(a,b) som også gjelder hvis m er negativ såfremt at b + ma ≥ 0.
  • gcd(a1·a2, b) = gcd(a1, b)·gcd(a2, b) hvis a1 and a2 er relativt primisk.

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

Referanser

[rediger | rediger kilde]
  1. ^ J.E. Prestesæter, Engelsk-norsk teknisk ordbok, Kunnskapsforlaget, Oslo (2006). ISBN 978-8257-31783-6.
  2. ^ J. Thompson, Matematikkleksikon, Kunnskapsforlaget, Oslo (2006). ISBN 978-8257-31796-6.

Litteratur

[rediger | rediger kilde]
  • 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

[rediger | rediger kilde]