Algoritme van Euclides: verschil tussen versies

Door [[uitgebreid algoritme van Euclides|omkering van de stappen in het algoritme van Euclides]] kan de ggd worden uitgedrukt als de [[lineaire combinatie|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 [[Stelling van Bachet-Bézout|identiteit van Bézout]]. Op deze manier geeft dit [[Uitgebreid algoritme van Euclides|uitgebreide algoritme]] een oplossing voor de [[Diophantischediofantische vergelijking]]

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.<ref>{{en}} {{aut|Godfried Toussaint}}, ''The Euclidean algorithm generates traditional musical rhythms'' (Het algoritme van Euclidische genereert de traditionele muzikale ritmes), ''Proceedings of BRIDGES: Mathematical Connections in Art, Music, and Science'', Banff, Alberta, Canada, 31 juli-3 augustus 2005, pp. 47-56.</ref> Ook is het een belangrijk onderdeel van het [[RSA (cryptografie)|RSA-algoritme]], een [[Asymmetrische cryptografie|publieke sleutel versleutelingsmethode]], die op grote schaal in de [[electronic commerce|elektronische handel]] wordt gebruikt. Het algoritme wordt gebruikt bij het oplossen van [[Diophantischediofantische vergelijking]]en, zoals het vinden van getallen die aan meerdere congruenties ([[Chinese reststelling]]) of [[omgekeerde|multiplicatieve inversen]] van een [[Eindig lichaam (Ned) / Eindig veld (Be)|eindig veld]] voldoen. Het algoritme van Euclides kan ook worden gebruikt in de constructie van [[kettingbreuk]]en, in de [[Sturm-ketting]]methode voor het vinden van reële wortels van een veelterm en in diverse moderne [[ontbinden in priemfactoren|geheelgetalfactorisatie-algoritmen]]. Ten slotte is het een fundamenteel instrument voor het bewijzen van [[stelling (wiskunde)|stellingen]] in de moderne [[getaltheorie]], zoals de [[vier-kwadratenstelling van Lagrange]] en de [[hoofdstelling van de rekenkunde]] (unieke factorisatie).