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

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}


We hebben nu gevonden: 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}

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}