Største felles skiller

Den største fellesfaktoren ( GCF ) er et matematisk begrep. Motstykket er det minst vanlige multiple (LCM) . Begge spiller en rolle i blant annet brøk og tallteori .

Det er det største naturlige tallet som kan brukes til å dele to hele tall uten en rest .

De to heltallene og er et heltall med egenskapen som de deler både og av, og at ethvert heltall, som også er tallene og deler, i sin tur deler . Med ringen av hele tall (som har en total orden >) normaliserer man det til det største hele slikt tallet . ${\ displaystyle \ operatorname {ggT}}$ ${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle m}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle m}$ ${\ displaystyle \ mathbb {Z}}$${\ displaystyle \ operatorname {ggT}}$${\ displaystyle | m |}$

Uttrykket "stor" korrelerer i høy grad med den vanlige rekkefølge relasjonen > av hele tall. Det er imidlertid ett viktig unntak: Siden flere av noe helt tall er ikke å bli slått i form av “størrelse” når det kommer til deleligheten. Dette synet er i tråd med foreningens forestilling (og idealteori ) og forenkler noen av beregningsreglene som er oppført nedenfor. ${\ displaystyle \ operatorname {ggT}}$${\ displaystyle 0}$ ${\ displaystyle m}$${\ displaystyle 0}$

Det engelske begrepet gcd (største felles divisor) for er også vanlig i matematiske tekster. ${\ displaystyle \ operatorname {ggT}}$

Det brukes også ofte som en stenografi for .${\ displaystyle (a, \, b)}$${\ displaystyle \ operatorname {ggT} (a, b)}$

eksempel

• 12 kan deles med følgende tall uten resten: 1, 2, 3, 4, 6, 12.
• 18 har disse faktorene: 1, 2, 3, 6, 9, 18.
• Så de vanlige faktorene (delere) på 12 og 18 er 1, 2, 3, 6 og den største av disse er 6; i tegn:

${\ displaystyle \ operatorname {gcd} (12.18) = 6}$

beregning

Beregning ved bruk av primfaktorisering

GgT og LCM kan bestemmes av primfaktoriseringen av de to gitte tallene. Eksempel:

• ${\ displaystyle 3528 = 2 ^ {\ farge {rød} 3} \ cdot 3 ^ {\ farge {rød} 2} \ cdot 5 ^ {\ farge {rød} 0} \ cdot 7 ^ {\ farge {rød} 2 }}$
• ${\ displaystyle 3780 = 2 ^ {\ color {OliveGreen} 2} \ cdot 3 ^ {\ color {OliveGreen} 3} \ cdot 5 ^ {\ color {OliveGreen} 1} \ cdot 7 ^ {\ color {OliveGreen} 1 }}$

For GCF tar man de viktigste faktorene som oppstår i både nedbrytninger og, som tilhørende eksponent, de respektive mindre av utgangseksponentene:

• ${\ displaystyle \ operatorname {ggT} (3528,3780) = 2 ^ {\ color {OliveGreen} 2} \ cdot 3 ^ {\ color {Red} 2} \ cdot 5 ^ {\ color {Red} 0} \ cdot 7 ^ {\ color {OliveGreen} 1} = 252}$

Euklidisk og Steins algoritme

Beregningen av primfaktoriseringen av store tall og dermed også bestemmelsen av den største fellesdeleren i henhold til metoden ovenfor er veldig kompleks. Imidlertid er den euklidiske algoritmen en effektiv måte å beregne den største fellesdeleren på to tall. Denne prosedyren ble ytterligere variert av Steins algoritme . Hvorvidt dette er en forbedring avhenger av den respektive evalueringsfunksjonen og "maskineriet" som utfører den respektive algoritmen.

Den klassiske euklidiske algoritmen beregner den største felles divisoren ved å lete etter et vanlig "mål" for lengden på to linjer. For å gjøre dette trekkes den minste av to lengder fra den større, og dette trinnet gjentas med resultatet og den mindre lengden til det subtraherte tallet er identisk med resultatet. Eksempel:

${\ displaystyle {\ begin {align} 143-65 & = 78 \\ 78-65 & = 13 \\ 65-13 & = 52 \\ 52-13 & = 39 \\ 39-13 & = 26 \\ 26 -13 & = 13 \ \\ slutt {justert}}}$

