uitgebreid algoritme van Euclides

Het uitgebreide algoritme van Euclides is een uitbreiding van het algoritme van Euclides, die niet alleen de grootste gemene deler g.g.d. van twee natuurlijke getallen en bepaalt, maar ook een oplossing geeft van de identiteit van Bézout, een lineaire diofantische vergelijking in gehele en : , waarin ggd staat voor grootste gemene deler. De uitbreiding bestaat daarin dat behalve de berekening van de g.g.d. van de getallen en met het algoritme van Euclides, ook de g.g.d. wordt uitgedrukt als gehele lineaire combinatie van en . Het bewijs van de stelling van Bachet-Bézout steunt op de constructie door het algoritme. Aan de hand van een voorbeeld zal duidelijk worden hoe het algoritme tot stand komt.