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 zogeheten identiteit van Bézout, een lineaire Diophantische vergelijking in gehele x en y:

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

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

Het bewijs van de stelling van Bachet-Bezout steunt op de constructie door het algoritme.

Aan de hand van een voorbeeld zal duidelijk worden hoe het algoritme tot stand komt.

Voorbeeld

We bepalen met het algoritme van Euclides de g.g.d. van 1140 en 900.

1140 = 1 × 900 + 240
900 = 3 × 240 + 180
240 = 1 × 180 + 60
180 = 3 × 60 + 0

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

60 = 240 - 1 × 180
180 = 900 - 3 × 240, zodat 60 = 240 - 1 × ( 900 - 3 × 240) = -1 × 900 + 4 × 240
240 = 1140 - 1 × 900, zodat 60 = -900 + 4 × (1140 - 1 × 900) = 4 × 1140 - 5 × 900

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

Men had op analoge wijze het resultaat ook direct kunnen verkrijgen:

1140 = 1 × 900 + 240, dus 240 = 1 × 1140 - 1 × 900
900 = 3 × 240 + 180, dus 180 = 1 × 900 - 3 × 240 = -3 × 1140 + 4 × 900
240 = 1 × 180 + 60, dus 60 = 1 × 240 - 1 × 180 = 4 × 1140 - 5 × 900
180 = 3 × 60 + 0

Algoritme

De systematiek in deze berekening laat zich als volgt beschrijven:

$\begin{matrix} r_{0} = a = x_0a+y_0b\\ r_{1} = b = x_1a+y_1b\\ r_{2} = a-q_2b = r_0-q_2r_1\\ \cdots\\ r_{n-1} = x_{n-1}a+y_{n-1}b\\ r_{n} = x_na+y_nb\\ r_{n+1} = r_{n-1}-q_{n+1}r_n =(x_{n-1}-q_{n+1}x_n)a+(y_{n-1}-q_{n+1}y_n)b=x_{n+1}a+y_{n+1}b\\ \cdots\\ r_{N-1} = x_{N-1}a+y_{N-1}b\\ r_{N} = x_Na+y_Nb\\ r_{N+1} = 0\\ \end{matrix}$

Het best bezien we eerst de berekeningen na de eerste paar stappen. Van de nieuwe $'a' = r_{n-1}$ en $'b' = r_n$ wordt de nieuwe rest $r_{n+1} = r_{n-1}-q_{n+1}r_n$ bepaald. In de vorige stappen zijn de resten $r_{n-1}$ en $r_n$ uitgedrukt als gehele lineaire combinatie van de oorspronkelijke getallen a en b, met coëfficiënten respectievelijk $x_{n-1}$ en $y_{n-1}$ en $x_n$ en $y_n$. Daarmee laat ook de nieuwe rest $r_{n+1}$ zich in a en b uitdrukken, met coëfficiënten $x_{n+1}=x_{n-1}-q_{n+1}x_n$ en $y_{n+1}=y_{n-1}-q_{n+1}y_n$. Het algoritme loopt af als de rest 0 wordt. De vorige rest is de gezochte g.g.d. uitgedrukt als gehele lineaire combinatie van a en b. Om het algoritme te beginnen, kiezen we als startwaarden $r_0=a$ en $r_1=b$.

Rekenschema

In het rekenschema van het algoritme houden we de rij met resten r bij en daarnaast de resultaten q van de deling, alsmede de coëfficiënten x en y, die dezelfde structuur vertonen als de resten. Als startwaarden kiezen we:

$r_0 = \max(a,b)\,$

$r_1 = \min(a,b)\,$

$x_0 = 1 \;$

$x_1 = 0 \;$

$y_0 = 0 \;$

$y_1 = 1 \;$

We bepalen de nieuwe rest r en het resultaat q van de deling door:

$q_{n+1} = r_{n-1}\div r_n\;$

$r_{n+1} = r_{n-1}-q_{n+1}r_n\;$

en vervolgens de nieuwe coëfficiënten uit:

$x_{n+1} = x_{n-1}-q_{n+1}x_n\;$

$y_{n+1} = y_{n-1}-q_{n+1}y_n\;$

Het algoritme loopt af als de nieuwe rest gelijk is aan 0.

Voorbeeld (vervolg)

Voor het voorbeeld ziet dat er zo uit (tussen haakjes is ter verduidelijking het tussenresultaat vermeld):

r q x y
1140 1 0 (1140 = 1 x 1140 + 0 x 900)
900 0 1 ( 900 = 0 x 1140 + 1 x 900)
240 1 1 -1 ( 240 = 1 x 1140 - 1 x 900)
180 3 -3 4 ( 180 =-3 x 1140 + 4 x 900)
60 1 4 -5 ( 60 = 4 x 1140 - 5 x 900)
0

Voorbeeld

Het bepalen van de g.g.d. van 202 en 142 gaat volgens dit algoritme als volgt:

$\begin{matrix} & 202 &= &1 &\cdot &202 \\ & 142 &= &&&&&1 &\cdot &142 \\ & 60 &= &1 &\cdot &202 &- &1 &\cdot &142 \\ & 22 &= &-2 &\cdot &202 &+ &3 &\cdot &142 \\ & 16 &= &5 &\cdot &202 &- &7 &\cdot &142 \\ & 6 &= &-7 &\cdot &202 &+ &10 &\cdot &142 \\ & 4 &= &19 &\cdot &202 &- &27 &\cdot &142 \\ & 2 &= &-26 &\cdot &202 &+ &37 &\cdot &142 \\ & 0 &= &71 &\cdot &202 &- &101 &\cdot &142 \end{matrix}$

2 is het getal dat voor de 0 nog uit te drukken was in de vorm xa+yb, dus is dat de grootste gemene deler van 202 en 142.