Den største felles divisoren er altså 13. Hvis du vet at 13 er prime, kan du lese av divisoren i eksemplet i andre trinn, siden et primtall ikke kan deles lenger som et resultat.

I den moderne euklidiske algoritmen blir divisjon etter rest utført i påfølgende trinn , mens resten blir den nye deleren i neste trinn. Divisoren som resulterer i resten 0 er den største felles divisoren av de opprinnelige tallene. Eksempel:

${\ displaystyle {\ begin {align} 3780 &: 3528 & = \ & 1 & \ \ operatorname {rest} & \ 252 \\ 3528 &: 252 & = \ & 14 & \ \ operatorname {rest} & \ 0 \ \\ slutt {justert}}}$

Så 252 er den største fellesdeleren i 3780 og 3528.

I C er algoritmen formulert slik:

int GreatestCommonDivisor(int a, int b)
{
    int h;
    if (a == 0) return abs(b);
    if (b == 0) return abs(a);

    do {
        h = a % b;
        a = b;
        b = h;
    } while (b != 0);

    return abs(a);
}

GCF av flere tall

Alle hovedfaktorer som forekommer i hvert av tallene brukes med den minste effekten som oppstår i hvert tilfelle, for eksempel:

${\ displaystyle 144 = 2 ^ {\ farge {rød} 4} \ cdot 3 ^ {\ farge {rød} 2} \ cdot 5 ^ {\ farge {rød} 0} \ cdot 7 ^ {\ farge {rød} 0 }}$

${\ displaystyle 160 = 2 ^ {\ color {OliveGreen} 5} \ cdot 3 ^ {\ color {OliveGreen} 0} \ cdot 5 ^ {\ color {OliveGreen} 1} \ cdot 7 ^ {\ color {OliveGreen} 0 }}$

${\ displaystyle 175 = 2 ^ {\ color {Blue} 0} \ cdot 3 ^ {\ color {Blue} 0} \ cdot 5 ^ {\ color {Blue} 2} \ cdot 7 ^ {\ color {Blue} 1 },}$

så:

${\ displaystyle \ operatorname {ggT} (144,160,175) = 2 ^ {\ color {Blue} 0} \ cdot 3 ^ {\ color {OliveGreen} 0} \ cdot 5 ^ {\ color {Red} 0} \ cdot 7 ^ {\ color {Red} 0} = 1.}$

Man kan også beregne først, og deretter, som en tosifret kombinasjon på de naturlige tallene, er GCF assosiativ : ${\ displaystyle \ operatorname {ggT} (144,160) = 16}$${\ displaystyle \ operatorname {gcd} (16,175) = 1,}$

${\ displaystyle \ operatorname {ggT} (m, \, \ operatorname {ggT} (n, o)) = \ operatorname {ggT} (\ operatorname {ggT} (m, n), \, o).}$

Dette rettferdiggjør stavemåten . ${\ displaystyle \ operatorname {ggT} (m, n, o)}$

Beregningsregler

Følgende gjelder for hele tall - med som mengden av : ${\ displaystyle a, b, c}$${\ displaystyle | a |}$${\ displaystyle a}$

	●	${\ displaystyle \ operatorname {ggT} (a, b)}$	${\ displaystyle = \ operatorname {ggT} (b, a)}$	(Kommutativ lov)
	●	${\ displaystyle \ operatorname {ggT} (\ pm a, \ pm b)}$	${\ displaystyle = \ operatorname {ggT} (a, b)}$
	●	${\ displaystyle \ operatorname {ggT} (a, a)}$	${\ displaystyle = | a |}$
	●	${\ displaystyle \ operatorname {ggT} (a, 0)}$	${\ displaystyle = | a |}$
	●	${\ displaystyle \ operatorname {ggT} (a, 1)}$	${\ displaystyle = 1}$
	●	${\ displaystyle \ operatorname {ggT} (a, b \; {\ bmod {\;}} a)}$	${\ displaystyle = \ operatorname {ggT} (a, b)}$	${\ displaystyle (a \ neq 0)}$
	●	${\ displaystyle \ operatorname {ggT} (a, b + ac)}$	${\ displaystyle = \ operatorname {ggT} (a, b)}$
	●	${\ displaystyle \ operatorname {ggT} (a, b, c)}$	${\ displaystyle = \ operatorname {ggT} (a, \, \ operatorname {ggT} (b, c)) = \ operatorname {ggT} (\ operatorname {ggT} (a, b), \, c)}$	(Associativ lov)
	●	${\ displaystyle \ operatorname {ggT} (a \ cdot c, b \ cdot c)}$	${\ displaystyle = \ operatorname {ggT} (a, b) \ cdot | c |}$	(Distribusjonslov)
	●	Er en felles skiller av og , da:   aksjer     og${\ displaystyle c}$${\ displaystyle a}$${\ displaystyle b}$ ${\ displaystyle c}$${\ displaystyle \ operatorname {ggT} (a, b)}$     ${\ displaystyle \ operatorname {ggT} (a: c, b: c) \, = \ operatorname {ggT} (a, b): | c |}$		Til   ${\ displaystyle c \ neq 0.}$
	●	Er   ( og er kongruent modulo ) da:${\ displaystyle a \ equiv b \ {\ bmod {\}} c}$${\ displaystyle a}$${\ displaystyle b}$ ${\ displaystyle c}$     ${\ displaystyle \ operatorname {ggT} (a, c) \ qquad \; \; \, = \ operatorname {ggT} (b, c)}$

