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

• Please see math.meta.stackexchange.com/questions/5020 in particular it's not clear to me whether your x and your X are means to be the same or different variables. – Lord Shark the Unknown May 24 at 3:19
• You have to put \$ signs around the MathJax for the formatting to take effect. – saulspatz May 24 at 3:19
• @LordSharktheUnknown The same variable, auto caps on phone, sorry – 123123 May 24 at 3:21
• You shouldn't get fractions, any more than you get fractions when using the Euclidean algorithm to compute the gcd of two integers. – saulspatz May 24 at 3:22
• @WillJagy Ah, I understand now. I thought the OP meant rational functions. – saulspatz May 24 at 3:40

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?
$$\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)$$