Uitgebreid algoritme van Euclides

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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 a en b bepaalt, maar ook een oplossing geeft van de identiteit van Bézout, een lineaire diofantische vergelijking in gehele x en y:

waarin ggd staat voor grootste gemene deler. De uitbreiding bestaat daarin dat behalve de berekening van de g.g.d. van de getallen a en b met het algoritme van Euclides, ook de g.g.d. wordt uitgedrukt als gehele lineaire combinatie van a en b.

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 in twee slagen de g.g.d. van 1140 en 900 en hun g.g.d. geschreven als de lineaire combinatie van beide getallen:


We hebben nu gevonden: . Met dit resultaat kunnen we nu de berekening in omgekeerde volgorde opschrijven:

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

Of in één slag: