Results 1 to 6 of 6

Math Help - GCD of Polynomials

  1. #1
    Junior Member
    Joined
    Oct 2008
    Posts
    65

    GCD of Polynomials

    say we have two polynomials, (x^5 + 1) and (x^2 + 1). We can find the GCD using Euclid's algorithm. Here is my work...

    x^5 + 1 = (x^3 - x) (x^2 + 1) + (x + 1)
    x^2 + 1 = (x - 1) (x + 1) + 2
    x + 1 = (0.5x + 0.5) (2) + 0

    Does this mean that the GCD is 2?!? That would mean that 2 divides x^5 + 1 and x^2 + 1 for all values of x, which is not true. Can anyone clear this up?
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Oct 2008
    Posts
    65

    Re: GCD of Polynomials

    I'm sorry, i read the problem wrong. It's asking for the gcd in Z/3Z. I'm not sure how to do this, can anyone help?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member TheChaz's Avatar
    Joined
    Nov 2010
    From
    Northwest Arkansas
    Posts
    600
    Thanks
    2

    Re: GCD of Polynomials

    Quote Originally Posted by hashshashin715 View Post
    ...That would mean that 2 divides x^5 + 1 and x^2 + 1 for all values of x, which is not true. Can anyone clear this up?
    THAT is where we need to know from where we take our "x"! In the reals, 2 divides everything (every nonzero element of the reals is a unit/is invertible), so 2 divides every polynomial, trivially, in that 2*(.5P(x)) = P(x).
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: GCD of Polynomials

    In Z/Z3, since it's a field, 2 also divides any polynomial. In particular, x + 1 = (2x + 2)(2) + 0. But in order to be unique, the GCD of two polynomials is usually defined so that its leading coefficient equals one. So, here the GCD is 1.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Oct 2008
    Posts
    65

    Re: GCD of Polynomials

    OK, but what does it mean for the GCD to be in Z/3Z as oppose to being in anything else?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,561
    Thanks
    785

    Re: GCD of Polynomials

    It means that the coefficients of all polynomials are considered in Z/3Z, so when you add or multiply polynomials, coefficient arithmetic is done in that field.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 7
    Last Post: April 7th 2011, 01:38 PM
  2. polynomials
    Posted in the Advanced Algebra Forum
    Replies: 0
    Last Post: February 3rd 2010, 09:13 AM
  3. Replies: 7
    Last Post: January 8th 2010, 04:13 AM
  4. polynomials
    Posted in the Algebra Forum
    Replies: 6
    Last Post: September 9th 2008, 07:40 PM
  5. Replies: 5
    Last Post: November 29th 2005, 04:22 PM

Search Tags


/mathhelpforum @mathhelpforum