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 ${\displaystyle n}$ og ${\displaystyle m}$, er det største heltal, som er divisor i både ${\displaystyle n}$ og ${\displaystyle m}$. For eksempel er den 3 den største fælles divisor af 9 og 15. Den største fælles divisor skrives som ${\displaystyle sfd(n,m)}$, eller som ${\displaystyle gcd(n,m)}$ 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 ${\displaystyle n\times m}$, og en hvilken som helst fælles divisor ${\displaystyle c}$ der går op i både ${\displaystyle n}$ og ${\displaystyle m}$. Rektanglets sider kan opdeles i segmenter med længde ${\displaystyle c}$, der deler rektanglet i et gitter af kvadrater med sidelængde ${\displaystyle c\times c}$. Den største fælles divisor ${\displaystyle d}$ er den største værdi af ${\displaystyle c}$ som dette er muligt for. Som illustration kan et rektangulært område af størrelse ${\displaystyle 24\times 60}$ opdeles i et gitter med: ${\displaystyle 1\times 1}$ kvadrater, ${\displaystyle 2\times 2}$ kvadrater, ${\displaystyle 3\times 3}$ kvadrater, ${\displaystyle 4\times 4}$ kvadrater, ${\displaystyle 6\times 6}$ kvadrater, eller ${\displaystyle 12\times 12}$ kvadrater. Derfor er 12 den største fælles divisor af 24 og 60. Når et ${\displaystyle 24\times 60}$ rektangulært område deles op i ${\displaystyle 12\times 12}$ kvadrater, vil det have to kvadrater langs den ene kant (${\displaystyle 24/12=2}$) og fem kvadrater langs den anden (${\displaystyle 60/12=5}$).

Hvis to naturlige tal ${\displaystyle n}$ og ${\displaystyle m}$ har ${\displaystyle sfd(n,m)=1}$, 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 ${\displaystyle 6=2\times 3}$ og ${\displaystyle 35=5\times 7}$. 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 ${\displaystyle n}$ og ${\displaystyle m}$ være heltal, og ${\displaystyle d=sfd(n,m)}$ væres deres største fælles divisor. Da ${\displaystyle n}$ og ${\displaystyle m}$ begge er multipla af ${\displaystyle d}$, kan vi skrive ${\displaystyle n=ad}$, og ${\displaystyle m=bn}$, hvor ${\displaystyle a}$ og ${\displaystyle b}$ også er heltal. Der er ikke et større tal ${\displaystyle D>d}$, hvor vi kan skrive ${\displaystyle n}$ og ${\displaystyle m}$ på samme form. Heltallene ${\displaystyle a}$ og ${\displaystyle b}$ skal være indbyrdes primiske, primiske, da enhver fælles faktor ellers ville kunne flyttes ud af ${\displaystyle a}$ og ${\displaystyle b}$ for at gøre ${\displaystyle d}$ større. Derfor skal ethvert andet heltal ${\displaystyle c}$ der går op i både ${\displaystyle n}$ og ${\displaystyle m}$, også gå op i ${\displaystyle d}$. Den største fælles divisor ${\displaystyle d}$ af ${\displaystyle n}$ og ${\displaystyle m}$ er den unikke (positive) fælles divisor af ${\displaystyle n}$ og ${\displaystyle m}$ der er deleligt med enhver anden fælles divisor ${\displaystyle c}$. ^[2]

SFD for to tal ${\displaystyle n}$ og ${\displaystyle m}$ 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 ${\displaystyle n}$ og ${\displaystyle m}$.^[3] F.eks. eftersom 1386 kan primtalsopløses til ${\displaystyle 2\times 3\times 3\times 7\times 11}$ og 3213 kan primtalsopløses til ${\displaystyle 3\times 3\times 3\times 7\times \times 17}$, er den største fælles divisor af 1386 og 3213 netop ${\displaystyle 63=3\times 3\times 7}$, 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

${\displaystyle sfd(n,m)=sfd(m,n)}$

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.

${\displaystyle sfd(a,b,c)=sfd(a,sfd(b,c))=sfd(sfd(a,b),c)}$

En anden, men ækvivalent, definition af SFD er nyttig i avanceret matematik, især ringteori.^[6] Den største fælles divisor ${\displaystyle d}$ af to heltal ${\displaystyle n}$ og ${\displaystyle m}$, 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 ${\displaystyle an+bm}$, hvor ${\displaystyle a}$ og ${\displaystyle b}$ er heltal. Mængden med alle lineære kombinationer med heltalskoefficienter af ${\displaystyle n}$ og ${\displaystyle m}$ er den samme som mængden med alle multiplier af ${\displaystyle d}$, dvs. alle tal på formen ${\displaystyle ad}$, hvor ${\displaystyle a}$ er et heltal. I moderne matematisk sprog er det ideal, der genereres af ${\displaystyle a}$ og ${\displaystyle b}$, lig det ideal, der genereres af ${\displaystyle d}$ 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 ${\displaystyle n}$ og ${\displaystyle m}$ også deler den største fælles divisor (fordi divisoren deler begge led i ${\displaystyle an+bm}$).

Anvendelser

Den største fælles divisor kan bl.a. bruges til at forkorte brøker. Hvis ${\displaystyle n}$ og ${\displaystyle m}$ er heltal, og ${\displaystyle d=sfd(n,m)}$, da vil

${\displaystyle {\frac {n}{m}}={\frac {n/d}{m/d}}}$,

hvor både ${\displaystyle n/d}$ og ${\displaystyle m/d}$ også er heltal, fordi ${\displaystyle d}$ 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

• Knuth, D. E. (1997). The Art of Computer Programming, Volume 2: Seminumerical Algorithms (3. udgave). Addison–Wesley. ISBN 0-201-89684-2.
• LeVeque, W. J. (1996) [1977]. Fundamentals of Number Theory. New York: Dover. ISBN 0-486-68906-9.
• Ore, O. (1948). Number Theory and Its History. New York: McGraw–Hill.
• Schroeder, M. (2005). Number Theory in Science and Communication (4. udgave). Springer-Verlag. ISBN 0-387-15800-6.
• Stark, H. (1978). An Introduction to Number Theory. MIT Press. ISBN 0-262-69060-8.
• Stillwell, J. (2003). Elements of Number Theory. New York: Springer-Verlag. ISBN 0-387-95587-9.

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