Just some culture, in case of curiosity. If you take any prime $q$ that has an integral expression as $ q = 2 x^2 + x y + 4 y^2, $ such as $2, \; 5, \; 7\; 19,$ then $ z^3 + z + 1 \equiv 0 \pmod q $ has no roots in integral $z.$
For the special case of $31,$ we have $ z^3 + z + 1 \equiv (z -3)(z - 14)^2 \pmod {31}. $ For any other prime $ p = x^2 + x y + 8 y^2, $ such as $47, \; 67, \; 131, \; 149,$ then $ z^3 + z + 1 \equiv 0 \pmod p $ has three distinct roots in integral $z$ and factors as three distinct linear factors.
For any prime $r$ with $(-31|r) = -1,$ such as $3, \; 11, \; 13, \; 17,$ then $ z^3 + z + 1 \equiv 0 \pmod r $ has a single non-repeated root, so the cubic factors as a linear times a quadratic.
Well, why not. It turns out that every integer $n,$ positive or negative or $0,$ has an expression in integers as $ n = x^2 + x y + 8 y^2 + z^3 + z,$ where we deliberately strip off the 1. The difficult question is, what integers $n$ have an expression in integers as $ n = 2 x^2 + x y + 4 y^2 + z^3 + z \; ?$ Certainly not all, $n = \pm 1$ do not work. The first few, in absolute value, that do not work are $ \pm 1, \; \pm 869, \; \pm 25171, \; \pm 21118439, \; \pm 611705641, $ these being the odd integers $u$ with $ 27 u^2 - 31 v^2 = -4. $ The first few even values of $u$ are $ 30 = 3^3 + 3, $ $ 729090 = 90^3 + 90, $ $ 17718345150 = 2607^3 + 2607, $ so these are easily expressed as $2 x^2 + x y + 4 y^2 + z^3 + z $ with both $x,y = 0.$
Well, somebody did mention the discriminant of a cubic, we have $ \mbox{disc}_z \left( z^3 + z + 1 \right) = -31 $ and $ \mbox{disc}_z \left( z^3 + z + u \right) = -4 - 27 u^2 = -31 v^2.$ So there.