1. ## GCD of Polynomials

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?

2. ## Re: GCD of Polynomials

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?

3. ## Re: GCD of Polynomials

Originally Posted by hashshashin715
...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?
THAT is where we need to know from where we take our "x"! In the reals, 2 divides everything (every nonzero element of the reals is a unit/is invertible), so 2 divides every polynomial, trivially, in that 2*(.5P(x)) = P(x).

4. ## Re: GCD of Polynomials

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.

5. ## Re: GCD of Polynomials

OK, but what does it mean for the GCD to be in Z/3Z as oppose to being in anything else?

6. ## Re: GCD of Polynomials

It means that the coefficients of all polynomials are considered in Z/3Z, so when you add or multiply polynomials, coefficient arithmetic is done in that field.