Het algoritme van Euclides
Het algoritme van Euclides is een manier om uit twee getallen de grootste gemene deler te vinden. De grootste gemene deler kun je onder andere gebruiken wanneer je breuken vereenvoudigt en wanneer je complexe vergelijkingen wilt oplossen. Het algoritme is vernoemd naar Euclides, een Griekse wiskundige die het algoritme beschreef in een van zijn werken in het jaar 300 voor Christus.
Een algoritme is een rekenkundige procedure waarbij je stap voor stap een berekening uitvoert volgens vaste regels.
Een aantal vaste stappen
Net als andere algoritmes werkt het algoritme van Euclides volgens een aantal stappen. De uitkomst na iedere stap vormt de input voor de volgende stap. Je kunt dus geen stappen overslaan en je begint met twee getallen.
In woorden werkt het ongeveer zo: je neemt het kleinste van de twee getallen en bepaalt hoeveel keer dit getal in het grootste getal past. Dat doe je opnieuw voor het kleinste van de twee eerste getallen en het getal dat je in de eerste stap hebt overgehouden. Dit proces herhaal je tot je niets meer overhoudt. Het laatste getal dat overblijft is de grootste gemene deler. We korten de grootste gemene deler af met ‘ggd’.
We laten dit in stappen zien in een voorbeeld waarbij we de grootste gemene deler zoeken van de getallen 315 en 91?
ggd (315, 91) = ?
Stap 1: 315 = (91 x 3) + 42
Stap 2: 91 = (42 x 2) + 7
Stap 3: 42 = (7 x 6)
Het getal 7 is de ggd (of de grootste gemene deler) van de getallen 315 en 91.
ggd (1300, 388) = ?
Stap 1: 1300 = (388 x 3) + 136
Stap 2: 388 = (136 x 2) + 116
Stap 3: 136 = (116 x 1) + 20
Stap 4: 116 = (20 x 5) + 16
Stap 5: 20 = (16 x 1) + 4
Stap 6: 16 = (4 x 4)
Het getal 4 is de ggd van de getallen 1300 en 388.
Rekenles.com 2018 ©
