Grootste gemene deler

De grootste gemene deler of grootste gemeenschappelijke deler, afgekort tot ggd, van een aantal gehele getallen, waarvan er ten minste een ongelijk is aan 0, is het grootste positieve gehele getal, waar al deze gehele getallen door gedeeld kunnen worden zonder dat er een rest overblijft. De grootste gemene deler van de getallen 8 en 12 is bijvoorbeeld 4. De grootste gemene deler wordt wel genoteerd als de functie $\operatorname {ggd}$, bijvoorbeeld $\operatorname {ggd} \left(8,12\right)=4$. Gemeen is een oud woord voor gemeenschappelijk.

Twee of meer getallen waarvan de ggd gelijk is aan 1 worden relatief priem of onderling ondeelbaar genoemd.

Voorbeelden

• De grootste gemene deler van 6 en 12 is het getal 6.

6 is het grootste gehele getal waardoor 6 en 12 gedeeld kunnen worden.

• De grootste gemene deler van 15 en 20 is het getal 5; notatie

$\operatorname {ggd} (15,20)=5$

• De grootste gemene deler van 6, 9 en 12 is 3; notatie

$\operatorname {ggd} (6,9,12)=3$

Berekening

Bovenstaande voorbeelden zijn eenvoudig, maar bij grotere getallen is het niet direct duidelijk wat de ggd is. De ggd wordt bijvoorbeeld berekend door beide getallen te ontbinden in priemfactoren. Dat wil zeggen dat van beide getallen wordt bepaald door welke priemgetallen ze deelbaar zijn. Daarbij wordt achtereenvolgens van elk priemgetal geprobeerd of dit een deler is. Als een getal een paar keer door hetzelfde priemgetal kan worden gedeeld, wordt dit ook zoveel keer genoteerd.

Vervolgens worden alle gemeenschappelijke priemfactoren met elkaar vermenigvuldigd. Het resultaat is de ggd. Een voorbeeld maakt dit duidelijk:

Het getal 24 kan door de priemgetallen 2 en 3 worden gedeeld, want 24 is gelijk aan 2 × 2 × 2 × 3.

Het getal 204 kan door de priemgetallen 2, 3 en 17 worden gedeeld, en wel is 204 = 2 × 2 × 3 × 17.

De grootste gemene deler van 24 en 204 is dus 2 × 2 × 3 = 12.

Een efficiënt algoritme (rekenmethode) voor het bepalen van de ggd is het algoritme van Euclides. Voor grote getallen is dit algoritme te verkiezen boven de methode met het ontbinden in factoren. Het is namelijk heel lastig, zelfs voor computers, om een groot getal in factoren te ontbinden als die factoren zelf ook grote getallen zijn.

Gebruik

Bij het vereenvoudigen van een breuk is het handig om de ggd van de teller en de noemer te bepalen. Zowel teller als noemer kunnen dan door hun ggd worden gedeeld en zo verkrijgt men direct de grootst mogelijke vereenvoudiging. De breuk 24/204 wordt zo vereenvoudigd tot (24/12)/(204/12) = 2/17. Een breuk van twee getallen die relatief priem zijn, kan niet vereenvoudigd worden.

Voorbeeld

Vereenvoudig 75/105.

75 = 3x5x5

105 = 3x5x7

De ggd van 75 en 105 is dus 3x5 = 15.

Vereenvoudiging:

${\frac {75}{105}}={\frac {75/15}{105/15}}={\frac {5}{7}}$

Eigenschappen

• Voor ieder getal $c$, zodat zowel $a$ als $b$ door $c$ kunnen worden gedeeld, geldt dat ook $\operatorname {ggd} (a,b)$ door $c$ kan worden gedeeld. Er zijn verschillende regels om het berekenen van een gegeven $\operatorname {ggd}$ te vereenvoudigen.
• $\operatorname {ggd} (a,b)$ is volgens de stelling van Bachet-Bézout het kleinste positieve getal dat uitgedrukt kan worden als $xa+yb$ voor zekere gehele getallen $x$ en $y$. $x$ en $y$ kunnen met het uitgebreide algoritme van Euclides worden berekend.

$\operatorname {ggd} (75,105)=15=3\times 75-2\times 105$

De stelling geldt zelfs voor de ggd van meer dan twee getallen:

$\operatorname {ggd} (18,60,72)=6=18+60-72=3\times 18+4\times 60-4\times 72$

• Het product van de ggd en het kleinste gemene veelvoud van twee positieve gehele getallen is gelijk aan het product van die twee gehele getallen zelf. Zo geldt voor de getallen 15 en 20:

$\operatorname {ggd} (15,20)\times \operatorname {kgv} (15,20)=5\times 60=300=15\times 20$

• Voor drie getallen $a$, $b$ en $c$ geldt dat $\operatorname {ggd} (a,c)=1\land \operatorname {ggd} (b,c)=1\Leftrightarrow \operatorname {ggd} (ab,c)=1$.

Grootste gemene deler in verschillende getallenverzamelingen

Niet alleen van een aantal natuurlijke getallen kan een grootste gemene deler bepaald worden, ook van elementen van een hoofdideaaldomein. Dit volgt uit de nu volgende generalisatie van de stelling van Bachet-Bézout.

Zij $R$ een hoofdideaaldomein en $a_{1},\ldots ,a_{n}$ elementen uit $R$. Dan bestaat er een grootste gemene deler $d$ van $a_{1},\ldots ,a_{n}$. Bovendien bestaan er elementen $r_{1},\ldots ,r_{n}$ uit $R$ zodat

$d=r_{1}a_{1}+\ldots +r_{n}a_{n}$

De grootste gemene deler is uniek op eenheden na: als $c$ en $d$ grootste gemene delers zijn van $a_{1},\ldots ,a_{n}$, dan bestaat er een eenheid $e$ zodat $c=de$.

In een uniek factorisatiedomein kan men ook een grootste gemene deler bepalen met de hierboven vermelde methode van het ontbinden in factoren.

Voetnoten