WisFaq!

De digitale vraagbaak voor het wiskundeonderwijs

HOME

samengevat

\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

Re: Wat doet het uitgebreide algoritme van euclides?