Uitgebreid Euclidisch algoritme
Het uitgebreide algoritme van Euclides is een manier om een x en y te vinden in de vergelijking
- xa+yb=ggd(a,b)
waarbij de ggd de grootste gemene deler (g.g.d.) is van a en b. Dit is de uitgebreide versie op het eenvoudigere algoritme van Euclides en maakt gebruik van de stelling van Bachet-Bezout.
Het algoritme gaat als volgt:
-
- Neem de variabelen x=v=1 en y=u=0
- Bepaal q en r in de vergelijking a=qb+r met
. Vervang daarna (simultaan):
- a door b, b door r
- x door u en y door v
- u door x-qu en v door y-qv
- Herhaal stap 2 totdat b gelijk is aan 0
- De waardes x en y zijn nu zo dat ggd(a,b)=xa+yb.
[bewerk] Voorbeeld
Het bepalen van de g.g.d. van 202 en 142 gaat volgens dit algoritme als volgt:
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.
