Results 1 to 2 of 2

Math Help - GCD in F5

  1. #1
    Member Maccaman's Avatar
    Joined
    Sep 2008
    Posts
    85

    GCD in F5

    Calculate gcd (2x^{5} + 2x^{4} + x^{3} + 3x^{2} + 1, -x^3 - x^2 + 2x + 2) in \mathbb{F}_5x
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    May 2008
    Posts
    2,295
    Thanks
    7
    Quote Originally Posted by Maccaman View Post
    Calculate gcd (2x^{5} + 2x^{4} + x^{3} + 3x^{2} + 1, -x^3 - x^2 + 2x + 2) in \mathbb{F}_5x
    do you know how Euclidean algorithm works? it's a general way to find the gcd of 2 polynomials. in your example you just need to remember that you're doing everything modulo 5.

    so let f(x)=2x^{5} + 2x^{4} + x^{3} + 3x^{2} + 1 and g(x)=-x^3 - x^2 + 2x + 2. use long division to get: f(x)=(-2x^2)g(x) + 2x^2 + 1. here you can replace -2x^2 by 3x^2, if you like,

    because 2 and -3 are equal modulo 5. next we use long division to divide g(x) by 2x^2+1: \ g(x)=(2x+2)(2x^2 + 1). the remainder here is 0. so we're done and the gcd is 2x^2+1.
    Follow Math Help Forum on Facebook and Google+

Search Tags


/mathhelpforum @mathhelpforum