Results 1 to 2 of 2

Thread: 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
    11,152
    Thanks
    731
    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 = $\displaystyle 4x^4+2x^3+6x^2+4x+5$ and b = $\displaystyle 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 $\displaystyle 3x^3 n = 4x^4$.

    What you seem to be saying is that the solution for n is $\displaystyle \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 $\displaystyle 3x^3 n \equiv 4x^4$ (mod 7)for n? We are first cancelling x's. So we get
    $\displaystyle 3n \equiv 4x$ (mod 7)

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

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

    $\displaystyle n \equiv 6x$ (mod 7)

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

    So your r1 = $\displaystyle 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: Jan 19th 2010, 11:13 AM
  2. Euclidean Algorithm
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Apr 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: Aug 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