Grootste gemene deler (ggd) berekenen

Vul 2 of meer gehele getallen in, gescheiden door puntkomma’s (;). Je kunt de ggd van 3 of meer getallen tegelijk bepalen. De priemfactorontbinding van elk getal en de gemeenschappelijke priemfactoren worden er ook bij getoond.

Gehele getallen (gescheiden door puntkomma’s)

Vul alleen gehele getallen van 1 of meer in, gescheiden door puntkomma’s (bijvoorbeeld 12; 18). 0, negatieve getallen en kommagetallen kunnen niet.

Resultaat

Vul links je getallen in, gescheiden door puntkomma’s (;), en klik op “Berekenen”. Het resultaat verschijnt hier.

Inhoudsopgave

[ SLUITEN ]

Wat je op deze pagina kunt doen
Waarvoor is deze berekening handig?
Zo werkt het
Formule
Symbolen en begrippen
- Symbolen
- Begrippen
Handig om vooraf te weten
Berekenen met Excel
Berekenen met Google Spreadsheets
Berekenen met Python
De formule in LaTeX en andere wiskundenotaties (om te kopiëren)
Zo laat je ChatGPT de berekening doen
Kenmerken van DataChef
Gerelateerde functies
Alle rekenmachines van NumberChef

Wat je op deze pagina kunt doen

Vul gehele getallen in, gescheiden door puntkomma’s (;), en je ziet meteen de grootste gemene deler (ggd, internationaal gcd)
Niet alleen 2 getallen: bepaal ook de ggd van 3 of meer getallen tegelijk, zoals “16; 88; 104”
De priemfactorontbinding van elk getal en de priemfactoren die ze gemeen hebben worden ook getoond, zodat je ook leert hoe je het antwoord vindt en controleert
Een heldere uitleg van de formules en formules om te kopiëren voor Excel, Google Spreadsheets en Python vind je ook op deze pagina

Je kunt alleen gehele getallen van 1 of meer (positieve gehele getallen) gebruiken. Deze pagina werkt niet met 0, negatieve getallen of kommagetallen.

Waarvoor is deze berekening handig?

Breuken vereenvoudigen (de bekendste toepassing)

Om \(\frac{12}{18}\) te vereenvoudigen, deel je teller en noemer door hun ggd, 6, en je krijgt in één keer \(\frac{2}{3}\).
In plaats van eerst door 2 te delen, dan door 3 enzovoort, brengt de ggd de breuk meteen naar de eenvoudigste vorm. Van de basisschool tot het dagelijks werk: dit is de meest voorkomende toepassing van de ggd.

Dingen eerlijk verdelen zonder dat er iets over blijft (feestjes en uitdeelcadeautjes)

Je wilt 24 koekjes en 36 pakjes drinken verdelen over zoveel mogelijk gelijke traktatiezakjes, zonder dat er iets overblijft. Het grootste aantal zakjes is \(\gcd(24, 36) = 12\), met in elk zakje 2 koekjes en 3 pakjes drinken.
Prijzenzakjes maken voor een schoolfeest of materiaal in gelijke pakketten verdelen: dit is de standaardberekening om verschillende soorten spullen in gelijke groepen te verdelen.

Tegels leggen en papier snijden (klussen en ontwerp)

Om een vloer van 330 cm bij 450 cm zonder kieren en zonder zagen te betegelen met vierkante tegels, is de grootste tegel die je kunt gebruiken \(\gcd(330, 450) = 30\), dus een vierkante tegel van 30 × 30 cm (11 rijen van 15 tegels).
Een rechthoek verdelen in zo groot mogelijke vierkanten gebruik je bij het betegelen van vloeren en wanden, en bij het zonder verlies knippen van kaartjes van dezelfde grootte uit een groot vel papier.

Tandwielen ontwerpen (machines en klokken)

Als het aantal tanden van twee in elkaar grijpende tandwielen een groot ggd heeft, raken steeds dezelfde tanden elkaar en slijten ze ongelijk. Een basisregel bij het ontwerpen van machines is dus om het aantal tanden zo veel mogelijk relatief priem te kiezen (ggd van 1).
De tandwielen in auto’s en klokken gebruiken dit idee om de ggd klein te houden.

