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.

Printable View

- Oct 21st 2006, 02:14 PMJaysFan31Gcd, 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. - Oct 21st 2006, 05:50 PMtopsquark
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