# Thread: Gcd, Euclidean Algorithm, Polynomials

1. ## 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.

2. Originally Posted by JaysFan31
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