Show that if a b > 0, then the values s and t computed by ExtEuclid(a, b) satisfy |s| b/d and |t| a/d. Hint: prove by induction on bbe careful, you have to stop the induction before b gets to zero, so the last step to consider is when b | a.

ExtEuclid(a, b): On input a, b, where a and b are integers such that a b 0, compute (d, s, t), where d = gcd(a, b) and s and t are integers such that as + bt = d, as follows:

if b = 0 then d a,

s 1, t 0

else

q [a/b], r a mod b

(d, s' , t' ) ExtEuclid(b, r)

s t' , t s' qt'

return (d, s, t)

Algorithm ExtEuclid(a, b): On input a, b, where a and b are integers such that a 2b20, compute (d, s, t), where d- gcd(a, b) and s and t are integers such that as +bt-d, as follows: if b 0 then da, s