How to compute gcd of two polynomials efficiently I have two polynomials $A=x^4+x^2+1$
And $B=x^4-x^2-2x-1$
I need to compute the gcd of $A$ and $B$ but when I do the regular Euclidean way I get fractions and it gets confusing, are you somehow able to use a SylvesterMatrix to find the gcd or am I probably doing something wrong?
I don’t know how to format properly yet so apologies 
 A: I think most efficiently it's the following.
$$x^4-x^2-2x-1=x^4-(x+1)^2=(x^2-x-1)(x^2+x+1).$$
$$x^4+x^2+1=(x^2+1)^2-x^2=(x^2-x+1)(x^2+x+1).$$
Can you end it now?
A: $$  \left(   x^{4}  +  x^{2}  + 1 \right)  $$ 
$$  \left(   x^{4}  -  x^{2}  - 2 x  - 1 \right)  $$ 
$$  \left(   x^{4}  +  x^{2}  + 1 \right)  =  \left(   x^{4}  -  x^{2}  - 2 x  - 1 \right)  \cdot \color{magenta}{  \left( 1  \right) } +  \left(  2 x^{2}  + 2 x  + 2 \right)  $$
$$  \left(   x^{4}  -  x^{2}  - 2 x  - 1 \right)  =  \left(  2 x^{2}  + 2 x  + 2 \right)  \cdot \color{magenta}{  \left(   \frac{  x^{2}  -  x  - 1 }{ 2 }  \right) } +  \left( 0 \right)  $$
$$ \frac{ 0}{1} $$
$$ \frac{ 1}{0} $$
$$ \color{magenta}{  \left( 1  \right) }  \Longrightarrow  \Longrightarrow  \frac{  \left( 1  \right) }{ \left( 1  \right) } $$
$$ \color{magenta}{  \left(   \frac{  x^{2}  -  x  - 1 }{ 2 }  \right) }  \Longrightarrow  \Longrightarrow  \frac{  \left(   \frac{  x^{2}  -  x  + 1 }{ 2 }  \right) }{ \left(   \frac{  x^{2}  -  x  - 1 }{ 2 }  \right) } $$
$$  \left(   x^{2}  -  x  + 1 \right)  \left( \frac{ 1}{2 } \right)  -  \left(   x^{2}  -  x  - 1 \right)  \left( \frac{ 1}{2 } \right)  =  \left( 1  \right)  $$
$$  \left(   x^{4}  +  x^{2}  + 1 \right)  =  \left(   x^{2}  -  x  + 1 \right)  \cdot \color{magenta}{  \left(   x^{2}  +  x  + 1 \right) } +  \left( 0 \right)  $$
$$  \left(   x^{4}  -  x^{2}  - 2 x  - 1 \right)  =  \left(   x^{2}  -  x  - 1 \right)  \cdot \color{magenta}{  \left(   x^{2}  +  x  + 1 \right) } +  \left( 0 \right)  $$
$$  \mbox{GCD} =   \color{magenta}{  \left(   x^{2}  +  x  + 1 \right) }   $$
$$  \left(   x^{4}  +  x^{2}  + 1 \right)  \left( \frac{ 1}{2 } \right)  -  \left(   x^{4}  -  x^{2}  - 2 x  - 1 \right)  \left( \frac{ 1}{2 } \right)  =  \left(   x^{2}  +  x  + 1 \right)  $$ 
.....
A: Why not using a simpler method?!
We define h=aA+bB (a&b are any constants) as a linear combination of A&B.
Now,the gcd of A&B=gcd of A&h=gcd of B&h.Why?
Because,taking gcd of A&B=c;
h=aA+bB=acA'+bcBb'=c(aA'+bB'),then c is a factor of h also.
Set a=1 & b=-1,so we get rid of the x^4 terms;
h=A-B=$2x^2+2x+2=2(x^2+x+1)$     (1)
Set a=1&b=1,so we get rid of the constant terms;
h=A+B=$2x^4-2x=2x(x^3-1)=2x(x-1)(x^2+x+1)$  (2)
Now,both of the linear combinations (1)&(2), 
contain $(2x^2+3x-2)$
Then,$(2x^2+3x-2)$ is the gcd.
