De digitale vraagbaak voor het wiskundeonderwijs

home |  vandaag |  gisteren |  bijzonder |  gastenboek |  wie is wie? |  verhalen |  contact

HOME

samengevat
vragen bekijken
een vraag stellen
hulpjes
zoeken
FAQ
links
twitter
boeken
help

inloggen

colofon

  \require{AMSmath} Printen

Wat doet het uitgebreide algoritme van euclides?

Ik had de volgende vraag: wat is het verschil tussen het algoritme van Euclides en de uitgebreide algoritme van Euclides? Of is dit gewoon hetzelfde?

matanj
Leerling bovenbouw havo-vwo - donderdag 18 maart 2004

Antwoord

Met het algoritme van Euclides bepaal je de ggd van twee getallen.

Voorbeeld 1: ggd(24,18)
24=1·18+6
18=3·6+0
Dus ggd(24,18)=6

Voorbeeld 2: ggd(25,7)
25=3·7+4
7=1·4+3
4=1·3+1
1=1·1=0
Dus ggd(25,7)=1
De rest op de regel voordat rest 0 verschijnt is de ggd.

Bij het uitgebreide algoritme van Euclides ter bepaling van ggd(a,b) bepaal je behalve de ggd van a en b ook de getallen p en q zo, dat ggd(a,b)=p·a+q·b.
Bekijken we bijvoorbeeld nog eens de berekening van ggd(25,7)
25=3·7+4, dus 4=25-3·7 (1)
7=1·4+3, dus 3=7-1·4 (2)
4=1·3+1, dus 1=4-1·3 (3)

Uit (1) en (2) volgt
3=7-1·4=7-(25-3·7)=4·7-1·25
Pakken we nu (3), dan krijgen we:
1=4-1·3=(25-3·7)-1·(4·7-1·25)=2·25-7·7
Dus ggd(25,7)=1 en ggd(25,7)=2·25-7·7 (klopt want 1=50-49)

Op Cryptografie I vind je onderaan de bladzijde ook een uitleg van het uitgebreide algoritme van Euclides en een handig rekenschema.

Wie is wie?
Vragen naar aanleiding van dit antwoord? Klik rechts..!
vrijdag 19 maart 2004
Re: Wat doet het uitgebreide algoritme van euclides?



home |  vandaag |  bijzonder |  gastenboek |  statistieken |  wie is wie? |  verhalen |  colofon

©2001-2024 WisFaq - versie 3