Greatest Common Divisor of polynomial

• Oct 22nd 2006, 12: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, 02: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
\$\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
• Oct 22nd 2006, 03:05 PM
topsquark
Quote:

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