title: Algoritme van Euclides
text: 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 het kleinste getal en 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.
  
  Achtergrond 
  De grootste gemeenschappelijke deler van twee getallen is het grootste getal dat beide getallen zonder rest deelt. Het algoritme van Euclides is gebaseerd op het principe dat de grootste gemene deler van twee getallen niet verandert als het kleinere getal van het grotere wordt afgetrokken.
  
  Zo is 21 de grootste gemene deler van  aangezien de ggd van  ook gelijk is aan 21. Aangezien men in het algoritme van twee getallen steeds het kleinste van het grootste aftrekt, kan men dit proces herhalen totdat een van de twee getallen gelijk wordt aan nul. De grootste gemene deler is het resterende getal (dat niet nul is).
  
  Uitbreiding 
  Door omkering van de stappen in het algoritme van Euclides kan de ggd worden uitgedrukt als de som van de twee originele getallen, elk vermenigvuldigd met een positief of negatief geheel getal bijvoorbeeld 21 = 5 × 105 + (-2) × 252. Deze belangrijke eigenschap staat bekend als de identiteit van Bézout. Op deze manier geeft dit uitgebreide algoritme een oplossing voor de diofantische vergelijking
  
  Geschiedenis 
  De oudste overgeleverde beschrijving van het euclidische algoritme vindt men in de Elementen (boek VII, propositie 1 en 2) van Euclides (ca. 300 v.Chr.), waarmee het een van de oudste numerieke algoritmen is die nog steeds worden gebruikt. Euclides beschouwde het meetkundige probleem om van twee afstanden een gemeenschappelijke "maat" te vinden. Het algoritme is waarschijnlijk niet door Euclides bedacht, maar was vrijwel zeker al bekend bij Eudoxus van Cnidus (ca. 375 v.Chr.). Ook Aristoteles (ca. 330 v.Chr.) wijst in zijn werk Topica (158b, 29-35) op het algoritme.
  
  Het originele algoritme werd alleen voor natuurlijke getallen en meetkundige lengtes (reële getallen) beschreven, maar in de 19e eeuw werd het algoritme veralgemeend tot andere soorten soorten getallen, zoals de gehele getallen van Gauss en veeltermen in één variabele. Dit leidde tot moderne abstracte algebraïsche begrippen zoals euclidische domeinen. Gabriel Lamé leverde in 1844 het wiskundig bewijs dat het algoritme nooit meer stappen vereist dan vijf keer het aantal cijfers (basis 10) van het kleinere gehele getal. Dit bewijs markeert het begin van computationele complexiteitstheorie. In de 20e eeuw werd het algoritme van Euclides verder veralgemeend naar andere wiskundige structuren, zoals knopen en multivariate veeltermen. Ook werden methoden ontwikkeld voor het verbeteren van de efficiëntie van het algoritme.
  
  Toepassingen 
  Het algoritme van Euclides kent vele theoretische en praktische toepassingen. Het kan worden gebruikt voor het genereren van bijna alle belangrijkste traditionele muzikale ritmes gebruikt in verschillende culturen over de hele wereld. Ook is het een belangrijk onderdeel van het RSA-algoritme, een publieke sleutel versleutelingsmethode, die op grote schaal in de elektronische handel wordt gebruikt. Het algoritme wordt gebruikt bij het oplossen van diofantische vergelijkingen, zoals het vinden van getallen die aan meerdere congruenties (Chinese reststelling) of multiplicatieve inversen van een eindig veld voldoen. Het algoritme van Euclides kan ook worden gebruikt in de constructie van kettingbreuken, in de Sturm-kettingmethode voor het vinden van reële wortels van een veelterm en in diverse moderne geheelgetalfactorisatie-algoritmen. Ten slotte is het een fundamenteel instrument voor het bewijzen van stellingen in de moderne getaltheorie, zoals de vier-kwadratenstelling van Lagrange en de hoofdstelling van de rekenkunde (unieke factorisatie).
  
  Het algoritme 
   Noem het grootste van de beide getallen , het andere .
   Trek  net zo vaak van  af totdat er 0 overblijft of een getal kleiner dan  ().
   Als er 0 overblijft, is  de ggd.
   Zo niet, herhaal dan het algoritme met  en wat er van  over is.
  
  Voorbeeld 
  Het volgende voorbeeld, waarin de ggd van 900 en 1140 wordt bepaald, verduidelijkt het algoritme van Euclides.
  
  Deling van 1140 door 900 levert:
  
  Omdat de gezochte ggd ook de ggd van 900 en 240 is, wordt 900 door 240 gedeeld:
  
  Dat gaat zo verder:
  
  Nu is de rest 0, waarmee een einde aan de berekening komt. De grootste gemene deler van 900 en 1140 is 60, want:
  
  de laatste stap, 180 = 3 × 60 + 0, laat zien dat 60|180,
  de stap daarvoor, 240 = 1 × 180 + 60, laat zien dat 60|240,
  verder terug, 900 = 3 × 240 + 180, laat zien dat 60|900,
  de eerste stap, 1140 = 1 × 900 + 240, dat 60|1140. 
  De conclusie is dat 60 een gemene deler is van 900 en 1140.
  
  Als d een gemene deler is van 900 en 1140, dan laat 
  de eerste regel, 1140 = 1 × 900 + 240, zien dat d|240
  de tweede regel, 900 = 3 × 240 + 180, dat d|180
  en de derde regel, 240 = 1 × 180 + 60, dat d|60
  Daaruit volgt dat elke gemene deler van 900 en 1140 een deler is van 60. Dan is 60 de grootste gemene deler.
  
  De berekening laat zich kort opschrijven als de rij:
  
  Voor elk opvolgend drietal ... a b c ... in de rij geldt: a mod b = c
  
  Op dezelfde manier wordt de berekening van de ggd van 752 en 372 opgeschreven:
  
  Daaruit volgt:
  
  Implementatie 
  Afhankelijk van de mogelijkheden die een programmeertaal biedt, kan er gebruikgemaakt worden van recursief programmeren en de 'mod'-operatie. In onderstaande implementatie wordt de stap
   Noem het grootste van de beide getallen , het andere 
  overgeslagen: het ene getal wordt zonder meer  en het andere  genoemd. Niettemin gaat het goed, aangezien  gelijk is aan  als  en de getallen daardoor bij de eerste recursie omgedraaid worden.
  
  bepaal ggd(A, B):
    als B = 0
      antwoord = A
    anders
      antwoord = ggd(B, (A mod B))
  
  Bij programmeertalen die geen ondersteuning voor recursief programmeren bieden en/of de 'mod'-operatie niet kennen, kan ook onderstaande gebruikt worden:
  bepaal ggd(A, B):
    zolang (A ≠ B)
      als A > B
        verminder A met B
      anders
        verminder B met A
  Na doorlopen van deze code zijn de getallen  en  gelijk en elkaars grootste gemene deler (evenals van de oorspronkelijke getallen).
  
  Getaltheorie
  Algoritme