Største fælles divisor

Fra Wikipedia, den frie encyklopædi
Spring til navigation Spring til søgning
"Rektangel delt ind i kvadrater. Rektanglet er to 24 kvadrater bredt og 60 kvadrater højt, og kan dækkes af 12x12 fliser."
Et rektangel er dækket med ti firkantede fliser, hvor 12 er SFD for 24 og 60. Mere generelt kan et rektangel dækkes med firkantede fliser med sidelængde hvis og kun hvis er en fælles divisor af og .

Den største fælles divisor (eng. greatest common divisor), forkortet SFD, også kaldet den største fælles faktor for to heltal og , er det største heltal, som er divisor i både og . For eksempel er den 3 den største fælles divisor af 9 og 15. Den største fælles divisor skrives som , eller som efter den engelske betegnelse. Euklids algoritme, opkaldt efter den græske matematiker Euklid (ca. 325 f.Kr.-ca. 270 f.Kr.), er en klassisk effektiv algoritme til at bestemme den største fælles divisor af to heltal. Den største fælles divisor finder anvendelse inden for mange områder af matematikken, og kan bl.a. bruges til at forkorte brøker.

Den største fælles divisor kan visualiseres som følger:[1] Tag udgangspunkt i et rektangulært område af størrelse , og en hvilken som helst fælles divisor der går op i både og . Rektanglets sider kan opdeles i segmenter med længde , der deler rektanglet i et gitter af kvadrater med sidelængde . Den største fælles divisor er den største værdi af som dette er muligt for. Som illustration kan et rektangulært område af størrelse opdeles i et gitter med: kvadrater, kvadrater, kvadrater, kvadrater, kvadrater, eller kvadrater. Derfor er 12 den største fælles divisor af 24 og 60. Når et rektangulært område deles op i kvadrater, vil det have to kvadrater langs den ene kant () og fem kvadrater langs den anden ().

Hvis to naturlige tal og har , kaldes de to tal for indbyrdes primiske. At to tal er indbyrdes primiske er ensbetydende med at deres primtalsopløsninger ikke har nogle primfaktorer til fælles. For eksempel er 6 og 35 indbyrdes primiske, og deres primtalsopløsninger er og . Da de ikke har nogle fælles primfaktorer, vil 1 være det største tal der går op i både 6 og 35. Specielt er primtal inbyrdes primiske med alle andre primtal.

Egenskaber[redigér | redigér wikikode]

Lad og være heltal, og væres deres største fælles divisor. Da og begge er multipla af , kan vi skrive , og , hvor og også er heltal. Der er ikke et større tal , hvor vi kan skrive og på samme form. Heltallene og skal være indbyrdes primiske, primiske, da enhver fælles faktor ellers ville kunne flyttes ud af og for at gøre større. Derfor skal ethvert andet heltal der går op i både og , også gå op i . Den største fælles divisor af og er den unikke (positive) fælles divisor af og der er deleligt med enhver anden fælles divisor . [2]

SFD for to tal og er produktet af de primfaktorer, de to tal har til fælles, hvor den samme primfaktor kan bruges flere gange, men kun så længe produktet af disse faktorer deler både og .[3] F.eks. eftersom 1386 kan primtalsopløses til og 3213 kan primtalsopløses til , er den største fælles divisor af 1386 og 3213 netop , produktet af deres fælles primtalsfaktorer. Hvis to tal ikke har nogen primtalsfaktorer til fælles, er deres største fælles divisor 1 (som her kommer fra det tomme produkt), med andre ord er de indbyrdes primiske.

Den største fælles divisor er symmetrisk

Den største fælles divisor af tre eller flere tal er lig med produktet af de primfaktorer, der er fælles for alle tallene, [4] men det kan også beregnes ved gentagne gange at beregne SFD af talpar.[5] F.eks.

En anden, men ækvivalent, definition af SFD er nyttig i avanceret matematik, især ringteori.[6] Den største fælles divisor af to heltal og , som begge er forskellig fra nul, er også den mindste positive lineære kombination med heltalskoefficienter af de to tal, det vil sige det mindste positive tal på formen , hvor og er heltal. Mængden med alle lineære kombinationer med heltalskoefficienter af og er den samme som mængden med alle multiplier af , dvs. alle tal på formen , hvor er et heltal. I moderne matematisk sprog er det ideal, der genereres af og , lig det ideal, der genereres af alene (et ideal genereret af et enkelt element kaldes et hovedideal, og alle idealer af heltal er hovedidealer). Nogle egenskaber ved SFD er lettere at se med denne definition for eksempel det faktum, at enhver fælles divisor af og også deler den største fælles divisor (fordi divisoren deler begge led i ).

Anvendelser[redigér | redigér wikikode]

Den største fælles divisor kan bl.a. bruges til at forkorte brøker. Hvis og er heltal, og , da vil

,

hvor både og også er heltal, fordi er divisor i begge tal. Den sidste brøk er uforkortelig, dvs. den kan ikke forkortes mere.

Se også[redigér | redigér wikikode]

Referencer[redigér | redigér wikikode]

  1. ^ Grossman, J. W. (1990). Discrete Mathematics. New York: Macmillan. s. 213. ISBN 0-02-348331-8. 
  2. ^ LeVeque 1996, s. 31
  3. ^ Schroeder 2005, s. 21–22
  4. ^ Stark 1978, s. 25
  5. ^ Ore 1948, s. 47–48
  6. ^ LeVeque 1996, s. 33

Litteratur[redigér | redigér wikikode]

Oversættelse
Denne artikel eller en tidligere version er helt eller delvist oversat fra den engelsksprogede Wikipedia, der er tilgængelig under Creative Commons Kreditering-Deling på samme vilkår 3.0. Se versionshistorik for oplysninger om oprindelig(e) bidragyder(e).