<s>[INST] Finding $\gcd(x^3, x^3+x+1)$ Suppose $f(x) = x^3$ and $g(x) = x^3+x+1$. I am trying to show that the $\gcd(f,g)= 1$ but am running into some trouble...
My attempt: (Division algorithm)
$x^3+x+1 = (1)(x^3)+(x+1)$
$x^3 = x^2(x+1)-x^2$
But I cannot go further than this, what is going wrong here?
 [/INST] The gcd of $x^3+x+1$ and $x^3$ is the same as the gcd of $x^3$ and $(x^3+x+1)-x^3=x+1$.
Now $x+1$ is irreducible and doesn't divide $x^3$. End.
By the way, the remainder of the division of $f(x)=x^3$ by $x+1$ is $f(-1)=-1$ and, indeed, $x^3+1=(x+1)(x^2-x+1)$, but it's not needed.
</s>