Results 1 to 3 of 3

Math Help - Greatest Common Divisor of polynomial

  1. #1
    Junior Member
    Joined
    Jul 2006
    Posts
    43

    Greatest Common Divisor of polynomial

    I'm having enormous trouble with this. Any help appreciated.
    GCD of:
    (x^4)+x+1 and (x^2)+x+1 in Z2(x).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,933
    Thanks
    336
    Awards
    1
    Quote Originally Posted by JaysFan31 View Post
    I'm having enormous trouble with this. Any help appreciated.
    GCD of:
    (x^4)+x+1 and (x^2)+x+1 in Z2(x).
    It looks fairly simple to me. Using the Euclidean Algorithm I get that
    x^4+x+1 = (x^2 - x)(x^2 + x + 1) + 1
    So r1 = 1.

    Then
    x^2+x+1 = (x^2+x+1)(1) + 0
    So r2 = 0.

    This means that the GCD is r1 = 1. (ie. They are relatively prime.)

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,933
    Thanks
    336
    Awards
    1
    Quote Originally Posted by topsquark View Post
    It looks fairly simple to me. Using the Euclidean Algorithm I get that
    x^4+x+1 = (x^2 - x)(x^2 + x + 1) + 1
    So r1 = 1.

    Then
    x^2+x+1 = (x^2+x+1)(1) + 0
    So r2 = 0.

    This means that the GCD is r1 = 1. (ie. They are relatively prime.)

    -Dan
    Another way to check this is to note that x^4 + x + 1 is irreducible in Z2[x].

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Greatest Common Divisor of (9m+8, 6m+5)
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 15th 2011, 05:43 AM
  2. [SOLVED] Least common multiple - Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 6
    Last Post: October 25th 2010, 05:45 AM
  3. Greatest Common Divisor.
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 23rd 2009, 12:36 AM
  4. Greatest common divisor
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: December 4th 2008, 01:08 AM
  5. greatest common divisor
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: March 25th 2008, 09:36 AM

Search Tags


/mathhelpforum @mathhelpforum