Største fælles divisor

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: 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 indbyrdes primiske med alle andre primtal.

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

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 . 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,  men det kan også beregnes ved gentagne gange at beregne SFD af talpar. F.eks.

 

En anden, men ækvivalent, definition af SFD er nyttig i avanceret matematik, især ringteori. 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 
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å 
 Mindste fælles multiplum

Referencer

Litteratur
 
 
 
 
 
 

Talteori