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 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[bewerken]

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[bewerken]

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[bewerken]

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)[bewerken]

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[bewerken]

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.