In this exercise you will see how matrix multiplication can be used to get a nice proof of the major identitie that play a role in the extended Euclidean algorithm. We consider two integers a,bZ and the sequences ri,qi,xi,yi that come from applying the extendec Euclidean algorithm to a,b. Suppose that rn+1=0 (i.e., rn=gcd(a,b) ). (a) For i=1,,n+1, define Ai=(qi110). Prove that (ab)=A1Ak(rk1rk) for k=1,,n+1. (b) Define x0=1,x1=0 and y0=0,y1=1 and xi=xi2qixi1 and yi=yi2qiyi1. Prove that (xi1xiyi1yi)=Ai1(xi2xi1yi2yi1) for i=2,,n+1. (c) Prove that (xi1xiyi1yi)(ab)=(ri1ri)fori=0,,n+1 and conclude that xia+yib=ri