De versleuteling die het internet veilig houdt

RSA-versleuteling, die wordt gebruikt bij online winkelen en internetbankieren, moet tijdens het maken van de sleutels controleren of twee getallen relatief priem zijn, en het algoritme van Euclides doet dat werk.
Een methode voor de ggd van meer dan 2.000 jaar geleden beschermt nu de communicatie over de hele wereld. Het laat zien hoe duurzaam wiskunde kan zijn.

Formule

Met priemfactorontbinding (de basismethode)

Wiskundige notatie (de gebruikelijke schrijfwijze)

\(\gcd(a,\ b)\) \(=\) \(p_1 \times p_2 \times \cdots\)

In woorden (symbolen vervangen door woorden)

② \(\gcd(a, b)\): ggd van \(a\) en \(b\) \(=\) ① product van alle gemeenschappelijke priemfactoren

De formule in woorden

① Schrijf beide getallen als product van priemgetallen en vermenigvuldig alle \(p_1, p_2, \ldots\): gemeenschappelijke priemfactoren

② om de \(\gcd(a, b)\): grootste gemene deler te krijgen

Een eenvoudig voorbeeld

De ggd van 12 en 18 (12 = 2 × 2 × 3 en 18 = 2 × 3 × 3, dus ze hebben één 2 en één 3 gemeen) is

ggd van 12 en 18 \(=\) product van de gemeenschappelijke priemfactoren (2 en 3)

\(12 = 2 \times 2 \times 3,\quad 18 = 2 \times 3 \times 3\)

\(\gcd(12,\ 18) = 2 \times 3 = 6\)

Het belangrijkste idee

De priemfactoren van een geheel getal zijn de priemgetallen die je krijgt als je het ontbindt in een product van alleen priemgetallen. Komt hetzelfde priemgetal in beide getallen meerdere keren voor, dan gebruik je het zo vaak als het voorkomt in het getal waarin het minder vaak zit. Bijvoorbeeld 8 = 2 × 2 × 2 en 12 = 2 × 2 × 3: 2 komt 3 keer voor in 8 en 2 keer in 12, dus ze hebben 2 keer een 2 gemeen. Dus \(\gcd(8, 12) = 2 \times 2 = 4\).

Het algoritme van Euclides (de methode voor grote getallen)

Wiskundige notatie (de gebruikelijke schrijfwijze)

\(\gcd(a,\ b)\) \(=\) \(\gcd(b,\ a \bmod b)\)

In woorden (symbolen vervangen door woorden)

② \(\gcd(a, b)\): ggd van \(a\) en \(b\) \(=\) ① ggd van “het kleinere getal \(b\)” en “de rest van \(a \div b\)”

De formule in woorden

① Deel het grotere getal door het kleinere en vervang het paar door het paar “het kleinere getal \(b\)” en “de rest \(a \bmod b\)”

② en de \(\gcd(a, b)\): grootste gemene deler blijft gelijk. De getallen worden steeds kleiner en als de rest 0 wordt, is het getal waardoor je deelde de ggd

Een eenvoudig voorbeeld

De ggd van 48 en 18 (48 ÷ 18 = 2 rest 12) is

ggd van 48 en 18 \(=\) ggd van “18” en “rest 12”

\(48 = 18 \times 2 + 12\)

\(18 = 12 \times 1 + 6\)

\(12 = 6 \times 2 + 0\)

\(\gcd(48,\ 18) = 6\)

Het belangrijkste idee

Priemfactorontbinding wordt ineens heel lastig als de getallen groter worden (probeer maar eens een getal als 134.221 te ontbinden: het is 79 × 1.699). Met het algoritme van Euclides herhaal je alleen “delen en de rest nemen” en kom je, hoe groot de getallen ook zijn, altijd bij de ggd uit. De methode staat in de “Elementen” van Euclides uit de 3e eeuw v.Chr. en wordt vaak het oudste algoritme ter wereld genoemd.

Ggd van 3 of meer getallen

Wiskundige notatie (de gebruikelijke schrijfwijze)

