<s>[INST] 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 
 [/INST] $$  \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)  $$ 
.....
</s>