Let a=128 and b=221, and let d=hof(a,b). Find the smallest integers s,t such that desa+th, using the Euclidean Algorithm. Recall the statement of the Proposition 10.5 in Liebeck, 4th edition, Chapter 10: Let a,be Z . ) Suppose c is an Integer such that a,c are coprime to each other, and clab. Then clb. b) Suppose that p is a prime number and plab. Then either pla or plb. We assume Proposition 10.5a) to be true. Which of the following is a correct proof for Proposition 10.5b)? Suppose that p does not divide a. Then since p is prime, hof(a,p)=1 or p. But p does not divide a so hof(a,p)=1. Hence a and p are coprime, so by part a), plb, as required. Suppose that p does not divide a. Then since p is prime, hof(a,p)=1 or p. But If we assume pla then hof(a,p)=p. Hence we arrive at a contradiction and pla, as required. Suppose that p does not divide a. Then since p is prime, hof(a,p)=1 or p. But p does not divide a so hof(a,p)=1. Hence a and p are coprime, so we arrive at a contradiction and p does not divide ab, as required. . Suppose that p does not divide a. Then since p is prime, hof(a,p)=1 or p. But if we assume plo then hof(b,p)=p. Hence we arrive at a contradiction and plb, as required. O Suppose that p does not divide a and p does not divide b. We will use the contrapositive and show that plab. Then since p is prime, hof(a,p)=1 or p. But p does not divide a so hef(a,p)=1. Similarly hef(b,p)=1. Hence a and p are coprime, and b and p are coprime. But by part a), plab. Therefore pla or plo, as required. Suppose that p does not divide a and p does not divide b. We will use the contrapositive and show that p does not divide ab. Then since p is prime, hef(a,p)=1 or p. But p does not divide a so hef(a,p)=1. Similarly hcf(b,p)=1. Hence a and p are coprime, and b and p are coprime. So by part a), p does not divide ab, as required