Grootste gemene deler
De grootste gemene deler van twee gehele getallen is het getal dat beide getallen zonder rest deelt, waarbij er geen ander, groter getal bestaat dat beide getallen ook zonder rest deelt.
Neem als voorbeeld de getallen 24 en 32. Wat is hun grootste gemene deler? Eerst zoeken we een getal dat beide getallen deelt.
- Het getal 12 deelt bijvoorbeeld wel 24, maar niet 32, want 32 / 12 is gelijk aan 2,666… en dat is geen geheel getal. Het getal 12 kan dus niet de grootste gemene deler van 24 en 32 zijn.
- En het getal 4? Dat deelt beide getallen: 24 / 4 is gelijk aan 6 en 32 / 4 is gelijk aan 8. Het getal 4 is dus onze eerste kandidaat. Bestaat er een groter getal dat beide getallen deelt?
- Het getal 8 deelt zowel 24 als 32 en is bovendien groter dan 4.
- Een ander getal groter dan 8 dat beide getallen deelt, bestaat niet. Het getal 8 is dus de grootste gemene deler van 24 en 32.
Het algoritme van Euclides voor het vinden van de grootste gemene deler
Er bestaat een vrij eenvoudige manier om de grootste gemene deler van twee getallen te vinden: het algoritme van Euclides. We beginnen met twee getallen x en y waarvan we de grootste gemene deler willen vinden. We proberen het als voorbeeld met de getallen x = 50 en y = 35. Dan gaan we zo te werk:
- We delen x / y en onthouden de rest van de deling. Die rest noteren we als z. In ons voorbeeld krijgen we 50 / 35, en dat geeft rest z = 15.
- Nu verschuiven we de variabelen: in variabele x bewaren we de waarde van y en in y bewaren we de waarde van z. De oorspronkelijke waarde van x gooien we weg. Na deze stap hebben we x = 35 en y = 15.
- Nu kijken we of y gelijk is aan nul. Zo ja, dan is het getal x de grootste gemene deler. Omdat y niet gelijk is aan nul, gaan we verder en herhalen we de hele werkwijze vanaf het eerste punt.
- We delen opnieuw x / y, dus 35 / 15, en dat geeft rest z = 5.
- We verschuiven de variabelen, dus we krijgen x = 15 en y = 5. Omdat y niet gelijk is aan nul, gaan we verder.
- We delen x / y, dus 15 / 5. De rest is z = 0.
- We verschuiven de variabelen en krijgen x = 5 en y = 0.
- Nu is y = 0 en stopt ons algoritme. De grootste gemene deler is het getal x = 5.
Belangrijk is dat de volgorde van de getallen niet uitmaakt. Als we de getallen uit het voorbeeld zouden omwisselen, kregen we het paar x = 35 en y = 50. De werkwijze zou hetzelfde zijn:
- We delen x / y, dus 35 / 50, en dat geeft rest z = 35.
- We verschuiven de variabelen: x = 50 en y = 35.
- We zien dat we na deze stap alleen de inhoud van de variabelen x en y met elkaar hebben omgewisseld…
Rekenmachine
Deze rekenmachine berekent de grootste gemene deler voor je.
