Algoritme van Euclides

In de getaltheorie, een deelgebied van de wiskunde, is het algoritme van Euclides een efficiënte methode voor het berekenen van de grootste gemene deler (ggd) van twee positieve gehele getallen. Het algoritme is vernoemd naar de Oud-Griekse wiskundige Euclides van Alexandrië, die het algoritme in de boeken VII en X van zijn Elementen beschreef. Het algoritme berust erop dat de ggd van twee gehele getallen ook de ggd is van zowel het kleinste getal als van de rest die overblijft bij deling van het grootste getal door het kleinste. Zo ontstaat er een aflopend iteratief proces. Er bestaat ook een uitgebreide variant van dit algoritme.