Thread: GCD of polynomials in Z3[x]

There seems to be an error in the following calculation, I'm not quite sure what it is though. Could someone point it out?
Thanks.

Find the GCD of p(x) = 2x^5 + x^3 + 2^x + 1 and q(x) = x^4 + x^3 + x + 1 in z3[x]
Use the Euclidean algorithm:
2x^5 + x^3 + 2x + 1 = (2x + 1)(x^4 + x^3 + x + 1) + x^2 + 2x
x^4 + x^3 + x + 1 = (x^2 + 2x + 2)(x^2 + 2x) + 1
x^2 + 2x = (1)(x^2 + 2x) + 0
So the answer is 1

Originally Posted by Zoird

There seems to be an error in the following calculation, I'm not quite sure what it is though. Could someone point it out?
Thanks.

Find the GCD of p(x) = 2x^5 + x^3 + 2^x + 1 and q(x) = x^4 + x^3 + x + 1 in z3[x]
Use the Euclidean algorithm:
2x^5 + x^3 + 2x + 1 = (2x + 1)(x^4 + x^3 + x + 1) + x^2 + 2x
x^4 + x^3 + x + 1 = (x^2 + 2x + 2)(x^2 + 2x) + 1
x^2 + 2x = (1)(x^2 + 2x) + 0
So the answer is 1

What is the problem? It seems you did everything correctly.

I was told there was something wrong with the calculation, but didn't really get a proper explanation of why. I'm quite sure that the first two lines are right, and the answer should be too. So that really only leaves the third row

x^2 + 2x = (1)(x^2 + 2x) + 0

But it's really simple, so how could it be wrong.. It drives me mad

Oh, and I noticed I wrote 2^x instead of 2x in the initial description, it should be 2x as in the calculation. Sorry about that.