Is $x^6 + 1$ divisible by $x^2 + 1$? I used polynomial long division and found that the remainder was $x + 1$.  So I concluded that $x^6 + 1$ is not divisble by $x^2 + 1$.  But this is not true since $x^6 + 1$ can be factored as a sum of cubes of $x^2$ and $1$.
What can we conclude if we use long division on two polynomials and get a non-zero remainder? 

In general,
$$ a^3 +b^3 = (a+b)(a^2 - ab +b^2).$$
Let $a = x^2$ and $b=1$.
