Största gemensamma delare

Från Wikipedia
Hoppa till: navigering, sök

Inom matematiken är den största gemensamma delaren (förkortat SGD) av två eller flera heltal vilka inte alla är noll det "största" heltal som delar alla talen.

Största gemensamma delaren av a och b skrivs ofta SGD(a, b) eller i talteoretisk litteratur endast (a, b). Till exempel, SGD(12,18) = 6 (eftersom 6 * 2 = 12 & 6 * 3 = 18), SGD(-4,14) = 2 (eftersom 2 * -2 = -4 & 2 * 7 = 14) och SGD(5,0) = 5 (eftersom 5 * 1 = 5 & 5 * 0 = 0). Största gemensamma delaren av 0 och 0 definieras vanligtvis att vara 0. (Visserligen är alla heltal gemensamma delare till 0 och 0, men av dessa räknas 0 som "störst i delbarhetsmening", därför att övriga heltal är äkta delare till 0.) Två tal kallas relativt prima om deras största gemensamma delare är 1. Till exempel är 9 och 28 relativt prima.

Den största gemensamma delaren är användbar för att skriva bråk i enklaste form. Till exempel

42/56 = 3/4

där vi har förkortat med 14, den största gemensamma delaren för 42 och 56.

Se även minsta gemensamma nämnare.

Algoritmer för att beräkna den största gemensamma delaren[redigera | redigera wikitext]

Den största gemensamma delaren kan i princip beräknas genom att ta reda på primtalsfaktoriseringen av de två talen och jämföra faktorerna. Detta sätt används dock inte i praktiken eftersom det är för tidskrävande. En mycket mer effektiv metod är Euklides algoritm.

Andra metoder[redigera | redigera wikitext]

Keith Slavin har bevisat att för udda a ≥ 1 är

\gcd(a,b)=\log_2\prod_{k=0}^{a-1} (1+e^{-2i\pi k b/a})

som är en funktion som även kan räknas för komplexa b. Wolfgang Schramm har visat att

\gcd(a,b)=\sum\limits_{k=1}^a \exp (2\pi ikb/a) \cdot \sum\limits_{d\left| a\right.} \frac{c_d (k)}{d}

där cd(k) är Ramanujans summa. Donald Knuth har bevisat följande:

\gcd(2^a-1, 2^b-1)=2^{\gcd(a,b)}-1

för alla icke-negativa heltal a och b, där a och b inte samtidigt noll. Mer allmänt är

\gcd(n^a-1,n^b-1)=n^{\gcd(a,b)}-1 \,

En användbar relation med Eulers fi-funktion är

 \gcd(a,b) = \sum_{k|a \; \hbox{och} \; k|b} \varphi(k).



Egenskaper[redigera | redigera wikitext]

Varje gemensam delare till a och b delar SGD(a, b)

Största gemensamma delaren till tre tal kan beräknas som SGD(a,b,c) = SGD(SGD(a,b),c) = SGD(a, SGD(b, c)).

Venn A intersect B.svg Matematikportalen – portalen för matematik på svenskspråkiga Wikipedia.