Største fælles deler

Den største fælles divisor ( GCD ) for to heltal er den største af deres fælles divisorer [1] . Eksempel: For tallene 54 og 24 er den største fælles divisor 6. $m$ $n$

Den største fælles divisor findes og er entydigt bestemt, hvis mindst et af tallene eller ikke er lig med nul. $m$ $n$

Mulig notation for den største fælles divisor af tal og : $m$ $n$

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

Begrebet største fælles divisor generaliserer naturligvis til sæt på mere end to heltal.

Relaterede definitioner

Mindste fælles multiplum

Det mindste fælles multiplum ( LCM ) af to heltal og er det mindste naturlige tal , der er deleligt med og (uden en rest). Det er betegnet LCM( m , n ) eller , og i engelsk litteratur . $m$ $n$ $m$ $n$ $[m,n]$ ${\mathrm {lcm}}(m,n)$

LCM for ikke-nul tal og eksisterer altid og er relateret til GCM af følgende relation: $m$ $n$

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

Dette er et specialtilfælde af en mere generel sætning: hvis tal, der ikke er nul, er et fælles multiplum af dem, så gælder følgende 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)

Coprime tal

Tal og siges at være coprime , hvis de ikke har andre fælles divisorer end . For sådanne tal gcd . Omvendt, hvis gcd så er tallene coprime. $m$ $n$ $\pm 1$ $(m,n)=1$ $(m,n)=1,$

På samme måde siges heltal , hvor , at være coprime , hvis deres største fælles divisor er en . $a_{1},a_{2},\dots a_{k}$ $k\geq 2$

Man bør skelne mellem begreberne gensidig primalitet, når GCD af et sæt tal er 1, og parvis gensidig primalitet , når GCD er 1 for hvert par tal fra sættet. Gensidig enkelhed følger af parvis enkelhed, men ikke omvendt. For eksempel, gcd(6,10,15) = 1, men eventuelle par fra dette sæt er ikke coprime.

Beregningsmetoder

Effektive måder at beregne gcd af to tal på er Euklid-algoritmen og den binære algoritme .

Derudover kan værdien af gcd( m , n ) let beregnes, hvis den kanoniske dekomponering af tal og til primfaktorer er kendt: $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}}},

hvor er distinkte primtal og og er ikke-negative heltal (de kan være nul, hvis det tilsvarende primtal ikke er i udvidelsen). Så er GCD( n , m ) og LCM[ n , m ] udtrykt med formlerne: $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})}}.

Hvis der er mere end to tal: , findes deres GCD i henhold til følgende algoritme: $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})

- dette er den ønskede GCD.

Egenskaber

Hovedegenskab: den største fælles divisor og er delelig med enhver fælles divisor af disse tal. Eksempel: for tallene 12 og 18 er den største fælles divisor 6; det er deleligt med alle fælles divisorer for disse tal: 1, 2, 3, 6. $m$ $n$
- Følge 1: sæt af fælles divisorer og falder sammen med mængden af divisorer af gcd( m , n ). $m$ $n$
- Følge 2: mængden af fælles multipla og falder sammen med mængden af multipla af LCM( m , n ). $m$ $n$
Hvis er deleligt med , så gcd( m , n ) = n . Især gcd( n , n ) = n . $m$ $n$
$(a,b)=(ab,b)$ . Generelt, hvis , hvor er heltal, så . $a=b*q+c$ $a,b,c,q$ $(a,b)=(b,c)$
$(a\cdot m,a\cdot n)=|a|\cdot (m,n)$ - den fælles faktor kan tages ud af GCD-tegnet.
Hvis , så efter division med tal bliver coprime, det vil sige . Dette betyder især, at for at reducere en brøk til en irreducerbar form, er det nødvendigt at dividere dens tæller og nævner med deres gcd. $D=(m,n)$ $D$ $\venstre({{\frac {m}{D)),{\frac {n}{D))}\right)=1$
Multiplikativitet : hvis coprime, så: $a_{1},a_{2}$

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

Den største fælles divisor af tal og kan defineres som det mindste positive element i mængden af alle deres lineære kombinationer : $m$ $n$

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

og repræsenterer derfor som en lineær kombination af tal og :

(m,n)

m

n

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

. Dette forhold kaldes Bezout-forholdet , og koefficienterne og er Bezout-koefficienterne . Bézout-koefficienter beregnes effektivt af den udvidede Euclid-algoritme . Denne erklæring er generaliseret til sæt af naturlige tal - dens betydning er, at undergruppen af gruppen, der genereres af mængden, er cyklisk og genereres af ét element: gcd ( a 1 , a 2 , … , a n ) .

u

v

\mathbb {Z}

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

Variationer og generaliseringer

Begrebet delelighed af heltal generaliserer naturligvis til vilkårlige kommutative ringe , såsom polynomialringen eller Gaussiske heltal . Det er dog umuligt at definere gcd( a , b ) som den største fælles divisor , fordi i sådanne ringe generelt er ordensrelationen ikke defineret . Derfor, som definitionen af GCD, tages dens hovedegenskab: $-en$ $b$

Den største fælles divisor GCD( a , b ) er den fælles divisor, der er delelig med alle andre fælles divisorer og .

-en

b

For naturlige tal svarer den nye definition til den gamle. For heltal er GCD i den nye betydning ikke længere unik: dets modsatte tal vil også være GCD. For gaussiske tal øges antallet af forskellige gcd'er til 4.

Gcd'en af to elementer i en kommutativ ring behøver generelt ikke at eksistere. For eksempel har følgende elementer og en ring ikke den største fælles divisor: $-en$ $b$ ${\mathbb {Z}}\venstre[{\sqrt {-3}}\højre]$

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 euklidiske ringe eksisterer den største fælles divisor altid og er defineret op til enhedsdelere, det vil sige, at antallet af gcds er lig med antallet af enhedsdelere i ringen .

Se også

Litteratur

Vinogradov I.M. Fundamentals af talteori. M.-L.: Stat. udg. teknisk og teoretisk litteratur, 1952, 180 s.

Noter

↑ Matematisk encyklopædi (i 5 bind) . - M . : Soviet Encyclopedia , 1982. - T. 3. side 857