Största gemensamma delare

Den största gemensamma divisorn ( GCD ) för två heltal är den största av deras gemensamma divisorer [1] . Exempel: För talen 54 och 24 är den största gemensamma delaren 6. $m$ $n$

Den största gemensamma divisorn finns och bestäms unikt om minst ett av talen eller inte är lika med noll. $m$ $n$

Möjlig notation för den största gemensamma delaren av tal och : $m$ $n$

gcd( m , n );
$(m,n)$ ;
$\gcd(m,n)$ (från engelska g retest c ommon d ivisor );
${\mathrm {hcf}}(m,n)$ (från Brit. h ighest c common factor ) .

Begreppet största gemensamma divisor generaliserar naturligtvis till mängder av mer än två heltal.

Relaterade definitioner

Minsta gemensamma multipel

Den minsta gemensamma multipeln ( LCM ) av två heltal och är det minsta naturliga talet som är delbart med och (utan en rest). Det betecknas LCM( m , n ) eller , och i engelsk litteratur . $m$ $n$ $m$ $n$ $[m,n]$ ${\mathrm {lcm}}(m,n)$

LCM för siffror som inte är noll och finns alltid och är relaterad till GCM genom följande relation: $m$ $n$

(m,n)\cdot [m,n]=m\cdot n

Detta är ett specialfall av en mer allmän sats: om det är tal som inte är noll, är någon gemensam multipel av dem, så gäller följande formel: $a_{1},a_{2},\dots ,a_{n}$ $D$

D=[a_{1},a_{2},\dots ,a_{n}]\cdot \left({\frac {D}{a_{1))},{\frac {D}{a_{2 ))),\dots ,{\frac {D}{a_{n}}}\right)

Samprimtal

Tal och sägs vara coprime om de inte har några andra gemensamma divisorer än . För sådana siffror gcd . Omvänt, om gcd är talen coprime. $m$ $n$ $\pm 1$ $(m,n)=1$ $(m,n)=1,$

På samma sätt sägs heltal , där , vara coprime om deras största gemensamma divisor är en . $a_{1},a_{2},\dots a_{k}$ $k\geq 2$

Man bör skilja mellan begreppen ömsesidig primalitet, när GCD för en uppsättning tal är 1, och parvis ömsesidig primalitet , när GCD är 1 för varje par av tal från mängden. Ömsesidig enkelhet följer av parvis enkelhet, men inte vice versa. Till exempel, gcd(6,10,15) = 1, men alla par från denna uppsättning är inte coprime.

Beräkningsmetoder

Effektiva sätt att beräkna gcd för två tal är Euklidalgoritmen och den binära algoritmen .

Dessutom kan värdet av gcd( m , n ) enkelt beräknas om den kanoniska uppdelningen av tal och till primtalsfaktorer är känd: $m$ $n$

n=p_{1}^{{d_{1}}}\cdot \dots \cdot p_{k}^{{d_{k}}},

m=p_{1}^{{e_{1}}}\cdot \dots \cdot p_{k}^{{e_{k}}},

där är distinkta primtal och och är icke-negativa heltal (de kan vara noll om motsvarande primtal inte är i nedbrytningen). Sedan uttrycks GCD( n , m ) och LCM[ n , m ] med formlerna: $p_{1},\dots ,p_{k}$ $d_{1},\dots ,d_{k}$ $e_{1},\dots ,e_{k}$

(n,m)=p_{1}^{{\min(d_{1},e_{1})}}\cdot \dots \cdot p_{k}^{{\min(d_{k},e_ {k})}},

[n,m]=p_{1}^{{\max(d_{1},e_{1})}}\cdot \dots \cdot p_{k}^{{\max(d_{k},e_ {k})}}.

Om det finns fler än två nummer: , hittas deras GCD enligt följande algoritm: $a_{1},a_{2},\dots a_{n}$

d_{2}=(a_{1},a_{2})

d_{3}=(d_{2},a_{3})

………

d_{n}=(d_{{n-1}},a_{n})

- detta är den önskade GCD.

Egenskaper

