Note that: as + bt = d, where gcd(a,b) = d

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