\(\gcd(a,\ b,\ c)\) \(=\) \(\gcd(\) \(\gcd(a,\ b)\) \(,\) \(c\) \()\)

In woorden (symbolen vervangen door woorden)

③ \(\gcd(a, b, c)\): ggd van de drie getallen \(=\) \(\gcd(\) ① ggd van \(a\) en \(b\), eerst bepaald \(,\) ② \(c\): het overgebleven getal \()\)

De formule in woorden

① Bepaal eerst de \(\gcd(a, b)\): ggd van twee van de getallen

② bepaal dan de ggd van dat resultaat en het \(c\): het overgebleven getal

③ en zo krijg je de \(\gcd(a, b, c)\): ggd van de drie getallen

Een eenvoudig voorbeeld

De ggd van 16, 88 en 104 (eerst is de ggd van 16 en 88 gelijk aan 8) is

ggd van 16, 88 en 104 \(=\) \(\gcd(\) ggd van 16 en 88 (8) \(,\) overgebleven getal (104) \()\)

\(\gcd(16,\ 88) = 8\)

\(\gcd(8,\ 104) = 8\)

\(\gcd(16,\ 88,\ 104) = 8\)

Het belangrijkste idee

Hoeveel gehele getallen je ook hebt: als je de ggd steeds voor twee getallen tegelijk bepaalt, krijg je de ggd van alle getallen. Bij 4 of meer getallen werkt het hetzelfde en de volgorde verandert niets aan het antwoord. De rekenmachine op deze pagina werkt de getallen ook twee tegelijk af, precies zoals in deze formule.

Het verband tussen de ggd en het kgv

Wiskundige notatie (de gebruikelijke schrijfwijze)

\(\gcd(a,\ b)\) \(\times\) \(\mathrm{lcm}(a,\ b)\) \(=\) \(a \times b\)

In woorden (symbolen vervangen door woorden)

① \(\gcd(a, b)\): grootste gemene deler \(\times\) ② \(\mathrm{lcm}(a, b)\): kleinste gemeen veelvoud \(=\) ③ \(a \times b\): product van de twee getallen

De formule in woorden

① Vermenigvuldig de \(\gcd(a, b)\): grootste gemene deler

② met het \(\mathrm{lcm}(a, b)\): kleinste gemeen veelvoud

③ en je krijgt altijd het \(a \times b\): product van de twee getallen

Een eenvoudig voorbeeld

Bij 12 en 18 (ggd 6, kgv 36):

ggd (6) \(\times\) kgv (36) \(=\) product van de twee getallen (12 × 18)

\(6 \times 36 = 216\)

\(12 \times 18 = 216\)

Het belangrijkste idee

Met dit verband kun je, als je de ggd weet, het kgv vinden met \(\mathrm{lcm}(a, b) = a \times b \div \gcd(a, b)\) (bij grote getallen is dit betrouwbaarder dan veelvouden opschrijven). Let op: dit verband geldt zo alleen voor twee getallen. Bij 3 of meer getallen geldt het in het algemeen niet.

De grootste gemene deler is het grootste positieve gehele getal dat alle getallen zonder rest deelt. Bij kleine getallen vermenigvuldig je de priemfactoren die ze gemeen hebben. Bij grote getallen gebruik je het algoritme van Euclides, waarbij je het paar steeds vervangt door de rest.

Symbolen en begrippen

Symbolen

\(\gcd(a, b)\)	ggd van a en b	De grootste gemene deler van \(a\) en \(b\). In Nederlandse schoolboeken schrijf je dit meestal als ggd(a, b); de internationale afkorting gcd komt van “greatest common divisor”. Je ziet ook wel \(\mathrm{GCF}(a, b)\) (greatest common factor): dat is precies hetzelfde.
\(a \bmod b\)	a modulo b	De rest als je \(a\) door \(b\) deelt. (Voorbeeld: \(48 \bmod 18 = 12\), want 48 ÷ 18 = 2 rest 12)
\(\mathrm{lcm}(a, b)\)	kgv van a en b	Het kleinste gemeen veelvoud van \(a\) en \(b\). In Nederlandse schoolboeken schrijf je dit meestal als kgv(a, b); de internationale afkorting lcm komt van “least common multiple”. (Voorbeeld: \(\mathrm{lcm}(12, 18) = 36\))
\(p_1, p_2, \ldots\)	p met index 1, p met index 2, enzovoort	De gemeenschappelijke priemfactoren op volgorde. De kleine getallen rechtsonder (de indices) geven alleen aan dat het de eerste, de tweede enzovoort is. Ze worden niet in de berekening gebruikt.
\(\cdots\)	stippen (beletselteken)	Een teken voor “enzovoort, volgens hetzelfde patroon”. Hier laat het zien dat je de priemfactoren op dezelfde manier met elkaar vermenigvuldigt, hoeveel het er ook zijn.

Begrippen

deler	Een positief geheel getal dat een geheel getal zonder rest deelt. 12 heeft 6 delers: 1, 2, 3, 4, 6 en 12.
gemeenschappelijke deler	Een deler die twee of meer gehele getallen gemeen hebben. De gemeenschappelijke delers van 12 en 18 zijn 1, 2, 3 en 6. Elke gemeenschappelijke deler is een deler van de grootste gemene deler (hier 6).
grootste gemene deler (ggd)	De grootste van de gemeenschappelijke delers. In het Engels heet het de greatest common divisor (gcd) of greatest common factor (gcf); in programmeertalen en op de universiteit zie je meestal gcd. Het is allemaal hetzelfde getal.
priemgetal	Een geheel getal van 2 of meer waarvan de enige delers 1 en het getal zelf zijn: 2, 3, 5, 7, 11, 13, … 1 is geen priemgetal.
ontbinden in priemfactoren	Een geheel getal schrijven als product van alleen priemgetallen. (Voorbeeld: \(12 = 2 \times 2 \times 3\)) Elk priemgetal dat je daarbij gebruikt, heet een priemfactor.
relatief priem	Als de ggd van twee gehele getallen 1 is (hun enige gemeenschappelijke deler is 1). Zoals 17 en 13 hebben ze helemaal geen priemfactoren gemeen. Je zegt ook wel dat ze onderling ondeelbaar zijn.
algoritme van Euclides	Een manier om de ggd te vinden door steeds te herhalen: “deel het grotere getal door het kleinere en vervang het paar door het kleinere getal en de rest”. Op school kom je het vooral in de bovenbouw tegen, en verder bij informatica en getaltheorie. Het is al sinds de oudheid bekend en wordt vaak het oudste algoritme ter wereld genoemd.
kleinste gemeen veelvoud (kgv)	Het kleinste positieve gehele getal dat een veelvoud is van twee of meer gehele getallen. Je gebruikt het om breuken gelijknamig te maken. Bij twee getallen geldt \(\gcd(a, b) \times \mathrm{lcm}(a, b) = a \times b\).

Handig om vooraf te weten

Dit helpt je om de berekening op deze pagina echt te begrijpen, en niet alleen op de knop te drukken.
Kom je er niet uit, dan is het herhalen van deze onderwerpen de snelste weg vooruit.

Tafels van vermenigvuldiging en delen met rest (groep 5-6, 8-10 jaar)	Het verschil kunnen zien tussen “gaat precies op” en “geeft een rest” Een deling met rest kunnen uitrekenen, zoals 48 ÷ 18 = 2 rest 12
Delers en gemeenschappelijke delers (klas 1, 12-13 jaar)	Alle delers van 12 kunnen opschrijven: 1, 2, 3, 4, 6, 12 De delers kunnen vinden die twee getallen gemeen hebben (gemeenschappelijke delers)
Breuken vereenvoudigen (groep 6-7, 9-11 jaar)	Weten dat de waarde van een breuk niet verandert als je teller en noemer door hetzelfde getal deelt
Priemgetallen en ontbinden in priemfactoren (klas 1-2, 12-14 jaar)	Priemgetallen kunnen herkennen (getallen zonder andere delers dan 1 en het getal zelf) Een geheel getal kunnen opsplitsen in een product van priemgetallen, zoals \(12 = 2 \times 2 \times 3\)

