Euclidean and Division AlgorithmsDate: 11/26/97 at 03:48:36 From: Terry Subject: Polynomial Can you show and explain the proofs of the Euclidean Algorithm and the Division Algorithm? Date: 11/26/97 at 11:57:47 From: Doctor Rob Subject: Re: Polynomial Since your subject is "Polynomial," I assume you are talking about these algorithms as applied to polynomials with coefficients in a field, such as the complex numbers, real numbers, or rational numbers, as opposed to being applied to integers. First the Division Algorithm. It is based on the theorem that given two polynomials F(x) and D(x) with D(x) nonzero, there exist polynomials Q(x) and R(x) such that F(x) = Q(x)*D(x) + R(x), and the degree of R is less than the degree of D. Q is called the quotient, and R the remainder, when F is divided by D. The proof of this theorem goes like this: If F(x) = 0, then set Q(x) = 0 and R(x) = 0, and we are done. If F(x) is not zero, let the leading term of F(x) be A*x^f, and the leading term of D(x) be B*x^d, with both A and B nonzero, f >= 0, and d >= 0. If f < d, we can use Q(x) = 0, R(x) = F(x), and we are done. If f >= d, then construct the polynomials T0(x) = (A/B)*x^(f-d), and F1(x) = F(x) - D(x)*T0(x). This has been designed so that the leading term of F(x) will be canceled by the leading term of D(x)*T0(x), since both are equal to A*x^f. If F1(x) = 0, then set Q(x) = T0(x) and R(x) = 0, and we are done. If F1(x) is not zero, let the leading term of F1(x) be A1*x^f1, where A1 is nonzero and f > f1 >= 0. If f1 < d, we can use Q(x) = T0(x) and R(x) = F1(x), and we are done. If f1 >= d, then construct the polynomials T1(x) = (A1/B)*x^(f1-d), and F2(x) = F1(x) - D(x)*T1(x). This has been designed so that the leading term of F1(x) will be canceled by the leading term of D(x)*T1(x), since both are equal to A1*x^f1. If F2(x) = 0, then set Q(x) = T0(x) + T1(x) and R(x) = 0, and we are done. If F2(x) is not zero, let the leading term of F2(x) be A2*x^f2, where A2 is nonzero and f > f1 > f2 >= 0. We continue this process until either one of the Fn's is zero or has degree less than d. That this must happen is guaranteed by the decreasing sequence of nonnegative integer degrees f > f1 > f2 > ... >= 0, which can have at most f + 1 terms. The process must end after n <= f + 1 steps. Then Q(x) = T0(x) + T1(x) + ... + Tn(x), and R(x) = Fn(x). An alternate proof can be constructed using mathematical induction. Example: Find the quotient and remainder of F(x) = x^4 - 3*x^2 + 2*x divided by D(x) = x^3 + x^2 - 2. Here f = 4, d = 3, A = B = 1. T0(x) = (1/1)*x^(4-3) = x. F1(x) = F(x) - D(x)*T0(x), = x^4 - 3*x^2 + 2*x - (x^3 + x^2 - 2)*x, = x^4 - 3*x^2 + 2*x - x^4 - x^3 + 2*x, = -x^3 - 3*x^2 + 4*x. Now f1 = 3 and A1 = -1, so T1(x) = (-1/1)*x^(3-3) = -1. F2(x) = F1(x) - D(x)*T1(x), = -x^3 - 3*x^2 + 4*x - (x^3 + x^2 - 2)*(-1), = -x^3 - 3*x^2 + 4*x + x^3 + x^2 - 2, = -2*x^2 + 4*x - 2. Since this has degree less than 3, we are done, and Q(x) = x - 1, and R(x) = -2*x^2 + 4*x - 2. Now for the Euclidean Algorithm. It uses the Division Algorithm. The appropriate theorem is the following. Given two polynomials F0(x) and F1(x) with F1(x) nonzero, construct a sequence of polynomials Q2, Q3, ... and F2, F3, ... in the following way. Use the division algorithm at each step. F0(x) = Q2(x)*F1(x) + F2(x), 0 <= deg(F2) < deg(F1) F1(x) = Q3(x)*F2(x) + F3(x), 0 <= deg(F3) < deg(F2) ... Fk-2(x) = Qk(x)*Fk-1(x) + Fk(x), 0 <= deg(Fk) < deg(Fk-1) Fk-1(x) = Qk+1(x)*Fk(x). Then Fk(x) is a nonzero constant multiple of the greatest common divisor of F0(x) and F1(x). Proof: Let D(x) be the greatest common divisor of F0(x) and F1(x). Use the principal of mathematical induction to show that Fk(x) divides Fi(x) for all i with 0 <= i <= k. Use it again to show that any common divisor of F0(x) and F1(x) divides Fi(x) for all i with 0 <= i <= k. Use in those induction steps the equations given above, and the fact that if D divides A and D divides B, then it divides A + B and A - B and A*C and B*C for any C. Together, the divisibility of any common divisor into Fk(x), and the fact that Fk(x) is a common divisor of F0(x) and F1(x), imply that Fk(x) divides D(x), and D(x) divides Fk(x). Thus Fk(x) = c*D(x) for some nonzero constant c. Example: Find the GCD of F0(x) = x^4 - 3*x^2 + 2*x and F1(x) = x^3 + x^2 - 2. x^4 - 3*x^2 + 2*x = (x - 1)*(x^3 + x^2 - 2) + (-2*x^2 + 4*x - 2), x^3 + x^2 - 2 = ([-1/2]*x-3/2)*(-2*x^2 + 4*x - 2) + (5*x - 5) -2*x^2 + 4*x - 2 = ([-2/5]*x+2/5)*(5*x - 5). Thus 5*x - 5 is a nonzero constant multiple of the G.C.D., which is always taken to be monic (leading coefficient 1), so the G.C.D. is x - 1. -Doctor Rob, The Math Forum Check out our web site! http://mathforum.org/dr.math/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/