# Greatest common divisor

• Apr 18th 2010, 03:53 PM
chella182
Greatest common divisor
$f(X)=X^4+X^3+2X+2$ and $g(X)=X^3+X^2+X+1$.
$f(X)$ and $g(X)$ are both polynomials over $\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, 04:04 PM
Debsta
Quote:

Originally Posted by chella182
$f(X)=X^4+X^3+2X+2$ and $g(X)=X^3+X^2+X+1$.
$f(X)$ and $g(X)$ are both polynomials over $\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, 04: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, 04: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
$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, 04: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
$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!