Problem (Extended Euclidean Algorithm)

Problem (Extended Euclidean Algorithm) 1. Given (a,b)=(105,1309), compute gcd(a,b), writing the sequence of divisions generated by the Euclidean Algorithm when computing gcd(a,b). 2. Given (a,b)=(105,1309), compute the Bzout identity of (a,b). All steps must be given, like in the lecture slides (Chapter 4 Part 2). 3. Given m=3677 and a=360, explain why a is invertible modulo m. Then compute the inverse of a modulo m using the Bzout identity of (a,m)