F. A Method for Computing the ged Let a(x) and b(x) be polynomials of positive d

Question

F. A Method for Computing the ged Let a(x) and b(x) be polynomials of positive degree. By the division algorithm, we may divide a(x) by b(x): alx -blglx) + ri.(x) 1 Prove that every common divisor of a(x) and b(x) is a common divisor of b(r) and ri(x). It follows from part 1 that the ged of a(r) and b(x) is the same as the ged of bx) and ri(x). This procedure can now be repeated on b(x) and r(x); divide b(r) by r1r): b(x)-ri(r)42(x)r2x) Next Finally rn-i (x)-(x)2n+1(x) + 0 In other words, we continue to divide each remainder by the succeeding remainder. Since the remainders continually decrease in degree, there must ultimately be a zero remainder. But we have seen that gcd(a(x),b(x)) = gcd(b(x), ri(x)) = _ gcd(rn-i (x), (x)) Since r,(x) is a divisor of r-x), it must be the ged of n(x andThus, (x)-gcd(a(x), b(x)] This method is called the euclidean algorithm for finding the ged.

Explanation / Answer

Let, gcd(a(x),b(x)) = d(x).

Then, there exist polynomials u(x) and v(x) such that [a(x) * u(x)] + [b(x) * v(x)] = d(x).

We have, a(x) = [b(x) * q1(x)] + r1(x)

Now, [a(x) * u] + [b(x) * v] = d(x)

i.e., [{[b(x) * q1(x)] + r1(x)} * u(x)] + [b(x) * v(x)] = d(x)

i.e., [b(x) * q1(x) * u(x)] + [r1(x) * u(x)] + [b(x) * v(x)] = d(x)

i.e., [b(x) * {[q1(x) * u(x)] + v(x)}] + [r1(x) * u(x)] = d(x)

Since, [{q1(x) * u(x)} + v(x)] and u(x) are two polynomials.

Therefore, gcd(b(x),r1(x)) = d(x).

Hence, gcd(a(x),b(x)) = gcd(b(x),r1(x)) = d(x).

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.