# Thread: Greatest Common Divisor of polynomial

1. ## Greatest Common Divisor of polynomial

I'm having enormous trouble with this. Any help appreciated.
GCD of:
(x^4)+x+1 and (x^2)+x+1 in Z2(x).

2. Originally Posted by JaysFan31
I'm having enormous trouble with this. Any help appreciated.
GCD of:
(x^4)+x+1 and (x^2)+x+1 in Z2(x).
It looks fairly simple to me. Using the Euclidean Algorithm I get that
$\displaystyle x^4+x+1 = (x^2 - x)(x^2 + x + 1) + 1$
So r1 = 1.

Then
$\displaystyle x^2+x+1 = (x^2+x+1)(1) + 0$
So r2 = 0.

This means that the GCD is r1 = 1. (ie. They are relatively prime.)

-Dan

3. Originally Posted by topsquark
It looks fairly simple to me. Using the Euclidean Algorithm I get that
$\displaystyle x^4+x+1 = (x^2 - x)(x^2 + x + 1) + 1$
So r1 = 1.

Then
$\displaystyle x^2+x+1 = (x^2+x+1)(1) + 0$
So r2 = 0.

This means that the GCD is r1 = 1. (ie. They are relatively prime.)

-Dan
Another way to check this is to note that $\displaystyle x^4 + x + 1$ is irreducible in Z2[x].

-Dan