<s>[INST] Long Division of polynomials How can we prove that $x^n$  isn't divisible by $g(x)=x^4+x+1$ without remainders?
I understand why for all $n<4$ it's working, but how with $n \ge  4$? How we can prove it formally?
Note: $x^n,\:g\left(x\right)\in \mathbb{Z}_2\left[x\right]$
 [/INST] Write $x^n = q_n(x) (x^4+x+1) + r_n(x)$.
Then $$x^{n+4} = x^4 q_n(x) (x^4+x+1) + x ^4 r_n(x) = x^4 q_n(x) (x^4+x+1) + (x+1) r_n(x)$$ and so $r_{n+4} \equiv (x+1) r_n \bmod (x^4+x+1)$.
The result follows by induction because $r_n = x^n \ne 0 $ for $n=0,1,2,3$ and $x+1$ is a unit mod $(x^4+x+1)$.
</s>