WisFaq!

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?

matanja
18-3-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.

hk
19-3-2004