Given two integers x,y, one may wonder what numbers can be obtained by adding integer multiples of x and y, i.e., what integers can be expressed as ax+by for some (not necessarily positive) integers a,b. It turns out that g=gcd(x,y) is the smallest positive integer that can be written as g=ax+by; this fact is known as Bzout's identity. In this problem, we'll modify the standard Euclidean algorithm to give us not only g= gcd(x,y), but also a pair (a,b) of integers for which ax+by=g. Such integers are called Bzout coefficients. We give (most of) the algorithm below: Require: integers x>y0 Ensure: a triple (g,a,b) of integers where g=gcd(x,y) and ax+by=g (a) State what a and b should be on Line 7, and prove that these values are correct ones. Hint: you will need to show that: (1) the output g equals gcd(x,y), and (2) ax+by=g. Note that by recursion/induction, we know that ay+br=g. Manipulate this to involve x,y instead of y,r. (b) Run the Extended Euclid algorithm by hand, showing a 'trace' of the execution (values of all the relevant variables for each recursive call), to find Bzout coefficients for the input (x,y)=(193,52). Verify that they are correct