How find gcd polynomials?

Question

How to find gcd of polynomials $gcd(x^3+x^2-x-1,3x^2+2x-1)$ ??

I divide of polynomials. It worked like this $\frac 13 x - \frac19$,$ R\left( x\right) =-\frac89x -\frac89$

Answer 1

You want the gcd of $f(x) = x^3+x^2-x-1$ and its derivative. Now $$f(x) = x^2 (x+1) - (x+1) = (x^2-1)(x+1) = (x-1)(x+1)^2$$ so $$\gcd(f(x), f'(x)) = x+1$$

Answer 2

HINT:

If $f(x)$ divides both,

$f(x)$ must divide $$3(x^3+x^2-x-1)-x(3x^2+2x-1)=x^2-2x-3=(x-3)(x+1)$$

Now $3x^2+2x-1=(3x-1)(x+1)$

OR

---

$x^3+x^2-x-1=(x+1)(x^2-1)=(x+1)^2(x-1)$

and $3x^2+2x-1=(3x-1)(x+1)$

Answer 3

You have gotten to a good start. What you are doing here is following the Euclidean algorithm, which at its core says:

For any $a, b, n$, we have $\gcd(a, b) = \gcd(a, b-na)$. If $b - na = 0$, then $a$ is the $\gcd$. If not, repeat this step as much as needed, with the new values for $a$ and $b$.

Note: when I say "any $a, b, n$", I mean "any $a, b, n$ in the current setting". Usually, when talking about the Euclidean algorithm, the setting is the integers, but in this case, what you have are polynomials, and therefore that is our setting (the formal word for "setting" in this context is ring).

Anyhow, we may use the algorithm to find what we're after: $$ \begin{align} &\gcd(3x^2+2x-1,x^3+x^2-x-1)\\ = &\gcd(3x^2+2x-1,x^3+x^2-x-1 - \left(\frac x3 -\frac19\right)(3x^2 + 2x - 1))\\ = &\gcd\left(3x^2 + 2x - 1, -\frac 89 x - \frac 89\right) \end{align} $$ using $a = 3x^2 + 2x - 1, b = x^3+x^2-x-1$ and $n = \frac x3 -\frac19$. Now you've decreased the degree of the problem by $1$ (you've changed from a second degree and a third degree to a first degree and second degree polynomial). You now do exactly the same thing again, until you are able to make $b-na$ to be $0$. Then $a$ will be your answer.

PS. Since you're allowed fractions, the actual coefficients of the polynomials matter little. It is the ratio between them that matters. Therefore, you are allowed to reduce $-\frac89 x - \frac89$ to $x + 1$ before continuing. This corresponds to $\gcd(a, b) = \gcd(a, -b)$ when talking about integers. The key point is that since $\frac 89$ is invertible in our setting (there is a number $\frac 98$ such that $\frac 89 \cdot \frac 98 = 1$), we get that $\gcd(a, b) = \gcd(a, \frac98 b)$. On the other hand, $x$ is not invertible ($\frac1x$ is not an admissable polynomial), and therefore you are not allowed to freely multiply or divide $a$ and $b$ by $x$.

Had you not been allowed to use fractions, but only integer coefficients, then the Euclidean algorithm wouldn't always lead to an answer (e.g. $\gcd(2, x)$), and the very concept of a greatest common divisor stops making sense.