Fra nevnte beregningsregel er det et spesielt resultat . Dette er også et resultat av at hvert heltall (til og med selve 0) er en divisor på 0, mens omvendt 0 ikke deler noe annet tall enn 0. ${\ displaystyle \ operatorname {ggT} (a, 0) = | a |}$${\ displaystyle \ operatorname {gcd} (0,0) = 0}$${\ displaystyle a}$${\ displaystyle a \ cdot 0 = 0}$

Hvis du beholder ett av de to argumentene, er det en multiplikasjonsfunksjon , for for coprime- tall og følgende gjelder: ${\ displaystyle \ operatorname {ggT}}$${\ displaystyle a}$${\ displaystyle b}$

${\ displaystyle \ operatorname {ggT} (ab, c) = \ operatorname {ggT} (a, c) \ cdot \ operatorname {ggT} (b, c)}$

Lemma fra Bezout

Etter Lemma Bézout kan den største fellesdeleren av to heltall og som en lineær kombinasjon av og representere med heltallskoeffisienter: ${\ displaystyle m}$${\ displaystyle n}$${\ displaystyle m}$${\ displaystyle n}$

• ${\ displaystyle \ operatorname {ggT} (m, n) = s \ cdot m + t \ cdot n}$ Med ${\ displaystyle s, t \ in \ mathbb {Z}}$

For eksempel, den største vanlige faktoren for og har følgende representasjon: ${\ displaystyle 12}$${\ displaystyle 18}$

• ${\ displaystyle \ operatorname {gcd} (12.18) = 6 = (- 1) \ times 12 + 1 \ times 18}$

Koeffisientene og kan beregnes ved hjelp av den utvidede euklidiske algoritmen . ${\ displaystyle s}$${\ displaystyle t}$

spesielle tilfeller

Følgende gjelder jevn , odde og hel : ${\ displaystyle e}$${\ displaystyle d}$${\ displaystyle i, j, k}$

${\ displaystyle \ operatorname {ggT} (2e, e ^ {2} -1) = 1}$;

${\ displaystyle \ operatorname {ggT} (2d, d ^ {2} -1) = 2}$;

${\ displaystyle \ operatorname {ggT} (2k (k + 1), 2k + 1) = 1}$;

${\ displaystyle \ operatorname {ggT} (4k, 4k ^ {2} -1) = 1}$;

${\ displaystyle \ operatorname {ggT} (ij, 1 + i + j) = \ operatorname {ggT} (1 + 2j, 1 + 2i)}$;

${\ displaystyle \ operatorname {ggT} (a, b) = 2 \ operatorname {ggT} (a / 2, b / 2)}$hvis a og b er jevne.

${\ displaystyle \ operatorname {ggT} (a, b) = \ operatorname {ggT} (a / 2, b)}$hvis a er jevn og b er merkelig.

${\ displaystyle \ operatorname {ggT} (a, b) = \ operatorname {ggT} ((ab) / 2, b)}$hvis a og b er rare.

