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, 03: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, 06: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 = and b = .

Set this up to do longhand. The first thing you need to do is find a number n such that .

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

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

(mod 7)

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

So

(mod 7)

(mod 7)

So

(mod 7)

So your r1 = . No fractions included.

So continue from there.

-Dan