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?