Grootste gemene deler

De grootste gemene deler, afgekort met g.g.d. (g.c.d. in het Engels wat staat voor greatest common divisor) van een aantal gegeven getallen is het grootste getal waar alle gegeven getallen door gedeeld kunnen worden.

Bijvoorbeeld de grootste gemene deler van 6 en 12 is het getal 6. De grootste gemene deler van 15 en 20 is het getal 5. De grootste gemene deler van 6, 9 en 12 is 3. Grootste gemene deler wordt vaak afgekort tot ggd. Bijvoorbeeld ggd(6, 9, 12) = 3.

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

Het product van de g.g.d. en het kleinste gemene veelvoud van twee getallen is gelijk aan het product van die twee getallen zelf.

Inhoud 1 Bepalen van de grootste gemene deler 2 Toepassing van de grootste gemene deler 3 Eigenschappen van de grootste gemene deler 4 Grootste gemene deler in verschillende getallenverzamelingen

[bewerk] Bepalen van de grootste gemene deler

Bovenstaande voorbeelden zijn eenvoudig, maar bij grotere getallen is het niet direct duidelijk wat de g.g.d. is. De g.g.d. wordt bijvoorbeeld bepaald door beide getallen te ontbinden in factoren. 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 g.g.d.

Een voorbeeld maakt dit duidelijk:

Het getal 24 is deelbaar door de priemgetallen 2, 2, 2, 3 (want 24 is gelijk aan 2 × 2 × 2 × 3)

Het getal 102 is deelbaar door de priemgetallen 2, 3 en 17.

De grootste gemene deler van 24 en 102 is dus 2 × 3 = 6.

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

[bewerk] Toepassing van de grootste gemene deler

Bij het vereenvoudigen van een breuk is het handig om de g.g.d. te bepalen. Het getal boven en onder de breuk kan dan door de g.g.d 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.

[bewerk] Eigenschappen van de grootste gemene deler

Stel dat d de g.g.d. 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 integers x en y. Zie daarvoor het uitgebreide algoritme van Euclides.

[bewerk] Grootste gemene deler in verschillende getallenverzamelingen

Niet enkel van een aantal natuurlijke getallen kan een grootste gemene deler genomen worden, ook van elementen van een hoofdideaaldomein. Dit volgt uit de stelling van Bezout: Zij R een hoofdideaaldomein en veronderstel a₁, ..., a_n elementen uit R. Dan bestaat er een grootste gemene deler d van a₁, ..., a_n. Bovendien bestaan er elementen r₁, ... ,r_n, element van R zodat

d=r₁a₁ + ... + r_na_n

De grootste gemene deler is uniek op eenheden na: als c en d grootste gemene delers zijn van a₁, ..., a_n, dan bestaat er een eenheid e zodat c=de.

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