Divisibility of polynomials in $\mathbb{Z}_n[x]$

For what values of $n$ is $x^2+1$ a factor of $x^5+5x+6$ in $\mathbb{Z}_n[x]$?

I know how to divide in $\mathbb{Z}[x]$ (with long division), but what should I do here with $\mathbb{Z}_n[x]$, and it's impossible to go through all values of $n$?

• You must have something of the form $$(x^2+1)(x^3+ax+b)=x^5+(a+1)x^3+bx^2+ax+b$$ so we see that $b=6$, $a=5$, $b=0$ and $a+1=0$... In which $\mathbb Z_n$'s does this happen? – String Jan 15 '14 at 22:05

We have $$x^5+5x+6=(x^3-x)(x^2+1)+6x+6.$$ Therefore $x^2+1$ be a factor only if $6x+6 = 0 \mod n$. It is possible for $n=2,3,6.$
$$x^5+5x+6= (x^3-x)(x^2+1)+6x+6.$$ You want to find a $\mathbb Z_n$, such that $$6x+6 \equiv 0 \,\,\,\text{in}\,\,\,\mathbb Z_n[x].$$ So $n=2,3$ or $6$.
${\rm mod}\ x^2\!+1\!:\,\ x^2\equiv -1\,\Rightarrow\, \color{#c00}{x^4\equiv 1}\,\Rightarrow\, \left\{\!\begin{eqnarray} f = x\color{#c00}{x^4}\!+5x+6\\ \equiv\, \color{#0a0}{6x+6}\end{eqnarray}\right\}\,\$ so $\,\ x^2\!+1\mid f\! \iff\! x^2\!+1\mid \color{#0a0}{6(x+1)}$