Find the GCD using the Euclidean Algorithm of
So I divided the polynomials and kept getting ridiculously complex fractions. Is this GCD 1?
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
What is the inverse of 3 in Z7? It's 5, because (mod 7).
So your r1 = . No fractions included.
So continue from there.