# Greatest common divisor

• Apr 18th 2010, 02:53 PM
chella182
Greatest common divisor
\$\displaystyle f(X)=X^4+X^3+2X+2\$ and \$\displaystyle g(X)=X^3+X^2+X+1\$.
\$\displaystyle f(X)\$ and \$\displaystyle g(X)\$ are both polynomials over \$\displaystyle \mathbb{Z}_5\$. Compute their greatest common divisor.

My notes aren't helping me here; never done an example like this before, so a detailed explanation of the method would be greatly appreciated :)
• Apr 18th 2010, 03:04 PM
Debsta
Quote:

Originally Posted by chella182
\$\displaystyle f(X)=X^4+X^3+2X+2\$ and \$\displaystyle g(X)=X^3+X^2+X+1\$.
\$\displaystyle f(X)\$ and \$\displaystyle g(X)\$ are both polynomials over \$\displaystyle \mathbb{Z}_5\$. Compute their greatest common divisor.

My notes aren't helping me here; never done an example like this before, so a detailed explanation of the method would be greatly appreciated :)

I'd start by factorising the two functions. To do this bracket the first 2 terms and the last two terms, and proceed to factorise.
• Apr 18th 2010, 03:07 PM
chella182
Quote:

Originally Posted by Debsta
I'd start by factorising the two functions. To do this bracket the first 2 terms and the last two terms, and proceed to factorise.

I've never heard of that method of factorising... care to explain it? :)
• Apr 18th 2010, 03:10 PM
Debsta
Quote:

Originally Posted by chella182
I've never heard of that method of factorising... care to explain it? :)

Doesn't always work but is a method to try when you have 4 terms (it does help in both your cases)
eg
\$\displaystyle x^4+x^3+2x+2
= (x^4+x^3) + (2x+2)
= x^3(x+1) + 2(x+1)
= (x+1) (x^3+2)
\$
• Apr 18th 2010, 03:16 PM
chella182
Quote:

Originally Posted by Debsta
Doesn't always work but is a method to try when you have 4 terms (it does help in both your cases)
eg
\$\displaystyle x^4+x^3+2x+2
= (x^4+x^3) + (2x+2)
= x^3(x+1) + 2(x+1)
= (x+1) (x^3+2)
\$

Wow, thanks! Not sure if my lecturer will appreciate the method if it doesn't always work (he's like that), but it's worth a shot anyway!