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

$ax+by=\mathrm {ggd} (a,b)$,

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

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

${\begin{matrix}&1140&=&1&\times &900&+&240\\&900&=&3&\times &240&+&180\\&240&=&1&\times &180&+&60\\&180&=&3&\times &60&+&0\\\end{matrix}}$

Dus: $\mathrm {ggd} (1140,900)=60$. Met dit resultaat kan nu de berekening in omgekeerde volgorde opgeschreven worden:

${\begin{matrix}60&=&240-1\times 180\\180&=&900-3\times 240&&&60&=&240-1\times (900-3\times 240)&=&-1\times 900+4\times 240\\240&=&1140-1\times 900&&&60&=&-900+4\times (1140-1\times 900)&=&4\times 1140-5\times 900\\\end{matrix}}$

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