Berekenen met Excel

Kopieer de hele tabel hieronder en plak die in cel A1 van Excel. Het werkt direct.

Tabel om de ggd van twee getallen te berekenen

Eerste getal a	12
Tweede getal b	18
Ggd(a; b)	=GGD(B1;B2)

Tabel om de ggd van 3 of meer getallen te berekenen

Getal 1	16
Getal 2	88
Getal 3	104
Ggd	=GGD(B1:B3)

Tabel om het algoritme van Euclides te controleren

Groter getal a	48
Kleiner getal b	18
Rest van a ÷ b (a mod b)	=REST(B1;B2)
ggd(a; b)	=GGD(B1;B2)
ggd(b; rest) (hetzelfde als hierboven)	=GGD(B2;B3)

Tabel om te controleren dat ggd × kgv = product van de twee getallen

Eerste getal a	12
Tweede getal b	18
Ggd(a; b)	=GGD(B1;B2)
Kgv(a; b)	=KGV(B1;B2)
ggd × kgv	=B3*B4
a × b (hetzelfde als hierboven)	=B1*B2

Excel heeft een ingebouwde functie GGD voor de grootste gemene deler. “=GGD(B1;B2)” geeft de ggd van de waarden in B1 en B2, dus de eerste tabel toont 6 in B3.
Met een bereik, zoals “=GGD(B1:B3)” in de tweede tabel, vind je de ggd van 3 of meer getallen tegelijk (B4 toont 8).
De derde tabel controleert het algoritme van Euclides. Met de functie REST (de rest van een deling) kun je zien dat ggd(a; b) en ggd(b; rest) dezelfde waarde hebben (beide 6).
In de vierde tabel komen ggd × kgv en a × b allebei uit op 216, wat het verband met het kgv bevestigt. Vervang de ingevulde getallen gewoon door je eigen getallen.

Berekenen met Google Spreadsheets

Kopieer de hele tabel hieronder en plak die in cel A1 van Google Spreadsheets. Het werkt direct.

Tabel om de ggd van twee getallen te berekenen

Eerste getal a	12
Tweede getal b	18
Ggd(a; b)	=GGD(B1;B2)

Tabel om de ggd van 3 of meer getallen te berekenen

Getal 1	16
Getal 2	88
Getal 3	104
Ggd	=GGD(B1:B3)

Tabel om het algoritme van Euclides te controleren

Groter getal a	48
Kleiner getal b	18
Rest van a ÷ b (a mod b)	=REST(B1;B2)
ggd(a; b)	=GGD(B1;B2)
ggd(b; rest) (hetzelfde als hierboven)	=GGD(B2;B3)

Tabel om te controleren dat ggd × kgv = product van de twee getallen

Eerste getal a	12
Tweede getal b	18
Ggd(a; b)	=GGD(B1;B2)
Kgv(a; b)	=KGV(B1;B2)
ggd × kgv	=B3*B4
a × b (hetzelfde als hierboven)	=B1*B2

Google Spreadsheets heeft de functies GGD, KGV en REST met dezelfde namen als Excel (in de Nederlandse versie), dus dezelfde formules werken ook daar.
Kopieer de hele tabel, plak die in cel A1 en vervang de ingevulde getallen door je eigen getallen.

Berekenen met Python

from math import gcd
from functools import reduce

numbers = [330, 75, 450, 225]  # gehele getallen waarvan je de ggd zoekt (willekeurig veel)

greatest_common_divisor = reduce(gcd, numbers)  # past gcd steeds op twee getallen tegelijk toe, vanaf het begin

print(f"ggd van {numbers}: {greatest_common_divisor}")

Werkt met alleen de standaardbibliotheek. math.gcd vindt de ggd van twee gehele getallen en reduce regelt het deel “steeds twee tegelijk”. Vervang de lijst bovenaan door je eigen getallen en voer de code uit (dit voorbeeld geeft 15).

De formule in LaTeX en andere wiskundenotaties (om te kopiëren)

Met priemfactorontbinding (de basismethode)

gcd(a, b) = p₁ × p₂ × ⋯