Hvis du setter et primtall sammen fra to virkelige summander, gjelder alltid coprime-tall for dem:

${\ displaystyle p = a + b; 0 <b \ leq a <p; a, b \ in \ mathbb {N}, p ​​\ in \ mathbb {P}; ggT (a, b) = 1}$.

applikasjoner

Brøker

Ved avkutting av en brøk , blir en felles faktor fjernet fra telleren og nevneren for en brøk, hvorved verdien av brøken ikke endres, f.eks. B .. Hvis du forkorter med den største fellesdeleren til teller og nevner, resulterer en brøk som ikke kan reduseres ytterligere. For eksempel er det slik ${\ displaystyle {\ tfrac {12} {18}} = {\ tfrac {6 \ cdot 2} {9 \ cdot 2}} = {\ tfrac {6} {9}}}$${\ displaystyle \ operatorname {ggT} (12,18) = {\ color {Blue} 6}}$

${\ displaystyle {\ frac {12} {18}} = {\ frac {2 \ cdot {\ color {Blue} 6}} {3 \ cdot {\ color {Blue} 6}}} = {\ frac {2 } {3}}}$

En brøkdel som ikke kan reduseres ytterligere kalles en redusert brøkdel eller en fullstendig og maksimalt redusert brøkdel .

Forholdet mellom GCD og det minst vanlige multiple

${\ displaystyle \ mathrm {ggT} (a, b) \ cdot \ mathrm {kgV} (a, b) = a \ cdot b}$

Videre algebraiske strukturer med GCD

Konseptet med GC er basert på begrepet delbarhet slik det er definert i ringer. Når man diskuterer GCD, begrenser man seg til null skillelinfrie ringer, i kommutativt tilfelle er dette integritetsringene .

En integritetsring, der to elementer hver har en gcd, kalles en gcd-ring eller gcd-område . (I en GCB-ring har hvert annet element også en LCM.)

Generelt har slike ringer ikke en delvis rekkefølge som er antisymmetrisk , i likhet med hele eller naturlige tall. Delbarhetsrelasjonen, som er en kvasi-orden, er ofte den eneste ordensrelasjonen. Derfor kan ggT være. normaliserer ikke lenger entydig som ikke-negativt, men bestemmer bare opp til tilknytning . To elementer og er assosiert, i tegn , når det er en enhet med . ${\ displaystyle a}$${\ displaystyle b}$${\ displaystyle a \ sim b}$ ${\ displaystyle \ epsilon}$${\ displaystyle a = b \ cdot \ epsilon}$

Vi utvider konseptet med GCD til settet med alle de største vanlige faktorene for elementene i en delmengde av en ring , formelt: ${\ displaystyle M}$${\ displaystyle R}$

${\ displaystyle d \ in \ operatorname {ggT} (M) \ quad: \ Longleftrightarrow \ quad \ forall y \ in R: (\ forall x \ in M: y \ mid x) \ Lefttrightarrow y \ mid d}$.

Med ord: Delene av er nøyaktig elementene som alle elementer fra deler seg fra. GCD er assosiert med hverandre. ${\ displaystyle d}$${\ displaystyle R}$${\ displaystyle M}$

Polynomringer

Du kan bruke gcd z. B. også skjema for polynomer . I stedet for primfaktoriseringen tar man her nedbrytningen til irredusible faktorer:

${\ displaystyle {\ begin {justert} f (X, Y) & = X ^ {2} + 2XY + Y ^ {2} = (X + Y) ^ {2} \\ g (X, Y) & = X ^ {2} -Y ^ {2} = (X + Y) (XY) \ slutt {justert}}}$

Deretter

${\ displaystyle \ operatorname {ggT} (f, g) \ sim X + Y}$

Den polynom ring i en variabel er euklidsk . Det er en divisjon med resten for å beregne . ${\ displaystyle \ mathbb {Q} [X]}$${\ displaystyle X}$${\ displaystyle \ operatorname {ggT}}$

Gaussisk nummerring

