How to factorize $n^5+n+1$? How to factorize $n^5+n+1$ ?
I think I should break $a^5$ and use a factorization formula. but how is it done?
 A: 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}$$
A: 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.$$

A: 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.
A: For completeness sake, the brute force approach:
Suppose there is a linear factor. Then
$$n^5+n+1=(n+a)(n^4+bn^3+cn^2+dn+e),$$
for some integers $a$, $b$, $c$, $d$ and $e$. In particular $ae=1$ so $a=\pm1$. Then plugging in $n=-a=\mp1$ yields
$$(-a)^5+(-a)+1=((-a)+a)((-a)^4+b(-a)^3+c(-a)^2+d(-a)+e)=0.$$
But this does not hold for $a=1$ or $a=-1$, a contradiction. So there is no linear factor.
Suppose there is a quadratic factor. Then
$$n^5+n+1=(n^2+an+b)(n^3+cn^2+dn+e).$$
As before $be=1$ so $b=e=\pm1$. Further comparing coefficients shows that
\begin{eqnarray*}
a+c&=&0,\\
b+ac+d&=&0,\\
bc+ad+e&=&0,\\
bd+ae&=&1.
\end{eqnarray*}
As $b=e=\pm1$ the latter shows that $d+a=\pm1$, and the second to last equation shows that
$$ad=\mp(c+1).$$
Then from $a+c=0$ it follows that $ad=\mp(-a+1)=\pm(1-a)$, which shows that $a$ divides $1-a$. This means that $a=1$ or $a=-1$, and $d=0$ or $d=2$ correspondingly (recall that $a+d=\pm1$). Either way we find that $a+d=1$ and hence $b=e=1$. Then the second equation above becomes
$$1-a^2+d=0,$$
because $a+c=0$, and we see that only $a=1$ and $d=0$ is a valid solution. This yields
$$n^5+n+1=(n^2+n+1)(n^3-n^2+1).$$
