Wat is de grootste gemene deler (GGD)?
De grootste gemene deler (GGD), in het Engels Greatest Common Divisor of Greatest Common Factor (GCD/GCF), is het grootste positieve gehele getal dat twee of meer gehele getallen deelt zonder rest. Bijvoorbeeld: ggd(12, 18) = 6, omdat 6 zowel 12 als 18 deelt en geen groter getal die eigenschap heeft. Let op: in Nederland is GGD ook de afkorting voor Gemeentelijke Gezondheidsdienst — in de wiskunde verwijst GGD altijd naar de grootste gemene deler.
De GGD speelt een centrale rol in de getaltheorie en wordt in het Nederlandse wiskundeonderwijs op de HAVO en het VWO behandeld bij het onderwerp 'gehele getallen en delers' (Wiskunde A/B/C in de tweede fase, conform de syllabi van het College voor Toetsen en Examens via Examenblad). De begrippen 'deler', 'priemgetal' en 'priemontbinding' vormen de basis voor het later kunnen redeneren over modulair rekenen en cryptografie.
Er zijn drie standaardmethoden om de GGD te bepalen: alle delers opsommen (geschikt voor kleine getallen), priemfactorontbinding (inzichtelijk maar traag voor grote getallen) en het algoritme van Euclides (verreweg het snelst, met logaritmische looptijd O(log min(a,b))).
Het algoritme van Euclides
Het algoritme van Euclides — beschreven rond 300 v.Chr. in Boek VII van de Elementen van Euclides en bestudeerd aan het Mathematisch Instituut van de Universiteit Leiden in colleges over discrete wiskunde — vervangt het paar (a, b) herhaaldelijk door (b, a mod b) tot de rest nul is. De laatste niet-nul rest is de GGD.
Voorbeeld: ggd(252, 105). Stap 1: 252 mod 105 = 42, dus ggd(252, 105) = ggd(105, 42). Stap 2: 105 mod 42 = 21, dus ggd(105, 42) = ggd(42, 21). Stap 3: 42 mod 21 = 0, dus ggd(42, 21) = 21. Resultaat: ggd(252, 105) = 21.
Het uitgebreide algoritme van Euclides berekent bovendien gehele coefficienten x en y zodat ax + by = ggd(a, b). Deze identiteit van Bezout is essentieel voor het bepalen van modulaire inversen, en daarmee voor de sleutelgeneratie in RSA-cryptografie.
Methoden om de GGD te vinden
📝Delers opsommen
Maak een lijst van alle delers van elk getal en kies de grootste gemeenschappelijke deler.
🔢Priemfactorontbinding
Ontbind elk getal in priemfactoren en vermenigvuldig de gemeenschappelijke priemmachten met de laagste exponent.
⚡Algoritme van Euclides
Pas herhaaldelijk ggd(a,b) = ggd(b, a mod b) toe tot de rest 0 is — snelst voor grote getallen.
🔗Uitgebreid Euclides
Berekent tevens gehele x, y met ax + by = ggd(a, b) — onmisbaar voor modulaire inversen in RSA.
GGD, KGV en het vereenvoudigen van breuken
Tussen de grootste gemene deler en het kleinste gemene veelvoud (KGV, in het Engels Least Common Multiple) bestaat voor twee positieve gehele getallen a en b de identiteit: ggd(a, b) x kgv(a, b) = a x b. Hieruit volgt dat kgv(a, b) = (a x b) / ggd(a, b), wat het KGV snel berekenbaar maakt zodra de GGD bekend is.
In het Nederlandse rekenonderwijs op de basisschool en in de onderbouw van HAVO/VWO wordt de GGD vooral gebruikt om breuken te vereenvoudigen tot hun eenvoudigste vorm. Voorbeeld: 36/48 vereenvoudigen. ggd(36, 48) = 12, dus 36/48 = (36/12) / (48/12) = 3/4. Een breuk waarvan teller en noemer copriem zijn (ggd = 1) is per definitie al in eenvoudigste vorm.
Bij optellen en aftrekken van breuken is het KGV juist nuttig om een gemeenschappelijke noemer te vinden, terwijl de GGD daarna helpt het resultaat weer te vereenvoudigen. Beide begrippen worden zo in samenhang gebruikt.
Toepassing in RSA-cryptografie
In het RSA-cryptosysteem — dat wordt onderwezen in keuzemodules wiskunde D op het VWO en in informatica-opleidingen — wordt de publieke exponent e gekozen zodat ggd(e, phi(n)) = 1, waarbij phi(n) de toetientfunctie van Euler is en n het product van twee grote priemgetallen p en q. Dit garandeert dat e een modulaire inverse d heeft modulo phi(n).
Het uitgebreide algoritme van Euclides berekent vervolgens de privesleutel d zodat e x d is congruent 1 (mod phi(n)). Zonder de GGD-toets en het uitgebreide Euclides-algoritme zou RSA niet werken: het is geen randthema maar de kern van moderne digitale handtekeningen, HTTPS-verbindingen en DigiD-authenticatie.
Veelvoorkomende GGD-waarden
Referentietabel voor veelgevraagde GGD-berekeningen, inclusief gemeenschappelijke delers en bijbehorend KGV:
| Getallen | GGD | Gemeenschappelijke delers | KGV |
|---|
| 12, 18 | 6 | 1, 2, 3, 6 | 36 |
| 24, 36 | 12 | 1, 2, 3, 4, 6, 12 | 72 |
| 15, 25 | 5 | 1, 5 | 75 |
| 48, 60 | 12 | 1, 2, 3, 4, 6, 12 | 240 |
| 100, 75 | 25 | 1, 5, 25 | 300 |
| 8, 12, 20 | 4 | 1, 2, 4 | 120 |
