# How to prove that $x^4+x^3+x^2+3x+3$ is irreducible over ring $\mathbb{Z}$ of integers?

Which criterion (test) one can use in order to prove that $x^4+x^3+x^2+3x+3$ is irreducible over ring $\mathbb{Z}$ of integers ?

Neither of Eisenstein's criterion and Cohn's criterion cannot be applied on this polynomial. I know that one can use factor command in Wolfram Alpha and show that polinomial is irreducible but that isn't point of this question.

-
Is semi brute force OK? If so, there is an easy argument. It actually doesn't care very much about the coefficient of $x$, as long as integer root is avoided. – André Nicolas Nov 10 '11 at 5:35
@AndreNicolas,Actually I would like to know if there is some good computational-algebra algorithm – pedja Nov 10 '11 at 5:52
@There are good canned procedures for computing Galois groups. Overkill, probably. – André Nicolas Nov 10 '11 at 6:53

Let your polynomial be $f$. Clearly it has no linear factor, since it has no root in $\mathbb{Z}$. Hence if it factors, it factors as the product of two irreducible quadratics $f_1, f_2$.
Now looking mod $2$ we get a factorization $f=x^4+x^3+x^2+x+1=f_1f_2$ in $\mathbb{F}_2[x]$. Now since $f$ has no root mod $2$, $f_1$ and $f_2$ are also irreducible quadratics in $\mathbb{F}_2[x]$. But the only irreducible quadratic in $\mathbb{F}_2[x]$ is $x^2+x+1$. This would imply $x^4+x^3+x^2+x+1 = (x^2+x+1)^2$ in $\mathbb{F}_2[x]$, which is false.
+1 Another way of seeing that $x^4+x^3+x^2+x+1$ is irreducible in $F_2[x]$ is to observe that it is a factor of $(x^5-1)=(x-1)(x^4+x^3+x^2+x+1)$. Thus any zero would a root of unity of order five. But $q=16$ is the lowest power of two with the property that $5\mid q-1$, so those roots of unity live in $GF(16)$. Thus their primitive polynomial has to be quartic. Your solution may be simpler. – Jyrki Lahtonen Nov 10 '11 at 6:54