Prove Bezouts theorem This is most easily done by induction

Prove Bezout\'s theorem. This is most easily done by induction on the number of steps in the Euclidean algorithm for a(x) and b(x). If the algorithm terminates right away, which means that a(x) divides b(x), then the result is proved. Next assume that you know the result for pairs of polynomials for which the algorithm terminates after k steps and deduce the results for pairs of polynomials for which the algorithm terminates after k+1 steps.

Solution

Proof:

Let a > b. The proof is by induction on Eulen(a, b). If Eulen(a, b) = 1, i.e., if b|a, then a = bu for an integer u. Hence,a + (1 - u)b = b = gcd(a, b). We can take s = 1 and t = 1 - u.

Assume the Corollary has been established for all pairs of numbers for which Eulen is less than n. Let Eulen(a, b) = n.Apply one step of the algorithm: a = bu + r. Eulen(b, r) = n - 1. By the inductive assumption, there exist x and y such thatbx + ry = gcd(b,r) = gcd(a,b). Express r as r = a - bu. Hence, ry = ay - buy; bx + (ay - buy) = gcd(a, b). Finally,b(x - uy) + ay = gcd(a, b) and we can take s = x - uy and t = y.