# Greatest Common Divisor of polynomial

• Oct 22nd 2006, 01:19 PM
JaysFan31
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).
• Oct 22nd 2006, 03:40 PM
topsquark
Quote:

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
$x^4+x+1 = (x^2 - x)(x^2 + x + 1) + 1$
So r1 = 1.

Then
$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
• Oct 22nd 2006, 04:05 PM
topsquark
Quote:

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

Then
$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 $x^4 + x + 1$ is irreducible in Z2[x].

-Dan