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 ).

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

$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 3528 = 2³⋅3²⋅7² og 3780 = 2²⋅3³⋅5¹⋅7¹. 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) = 2²⋅3²⋅7¹ = 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_i, b_i ) 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_i, b_i ) er det største av de to samme tallene. Hvis man nå benytter at min(a_i, b_i ) + max(a_i, b_i ) = a_i + b_i , 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⋅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

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

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

$a=q_{0}\cdot b+r_{0}$

som gir kvotienten q₀ og resten r₀. Da vil normalt b > r₀ slik at neste step blir b = q₁⋅r₀ + r₁. På denne måten fortsetter man videre med r₀ = q₂⋅r₁ + r₂. 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_k  blir stadig mindre. Etter n step vil da til slutt resten r_n = 0 og den største felles divisor gcd(a,b) = r_{n - 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 r₂ = 2. Største felles divisor er dermed gcd(1071,462) = r₁ = 21. Beregninger med større tall vil gå tilsvarende raskt.

Bézouts identitet

Fra algoritmen har man at r₀ = a - q₀⋅b slik at denne resten er en lineær kombinasjon av de gitte tallene a og b. I neste step finner man resten r₁ = b - q₁⋅r₀  som derfor også vil være en lineær kombinasjon av a og b. Og slik vil det fortsette med at hver rest r_k  blir en slik lineær kombinasjon. Etter n step tar beregningen slutt. Da er den største felles faktor gcd(a,b) = r_{n - 1} = r_{n - 3} - q_{n - 1}⋅r_{n - 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

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

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

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

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