We consider two integers a, b e Z and the sequences ri, qi, xi, yi that come from applying the extended Euclidean algorithm to a, b. Suppose that n+1 = gcd(a, b)). (a) For i = 1,..., n + 1, define A; = (43). = 0, y = = 1 and x; = x-2 (b) Define xo = 1, x = 0 and yo = (c) Prove that |Xi-1 Vi-1 Xi Xi-1 and conclude that xa + yib = r. :') yi 0 (i.e., n = = Prove that (8) k-1 1,...,n+1. rk qixi-1 and y = yi-2- qiyi-1. Prove that Yi-1 *)(0) = (2) = A... Ak -1 (xi-2 yi-2 for i= 2, ...,n + 1. (Xi-1 Ni-1) for k= for i=0,...,n+1