For what natural numbers $n$ is $\mathbf Z/n\mathbf Z$ $[x]/(x^3+x+1)$ a field? I recently saw this question in the exam of a first abstract algebra course in my college. It shouldn't be too difficult, yet I can't seem to get the solution. Any ideas on how to tackle this?
 A: Below is an approach using some number theory. Hope this is fine.
As you already know, this quotient is a field if and only if the polynomial is irreducible. Since a cubic polynomial is reducible if and only if it has a root (for degree reasons), the quotient is a field if and only if this polynomial has no roots in $\mathbb Z/n\mathbb Z,$ i.e. if and only if $x^3+x+1\equiv0\pmod n$ has no solutions in integers.
Further, by the cubic formula, especially the equation (19) in the link, if $\omega$ is a root, then $\omega^3=\frac{-1}{2}\pm\frac{1}{2}\sqrt{1+\frac{4}{27}},$ so $\omega=-\omega^3-1=\frac{-1}{2}\mp\frac{1}{2}\sqrt{1+\frac{4}{27}}.$ This shows that the polynomial has a  root if and only if $y^2\equiv\frac{31}{27}\pmod n$ is solvable in integers.
First consider the case where $n$ is a prime $p\not=2, 3, 31.$
Now the congruence $y^2\equiv31\cdot27^{-1}\pmod p$ is solvable if and only if the Legendre symbol $\left(\frac{31\cdot27^{-1}}{p}\right)=1.$ So the quotient is a field if and only if the congruence is not solvable, if and only if $$\left(\frac{31\cdot3}{p}\right)=-1.$$
By quadratic reciprocity, the last condition is equivalent with $$(-1)^{(p-1)/2}\left(\frac{p}{31}\right)(-1)^{(p-1)/2}\left(\frac{p}{3}\right)=\left(\frac{p}{31}\right)\left(\frac{p}{3}\right)=-1$$
Now we have a necessary and sufficient condition under the hypothesis that $n$ is a prime $\not=2, 3 , 31.$ If $n$ is not a prime, say $n=\prod_ip_i^{n_i},$ then $\mathbb Z/n\mathbb Z[x]/(x^3+x+1)\cong \bigoplus_i\mathbb Z/p_i^{n_i}\mathbb Z[x]/(x^3+x+1)$ is not a field: e.g. the element $(1,0,\cdots,0)$ is not invertible. Finally, as 
$$(1)^3+(1)+1=3,$$
$$(3)^3+(3)+1=31,$$
it follows that none of $3, 31$ satisfies the condition, while the polynomial is irreducible modulo $2:$ there are only two elements in $\mathbb Z/2\mathbb Z,$ none of which satisfies $x^3+x+1=0.$ Thanks to Jyrki Lahtonen for pointing this out!
Hope this helps, and, if any error occurs, please inform me, thanks in advance.
A: Hint: A quotient by an ideal is a field if and only if the ideal is maximal, so you'd want to look for when the polynomial factorises.
