Euclid's algorithm finds the greatest common divisor gcd(a,b) of integers a and b. Show that with a little extra bookkeeping it can also find (possibly negative) integers x and y such that ax+by=gcd(a,b).

Now assume that b y < b and by 1 mod a.