Gcd, Euclidean Algorithm, Polynomials

Quote:

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 = $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