Största gemensamma delare

 Den här artikeln behöver källhänvisningar för att kunna verifieras. (2020-06)
Åtgärda genom att lägga till pålitliga källor (gärna som fotnoter). Uppgifter utan källhänvisning kan ifrågasättas och tas bort utan att det behöver diskuteras på diskussionssidan.

Inom matematiken är den största gemensamma delaren (förkortat SGD) av två eller flera heltal vilka alla inte är noll det största heltal som delar alla talen. Största gemensamma delaren av heltalen a och b skrivs ofta SGD(a, b) eller i talteoretisk litteratur endast (a, b)

Enkel beräkningsmetod

Här följer ett exempel på hur största gemensamma delare kan bestämmas för de båda talen 48 och 180. Talen primtalsfaktoriseras enligt:

48 = 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 3 {\displaystyle 48=2\cdot 2\cdot 2\cdot 2\cdot 3}
180 = 2 ⋅ 2 ⋅ 3 ⋅ 3 ⋅ 5 {\displaystyle 180=2\cdot 2\cdot 3\cdot 3\cdot 5}

Ett Venndiagram ritas där vart och ett av talens faktorer utgör en multimängd. I multimängdernas snitt återfinnes de faktorer som de båda talen delar, nämligen två tvåor och en trea:

Den största gemensamma delaren är produkten av elementen i Venndiagrammets snitt:

S G D ( 48 , 180 ) = 2 ⋅ 2 ⋅ 3 = 12 {\displaystyle SGD(48,180)=2\cdot 2\cdot 3=12}

Metoden kan även användas för att bestämma minsta gemensamma multipel, som beräknas genom att multiplicera alla talen i Venndiagramet:

Minsta gemensamma multipel = 2 ⋅ 2 ⋅ 2 ⋅ 2 ⋅ 3 ⋅ 3 ⋅ 5 = 720 {\displaystyle =2\cdot 2\cdot 2\cdot 2\cdot 3\cdot 3\cdot 5=720}

På samma vis är SGD(12,18) = 6 (eftersom 6 × 2 = 12 och 6 × 3 = 18), SGD(-4,14) = 2 (eftersom 2 × -2 = -4 och 2 × 7 = 14) och SGD(5,0) = 5 (eftersom 5 × 1 = 5 och 5 × 0 = 0).

Specialfall

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.

Användningsområde

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, som är den största gemensamma delaren för 42 och 56.

Algoritmer för att beräkna den största gemensamma delaren

Den största gemensamma delaren kan beräknas enligt metoden ovan genom att ta reda på primtalsfaktoriseringen av de två talen och multiplicera snittet av de båda mängderna. 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

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

gcd ( a , b ) = log 2 ⁡ ∏ k = 0 a − 1 ( 1 + e − 2 i π k b / a ) {\displaystyle \gcd(a,b)=\log _{2}\prod _{k=0}^{a-1}(1+e^{-2i\pi kb/a})}

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

gcd ( a , b ) = ∑ k = 1 a exp ⁡ ( 2 π i k b / a ) ⋅ ∑ d | a c d ( k ) d {\displaystyle \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 {\displaystyle \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 {\displaystyle \gcd(n^{a}-1,n^{b}-1)=n^{\gcd(a,b)}-1\,}

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

gcd ( a , b ) = ∑ k | a och k | b φ ( k ) . {\displaystyle \gcd(a,b)=\sum _{k|a\;{\hbox{och}}\;k|b}\varphi (k).}

Egenskaper

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

SGD(a, b)=SGD(a-k×b,b) för alla heltal k.

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

Se även