De grootste gemene deler van gehele getallen is het grootste positieve getal dat ze allemaal zonder rest deelt. De afkorting is ggd. Hij vereenvoudigt breuken en verhoudingen, verdeelt aantallen in gelijke groepen en bepaalt de grootste maat die exact in meerdere lengtes past.
Gemeenschappelijke delers maken de definitie zichtbaar
De positieve delers van 18 zijn 1, 2, 3, 6, 9 en 18. Voor 24 zijn het 1, 2, 3, 4, 6, 8, 12 en 24. Gemeenschappelijk zijn 1, 2, 3 en 6, dus de ggd is 6. Volledig opsommen wordt onpraktisch bij grote getallen.
Kies twee positieve gehele getallen. Het paneel toont elke deling en rest van Euclides, zodat de route controleerbaar blijft.
Volg het algoritme van Euclides
Elke stap vervangt het paar door deler en rest; de laatste niet-nulrest is de ggd.
Priemfactorisatie bewaart de kleinste exponenten
Ontbind elk getal in priemfactoren. Neem voor elke priemfactor die overal voorkomt de kleinste exponent en vermenigvuldig de gekozen machten. De methode werkt ook voor drie of meer getallen.
Voor 84 en 126 zijn één factor 2, 3 en 7 gemeenschappelijk. Het product is 42. De controle: 84 gedeeld door 42 is 2 en 126 gedeeld door 42 is 3. Geen extra priemmacht komt in beide ontbindingen voor.
Euclides vermijdt lastige factorisaties
Voor (a>b>0) deel je (a) door (b). Vervang het paar door (b) en de rest en herhaal. Gemeenschappelijke delers blijven behouden, want iedere deler van (a) en (b) deelt ook (a-qb). De laatste niet-nulrest is de ggd.
Bij 252 en 105 volgen de resten 42, 21 en nul. De ggd is 21 zonder volledige factorisatie. Gewoonlijk geldt (gcd(a,0)=|a|); het paar (0,0) blijft vaak ongedefinieerd.
Identiteiten bieden een tweede controle
De invoer omwisselen verandert de positieve ggd niet. Na delen door de ggd zijn de quotiënten onderling ondeelbaar. Bovendien is ggd maal kleinste gemene veelvoud gelijk aan de absolute waarde van het product van beide getallen.
Tegelen zonder snijverlies
Een vloer van 252 cm bij 105 cm moet met de grootst mogelijke vierkante tegels zonder snijden worden bedekt. De zijde deelt beide maten en is 21 cm. Er passen 12 bij 5, dus 60 tegels.
De ggd geldt bij exacte deelbaarheid. Zijn afval, toleranties of afgeronde metingen toegestaan, dan vraagt de praktische keuze een ander criterium. Zet alle lengtes eerst om naar dezelfde exacte eenheid.
Voor drie getallen werk je stapsgewijs: bepaal eerst de ggd van de eerste twee en daarna de ggd van dat antwoord en het derde getal. De ggd van 48 en 72 is 24; samen met 60 wordt dat 12. Negatieve tekens veranderen de deelbaarheid niet, dus werk met absolute waarden en geef een positieve ggd. Deel ieder oorspronkelijk getal door de kandidaat. Alle quotiënten moeten geheel zijn, en de kandidaat kan niet groter zijn dan de absolute waarde van een niet-nulinvoer.
