Algebra

Analyse

Bewijzen

De grafische rekenmachine

Discrete wiskunde

Fundamenten

Meetkunde

Oppervlakte en inhoud

Rekenen

Schoolwiskunde

Statistiek en kansrekenen

Telproblemen

Toegepaste wiskunde

Van alles en nog wat


\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