computing gcd(a,b)=ax+by

Euclid(a,b: integer):integer3

g := a; g' := b;

x := 1; x' := 0;

y := 0; y' := 1;

WHILE g'>0 DO

. . . k := g div g'

. . . (g'',x'',y'') := (g,x,y) - k(g',x',y')

. . . (g,x,y) := (g',x',y')

. . . (g',x',y') := (g'',x'',y'')

RETURN (g,x,y)

running time: O(|a||b|)