# GCD of polynomials in Z3[x]

• Aug 31st 2007, 08:09 AM
Zoird
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
• Aug 31st 2007, 01:22 PM
ThePerfectHacker
Quote:

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.
• Sep 1st 2007, 12:03 AM
Zoird
Gcd
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 :confused:

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.