I den gaussiske nummerringen er den største fellesdeleren av og er jevn , fordi og . Strengt tatt er det bare en største felles faktor, siden alle tallene knyttet til dette tallet også er de største vanlige faktorene. (Enhetene er .) ${\ displaystyle \ mathbb {Z} + \ mathrm {i} \ mathbb {Z}}$${\ displaystyle 2}$${\ displaystyle 1 + 3 \ mathrm {i}}$${\ displaystyle 1+ \ mathrm {i}}$${\ displaystyle 2 = - \ mathrm {i} (1+ \ mathrm {i}) ^ {2}}$${\ displaystyle 1 + 3 \ mathrm {i} = (1+ \ mathrm {i}) (2+ \ mathrm {i})}$${\ displaystyle 1+ \ mathrm {i}}$${\ displaystyle \ pm 1, \ pm \ mathrm {i}}$

Integritet ringer

I integritetsringen har elementene det ${\ displaystyle R = \ mathbb {Z} [{\ sqrt {-3}}]}$

${\ displaystyle a: = 4 = 2 \ cdot 2 = (1 + {\ sqrt {-3}}) (1 - {\ sqrt {-3}}), \ quad b: = (1 + {\ sqrt { -3}}) \ cdot 2}$

ingen gcd: elementene og er to maksimale vanlige faktorer , fordi begge har samme mengde , men disse to elementene er ikke forbundet med hverandre. Så det er ingen GCF av og . ${\ displaystyle 1 + {\ sqrt {-3}}}$${\ displaystyle 2}$${\ displaystyle a}$${\ displaystyle b}$

Elementene nevnt og har sin egen GCT, nemlig . Derimot har de ingen LCM, for hvis en LCM følger av "GCD LCM-ligningen" som til tilhørende trenger å være. Det vanlige multiple er imidlertid ikke et multiplum av , så det er ingen LCM, og de to elementene har ikke LCM i det hele tatt. ${\ displaystyle 1 + {\ sqrt {-3}}}$${\ displaystyle 2}$${\ displaystyle 1}$${\ displaystyle v}$${\ displaystyle v}$${\ displaystyle k: = (1 + {\ sqrt {-3}}) \ cdot 2}$${\ displaystyle 4}$${\ displaystyle k}$${\ displaystyle k}$

Er en integritetsring og elementene og har en LCM, så har de også en GCF, og ligningen gjelder ${\ displaystyle R}$${\ displaystyle a}$${\ displaystyle b}$

${\ displaystyle a \ cdot b \ sim \ operatorname {ggT} (a, b) \ cdot \ operatorname {kgV} (a, b)}$

En euklidisk ring er en hovedidealring som er en faktorring som til slutt er en GCF-ring. På samme måte er hver viktigste ideelle ring en bezoutring , som igjen alltid er en gcd-ring.

Et eksempel på en ikke-kommutativ ring GCD er Hurwitzquaternionen .

Analytisk tallteori

I elementær tallteori er den største fellesdeleren av to hele tall et av de viktigste grunnleggende begrepene. Du skriver der regelmessig og mener positiv GCD, så du antar . ${\ displaystyle g}$${\ displaystyle m, n \ in \ mathbb {Z} \ setminus \ lbrace 0 \ rbrace}$${\ displaystyle g = (m, n)}$${\ displaystyle g \ in \ mathbb {N}}$

I analytisk tallteori kan gcd-funksjonen fortsettes analytisk i en variabel for en hel funksjon . → Se Ramanujan sum . ${\ displaystyle \ mathbb {Z} \ setminus \ lbrace 0 \ rbrace \ rightarrow \ mathbb {N}; \; m \ mapsto (m, n)}$${\ displaystyle n \ in \ mathbb {N} \ setminus \ lbrace 0 \ rbrace}$

Individuelle bevis

1. Bund Peter Bundschuh: Introduksjon til tallteori . 6. utgave. Springer, Berlin 2008, ISBN 978-3-540-76490-8 , s.15 .

litteratur

• Peter Bundschuh : Introduksjon til tallteori . 6. utgave. Springer, Berlin 2008, ISBN 978-3-540-76490-8 .
• Ulm University: "Elementary Number Theory" [1]

weblenker

• Ulike online verktøy for primfaktorisering, GCF og LCM.
• Forelesningsnotater: (PDF; 1,2 MB) Analytisk videreføring av GCD til en hel funksjon.
• Christian Spannagel : Den euklidiske algoritmen . Forelesningsserie, 2012.
• Christian Spannagel : Den største fellesfaktoren og den minst vanlige multiple . Forelesningsserie, 2012.