EXTENDED-EUCLID(a,b) 1 ifb==0 2 return (a,1,0) 3 else (d',x',y')=EXTENDED-EUCLID(b,a mod b) 4 (d,x,y)=(d',y',x'-La/b]y') 5 return (d,x,y) d =d' =bx'+(a mod b)y' =bx'+(a-b[a/b])y =ay'+b(x'-[a/bly')d =d’ =bx’+(a mod b)y’ =bx’+(a-b[a/b])y’ =ay’+b(x’-[a/b]y’)