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₀ = a en r₁ = 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.