|
|
\require{AMSmath}
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.
|
Vragen naar aanleiding van dit antwoord? Klik rechts..!
vrijdag 19 maart 2004
|
|
home |
vandaag |
bijzonder |
gastenboek |
statistieken |
wie is wie? |
verhalen |
colofon
©2001-2024 WisFaq - versie 3
|