Største fælles divisor

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

EgenskaberRediger

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

AnvendelserRediger

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åRediger

ReferencerRediger

  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

LitteraturRediger

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