<s>[INST] Why is it enough to imply that $x^3+x+1|x^6+x^5+x^4+x^3+x^2+x+1$? I tried to understand a solution but I am stuck at how did the solution concluded that $x^3+x+1\mid x^6+x^5+x^4+x^3+x^2+x+1.$
Consider the field of element $8$ given by $\mathbb{F}=\frac{\mathbb{Z}_2[X]}{\langle X^3+X+1\rangle}.$ Now I can tell that each element $x$ in $\mathbb{F}$ satisfies the relation $x^8-x=0.$ Also I can see that $X^8-X=X(X-1)(X^6+X^5+X^4+X^3+X^2+X+1).$ The solution then says this implies that $X^3+X+1\mid X^6+X^5+X^4+X^3+X^2+X+1.$ However I do not understand how did they reach such conclusion?
I can see that $X^8-X$ can be factored into $\Pi _{i=1}^8X-q_i$ for every $q_i\in\mathbb{F}$ but I do not see how that would help to solve my problem.
 [/INST] Well, the general result is that the elements of $\Bbb F_q$, $q=p^n$ with $p$ prime, satisfy $x^q-x=0$. Moreover, $x^q-x$ is the product of all irreducible polynomials of degree $d\geq 1$ over $\Bbb F_p$ with $d\mid n$.
In your case, $q=2^3$ and $x^8-x = x(x-1)(x^3+x+1)(x^3+x^2+1)$ over $\Bbb F_2$.
</s>