Grootste gemene deler

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

De grootste gemene deler, afgekort tot ggd, van een aantal gehele getallen (waarvan er ten minste één 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}(\dots).

Voorbeelden[bewerken]

  • 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
\mathrm{ggd}(15, 20) = 5
  • De grootste gemene deler van 6, 9 en 12 is 3; notatie
\mathrm{ggd}(6, 9, 12) = 3

Bepaling[bewerken]

Bovenstaande voorbeelden zijn eenvoudig, maar bij grotere getallen is het niet direct duidelijk wat de ggd is. De ggd wordt bijvoorbeeld bepaald 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 2 of meerdere malen door hetzelfde priemgetal deelbaar is wordt dit 2 of meerdere malen genoteerd.

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

Het getal 24 is deelbaar door de priemgetallen 2 en 3 want 24 is gelijk aan 2 × 2 × 2 × 3.
Het getal 204 is deelbaar door de priemgetallen 2, 3 en 17. En 204 = 2 x 2 x 3 x 17.
De grootste gemene deler van 24 en 204 is dus 2 x 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[bewerken]

Bij het vereenvoudigen van een breuk is het handig om de ggd te bepalen. Het getal boven en onder de breuk (respectievelijk de teller en de noemer) kan dan door de ggd worden gedeeld en zo verkrijgt men direct de grootst mogelijke vereenvoudiging. De breuk 24/102 wordt aldus vereenvoudigd tot 4/17. (Een breuk van twee relatief prieme getallen kan niet vereenvoudigd worden.)

Bijvoorbeeld: vereenvoudig 75/105:

75 = 3x5x5
105 = 3x5x7

Wat hebben ze gemeen? De ggd is 3x5 = 15.

Vereenvoudiging:

\frac{75}{105} = \frac{5\times 15}{7\times 15} =\frac 57

Eigenschappen[bewerken]

Stel dat d de ggd is van a en b. Nu kunnen we over d twee dingen zeggen:

  1. Iedere gemene deler van a en b is tegelijkertijd ook een deler van d.
  2. d is het kleinste positieve getal dat uitgedrukt kan worden als xa+yb voor zekere gehele getallen x en y. Zie daarvoor het uitgebreide algoritme van Euclides.

Relatief priem[bewerken]

Een paar getallen waarvan de ggd gelijk is aan 1 wordt relatief priem genoemd.

Product ggd en kgv van twee getallen gelijk aan product[bewerken]

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

\mathrm{ggd}(15,20) \times \mathrm{kgv}(15,20) = 5 \times 60 = 300 = 15 \times 20 .

Grootste gemene deler in verschillende getallenverzamelingen[bewerken]

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, \dots , a_n elementen uit R. Dan bestaat er een grootste gemene deler d van a_1, \dots , a_n. Bovendien bestaan er elementen r_1, \dots , r_n uit R zodat

d=r_1a_1+\dots + r_na_n.

De grootste gemene deler is uniek op eenheden na: als c en d grootste gemene delers zijn van a_1, \dots , 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.

Voorbeelden[bewerken]

  • De ggd van twee gehele getallen kan volgens bovengenoemde stelling geschreven worden als geheeltallige lineaire combinatie van de beide getallen. Zo geldt voor de getallen 75 en 105;
\operatorname{ggd}(75,105)=15 =3\times 75 - 2\times 105
Omdat 7\times 75 -5\times 105=0,
zijn er ook andere combinaties mogelijk, bijvoorbeeld:
15 =10\times 75 - 7\times 105=-4\times 75+3\times 105
  • De generalisatie behelst de ggd van meer dan twee getallen. Voor de getallen 18, 60 en 72 geldt:
\operatorname{ggd}(18,60,72)= 6 =18 + 60 - 72=3\times 18+4\times 60-4\times 72 .