\require{AMSmath}

Het uitgebreid euclidisch algoritme

ik moet voor wiskunde een som berekenen met het uitgebreid euclidisch algoritme. De getallen zijn: 404 en 284. Ik heb al een voorbeeldsom maar ik weet niet hoe het nou precies in elkaar zit en hoe ik het zelf dus moet toepassen:
voorbeeldsom:
202 = 1 · 202
142=1·142
60= 1·202 - 1·142
22=-2·202+3·142
16=5·202-7·142
6=-7·202+10·142
4=19·202-27·142
2=-26·202+37·142
0=71·202-101·142

ik hoop dat jullie mij kunnen helpen!

Laura
Leerling bovenbouw havo-vwo - zaterdag 21 mei 2005

Antwoord

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 0br.
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	

hk
maandag 23 mei 2005

©2001-2024 WisFaq