Huvudegenskap: den största gemensamma divisorn och är delbar med vilken gemensam divisor som helst av dessa tal. Exempel: för talen 12 och 18 är den största gemensamma delaren 6; den är delbar med alla vanliga delare av dessa tal: 1, 2, 3, 6. $m$ $n$
- Resultat 1: uppsättning gemensamma divisorer och sammanfaller med uppsättningen av divisorer för gcd( m , n ). $m$ $n$
- Resultat 2: mängden gemensamma multipler och sammanfaller med mängden multiplar av LCM( m , n ). $m$ $n$
Om är delbart med , då gcd( m , n ) = n . Speciellt gcd( n , n ) = n . $m$ $n$
$(a,b)=(ab,b)$ . I allmänhet, om , var är heltal, då . $a=b*q+c$ $a,b,c,q$ $(a,b)=(b,c)$
$(a\cdot m,a\cdot n)=|a|\cdot (m,n)$ - den gemensamma faktorn kan tas ur GCD-tecknet.
Om , sedan efter division med tal blir coprime, det vill säga . Detta betyder i synnerhet att för att reducera ett bråk till en irreducerbar form, är det nödvändigt att dividera dess täljare och nämnare med deras gcd. $D=(m,n)$ $D$ $\left({{\frac {m}{D)),{\frac {n}{D))}\right)=1$
Multiplikativitet : om coprime, då: $a_{1},a_{2}$

(a_{1}\cdot a_{2},b)=(a_{1},b)\cdot (a_{2},b)

Den största gemensamma delaren av tal och kan definieras som det minsta positiva elementet i mängden av alla deras linjära kombinationer : $m$ $n$

\left\{a\cdot m+b\cdot n\mid a,b\in \mathbb{Z } \right\}

och representerar därför som en linjär kombination av tal och :

(m,n)

m

n

(m,n)=u\cdot m+v\cdot n

. Detta förhållande kallas Bezout-förhållandet , och koefficienterna och är Bezout-koefficienterna . Bézout-koefficienter beräknas effektivt av den utökade Euklidiska algoritmen . Detta uttalande är generaliserat till mängder av naturliga tal - dess betydelse är att undergruppen av gruppen som genereras av mängden är cyklisk och genereras av ett element: gcd ( a 1 , a 2 , … , a n ) .

u

v

\mathbb {Z}

\{a_{1},a_{2},\dots,a_{n}\}

Variationer och generaliseringar

Begreppet delbarhet av heltal generaliserar naturligtvis till godtyckliga kommutativa ringar , såsom polynomringen eller Gaussiska heltal . Det är dock omöjligt att definiera gcd( a , b ) som den största gemensamma divisorn , eftersom i sådana ringar generellt sett är ordningsrelationen inte definierad . Därför, som definitionen av GCD, tas dess huvudsakliga egenskap: $a$ $b$

Den största gemensamma divisorn GCD( a , b ) är den gemensamma divisorn som är delbar med alla andra gemensamma divisorer och .

a

b

För naturliga tal är den nya definitionen likvärdig med den gamla. För heltal är GCD i den nya meningen inte längre unik: dess motsatta nummer kommer också att vara GCD. För Gaussiska tal ökar antalet olika gcd till 4.

Gcd för två element i en kommutativ ring behöver i allmänhet inte existera. Till exempel har följande element och en ring inte en största gemensamma divisor: $a$ $b$ ${\mathbb {Z}}\left[{\sqrt {-3}}\right]$

a=4=2\cdot 2=\left(1+{\sqrt {-3}}\right)\left(1-{\sqrt {-3}}\right),\qquad b=\left(1 +{\sqrt {-3}}\right)\cdot 2.

I euklidiska ringar finns alltid den största gemensamma delaren och definieras upp till enhetsdelare , det vill säga antalet gcds är lika med antalet enhetsdelare i ringen.

Se även

Litteratur

Vinogradov I.M. Fundamentals of Number Theory. M.-L.: Stat. ed. teknisk och teoretisk litteratur, 1952, 180 sid.

Anteckningar

↑ Matematisk uppslagsverk (i 5 volymer) . - M . : Soviet Encyclopedia , 1982. - T. 3. sida 857