\gcd(a, b) = p_1 \times p_2 \times \cdots

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>gcd</mi>
    <mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
    <mo>=</mo>
    <msub><mi>p</mi><mn>1</mn></msub>
    <mo>&#xD7;</mo>
    <msub><mi>p</mi><mn>2</mn></msub>
    <mo>&#xD7;</mo>
    <mo>&#x22EF;</mo>
  </mrow>
</math>

gcd(a, b) = p_1 xx p_2 xx cdots

GCD[a, b]

igcd(a, b);

g = gcd(a, b);

gcd(a, b) = p_1 × p_2 × ⋯

Het algoritme van Euclides (de methode voor grote getallen)

gcd(a, b) = gcd(b, a mod b)

\gcd(a, b) = \gcd(b,\ a \bmod b)

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>gcd</mi>
    <mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
    <mo>=</mo>
    <mi>gcd</mi>
    <mo>(</mo><mi>b</mi><mo>,</mo>
    <mi>a</mi><mspace width="0.3em"/><mi>mod</mi><mspace width="0.3em"/><mi>b</mi>
    <mo>)</mo>
  </mrow>
</math>

gcd(a, b) = gcd(b, a mod b)

GCD[a, b] == GCD[b, Mod[a, b]]

igcd(a, b) = igcd(b, a mod b);

gcd(a, b) == gcd(b, mod(a, b))

gcd(a, b) = gcd(b, a mod b)

Ggd van 3 of meer getallen

gcd(a, b, c) = gcd(gcd(a, b), c)

\gcd(a, b, c) = \gcd(\gcd(a, b),\ c)

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>gcd</mi>
    <mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>,</mo><mi>c</mi><mo>)</mo>
    <mo>=</mo>
    <mi>gcd</mi>
    <mo>(</mo>
    <mi>gcd</mi>
    <mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
    <mo>,</mo><mi>c</mi>
    <mo>)</mo>
  </mrow>
</math>

gcd(a, b, c) = gcd(gcd(a, b), c)

GCD[a, b, c]

igcd(igcd(a, b), c);

g = gcd(gcd(a, b), c);

gcd(a, b, c) = gcd(gcd(a, b), c)

Het verband tussen de ggd en het kgv

gcd(a, b) × lcm(a, b) = a × b

\gcd(a, b) \times \mathrm{lcm}(a, b) = a \times b

<math xmlns="http://www.w3.org/1998/Math/MathML" display="block">
  <mrow>
    <mi>gcd</mi>
    <mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
    <mo>&#xD7;</mo>
    <mi>lcm</mi>
    <mo>(</mo><mi>a</mi><mo>,</mo><mi>b</mi><mo>)</mo>
    <mo>=</mo>
    <mi>a</mi>
    <mo>&#xD7;</mo>
    <mi>b</mi>
  </mrow>
</math>

gcd(a, b) xx lcm(a, b) = a xx b

GCD[a, b]*LCM[a, b] == a*b

igcd(a, b)*ilcm(a, b) = a*b;

gcd(a, b)*lcm(a, b) == a*b

gcd(a, b) × lcm(a, b) = a × b

Zo laat je ChatGPT de berekening doen

Je bent een rekenassistent voor gehele getallen. Voer de volgende berekening uit door daadwerkelijk Python-code uit te voeren en baseer je antwoord alleen op de getallen uit het resultaat van de uitvoering (geef geen antwoord op basis van hoofdrekenen of gokken).

Zoek voor de vier gehele getallen 330, 75, 450 en 225 het volgende:
1. De grootste gemene deler (ggd) van de vier getallen
2. De priemfactorontbinding van elk getal
3. De priemfactoren die alle vier de getallen gemeen hebben

Laat de formules zien die je hebt gebruikt en de getallen uit het resultaat van de uitvoering.

Zo werkt het

1

Vul je getallen in

Typ de getallen waarmee je wilt rekenen in de invoervelden
2

Bereken

Klik op de knop “Berekenen”
3

Bekijk het resultaat

Het resultaat verschijnt meteen. Op dezelfde pagina vind je ook de uitwerking van de berekening en de uitleg van de formule