Op uitgebreid euclidisch algoritme kun je lezen:
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.
Het algoritme gaat als volgt:
stap 1) Neem de variabelen x=v=1 en y=u=0
stap 2)Bepaal q en r in de vergelijking a=qb+r met 0
b
r.
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
stap 3)Herhaal stap 2 totdat b gelijk is aan 0
De waardes x en y zijn nu zo dat ggd(a,b)=xa+yb.
De opdracht
"Bepaal q en r in de vergelijking a=qb+r met 0br." voer je het makkelijkst zo uit:
deel a door b, het gehele deel van de deling is q, de rest bij deling is r.
In onderstaande tabel heb ik dat eens in praktijk gebracht.
Op de eerste regel staan de namen van de variabelen.
Op de tweede regel staat de situatie als je stap 2 de eerste keer ingaat.
Op de volgende regels de situatie nadat je stap 2 weer een keer hebt uitgevoerd.
a b q r x y u v
202 142 - - 1 0 0 1
202 142 1 60 0 1 1 -1
142 60 2 22 1 -1 -2 3
60 22 2 16 -2 3 5 -7
22 16 1 6 5 -7 -7 10
16 6 2 4 -7 10 19 -27
6 4 1 2 19 -27 -26 37
4 2 2 0 -26 37 71 -101
Voor a=404 en b=284 krijg je dan:
a b q r x y u v
404 284 - - 1 0 0 1
404 284 1 120 0 1 1 -1
284 120 2 44 1 -1 -2 3
120 44 2 32 -2 3 5 -7
44 32 1 12 5 -7 -7 10
32 12 2 8 -7 10 19 -27
12 8 1 4 19 -27 -26 37
8 4 2 0 -26 37 71 -101
maandag 23 mei 2005
