How to compute gcd of two polynomials efficiently

Question

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

Answer 1

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?

Answer 2

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

.....

Answer 3

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.