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

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

We hebben nu gevonden: $ggd(1140,900)=60$$ggd(1140,900)=60$. Met dit resultaat kunnen we nu de berekening in omgekeerde volgorde opschrijven:

${\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}}$${\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.

Of in één slag:

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