Uitgebreid algoritme van Euclides

Uit Wikipedia, de vrije encyclopedie
Naar navigatie springen Naar zoeken springen

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.

Voorbeeld[bewerken]

Bepaal de g.g.d. van 1140 en 900 en schrijf hun g.g.d. als lineaire combinatie van beide getallen.

Dus: . Met dit resultaat kan nu de berekening in omgekeerde volgorde opgeschreven worden:

Daarmee is de g.g.d. 60 uitgedrukt als gehele lineaire combinatie van 1140 en 900.