Results 1 to 2 of 2

Math Help - Gcd, Euclidean Algorithm, Polynomials

  1. #1
    Junior Member
    Joined
    Jul 2006
    Posts
    43

    Gcd, Euclidean Algorithm, Polynomials

    Find the GCD using the Euclidean Algorithm of
    (4x^4)+(2x^3)+(6x^2)+4x+5
    and
    (3x^3)+(5x^2)+6x
    in Z7[x].

    So I divided the polynomials and kept getting ridiculously complex fractions. Is this GCD 1?

    Thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    10,054
    Thanks
    368
    Awards
    1
    Quote Originally Posted by JaysFan31 View Post
    Find the GCD using the Euclidean Algorithm of
    (4x^4)+(2x^3)+(6x^2)+4x+5
    and
    (3x^3)+(5x^2)+6x
    in Z7[x].

    So I divided the polynomials and kept getting ridiculously complex fractions. Is this GCD 1?

    Thanks.
    If I did this right (it's been a while) I'm getting a GCD of 5, so technically yes the GCD is 1. (Someone please check this.)

    Whether I'm right or wrong, you have a significant theoretical problem listed in your post: fractions do not exist in Z7.

    For example, the first step of the Euclidean Algorthm says to find r1:
    a = q*b + r1
    where a = 4x^4+2x^3+6x^2+4x+5 and b =  3x^3+5x^2+6x.

    Set this up to do longhand. The first thing you need to do is find a number n such that 3x^3 n = 4x^4.

    What you seem to be saying is that the solution for n is \frac{4}{3}x, but this polynomial does not exist in Z7[x]. (Well, not in this form anyway!)

    What are we doing when we solve the equation 3x^3 n \equiv 4x^4 (mod 7)for n? We are first cancelling x's. So we get
    3n \equiv 4x (mod 7)

    What is the inverse of 3 in Z7? It's 5, because 3 \cdot 5 \equiv 1 (mod 7).

    So
    5 \cdot 3n \equiv 5 \cdot 4x (mod 7)

    n \equiv 6x (mod 7)

    So
    4x^4+2x^3+6x^2+4x+5 \equiv (6x)(3x^3+5x^2+6x) + (5x^2+x+5) (mod 7)

    So your r1 = 5x^2 + x + 5. No fractions included.

    So continue from there.

    -Dan
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Euclidean algorithm
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: January 19th 2010, 11:13 AM
  2. Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 29th 2009, 11:51 AM
  3. Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: May 13th 2007, 07:20 AM
  4. Euclidean algorithm gcd lcm help..
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: August 10th 2006, 05:46 AM
  5. Euclidean Algorithm
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 7th 2006, 11:25 AM

Search Tags


/mathhelpforum @mathhelpforum