I'm sorry, i read the problem wrong. It's asking for the gcd in Z/3Z. I'm not sure how to do this, can anyone help?
say we have two polynomials, (x^5 + 1) and (x^2 + 1). We can find the GCD using Euclid's algorithm. Here is my work...
x^5 + 1 = (x^3 - x) (x^2 + 1) + (x + 1)
x^2 + 1 = (x - 1) (x + 1) + 2
x + 1 = (0.5x + 0.5) (2) + 0
Does this mean that the GCD is 2?!? That would mean that 2 divides x^5 + 1 and x^2 + 1 for all values of x, which is not true. Can anyone clear this up?
In Z/Z3, since it's a field, 2 also divides any polynomial. In particular, x + 1 = (2x + 2)(2) + 0. But in order to be unique, the GCD of two polynomials is usually defined so that its leading coefficient equals one. So, here the GCD is 1.