How to factorize $n^5+n+1$?
Not sure if my answer can satisfy:
$$\begin{aligned} n^5+n+1&=(n^5-n^2)+(n^2+n+1)\\&=n^2(n-1)(n^2+n+1)+(n^2+n+1)\\&=(n^3-n^2+1)(n^2+n+1)\end{aligned}$$
By trial and error, knowing that there must be a simple solution.
Factoring $n^5+1$ leads nowhere. $$n^5+n+1=(n+1)(n^4-n^3+n^2-n+1)+n.$$
Factoring $n^5+n$ leads nowhere. $$n^5+n+1=n(n+1)(n^3-n^2+n-1)+1.$$
Factoring $n^5+n^2$ with an artifice fails, but shows some hope $$n^5+n^2-n^2+n+1=n^2(n+1)(n^2-n+1)-n^2+n+1.$$
- Factoring $n^5-n^2$ instead works ! $$n^5-n^2+n^2+n+1=n^2(n-1)(n^2+n+1)+n^2+n+1.$$
Your coefficients are $(1,0,0,0,1,1)$. That suggests to me that $(1,1,1,1,1,1) + (0,-1,-1,-1,0,0)$ will be useful, to form the pattern with blocks of 3 unit coefficients, i.e. that $(x^2+x+1)$ is a factor.