How to factorize the polynomial in the ring $\mathbb{Z}_5[x]$ I need to factor the polynomial $x^5+3x^4+x^3+x^2+3$ into the product of the irreducible ones in the ring $\mathbb{Z}_5[x]$.
The problem is I don't see any whole roots (I tried every possible divisor of 3) in the given polynomial. Does it mean that it is already irreducible?
 A: Actually, $2$, $3$, and $4$ are roots of that polynomial in $\mathbb Z_5[x]$. So, your polynomial can be written as$$(x^2+ax+b)(x-2)(x-3)(x-4).$$Since $b\times(-4)=3$, $b=3$. It is not hard now to see that $a=2$.
A: It is easy to check that $-1$ is a root, and by Horner's algorithm, you obtain 
$$x^5+3x^4+x^3+x^2+3=(x+1)(x^4+2x^3-x^2+2x-2).$$
Similarly, the quotient has  $2$ as a root and
$$ x^4+2x^3-x^2+2x-2=(x-2)(x^3-x^2+2x+1).$$
The latter quotient has  $-2$ as a root, and
$$x^3-x^2+2x+=(x+2)(x^2+2x+3),$$
so that $$x^5+3x^4+x^3+x^2+3=(x+1)(x-2)(x+2)(x^2+2x+3). $$
Now the quadratic factor is irreducible because it has no root. Indeed
$$ x^2+2x+3=(x+1)^2+2,$$
and the non-zero squares in $\mathbf Z/5\mathbf Z$ are $\pm 1$.
A: Below is a simple gcd-based method method that generalizes widely.
Since $\,x^5\!-\!x \equiv \color{#0a0}x(\color{#c00}{x\!-\!1})\cdots (x\!-\!4)\,$ we get all linear factors of $\,f\,$ via $\,\gcd(f,x^5\!-\!x)$ 
$\color{#0a0}{f(0)\not\equiv 0}\,$ so we can cancel $\color{#0a0}x$ and compute $\,\gcd(f,x^4\!-\!1).\, $ Using the Euclidean algorithm
$\!\bmod x^4\!-\!1\!:\  x^4\equiv 1\,\Rightarrow\, f \equiv x\!+\!3\!+\!x^3\!+\!x^2\!+\!3\equiv x^3\!+\!x^2\!+\!x\!+\!1\equiv (x^4\!-\!1)/(\color{#c00}{x\!-\!1}) =: g$
so the gcd $\ (f,x^4\!-\!1) = (f\bmod x^4\!-\!1,\,x^4\!-\!1) = (g,\,x^4\!-\!1) = g,\ $ by $\ g\mid x^4\!-\!1$
Therefore every element is a root of $f$ except $\,\color{#0a0}0,\color{#c00}1\,$ so $f = (x\!-\!2)(x\!-\!3)(x\!-\!4)g(x)\,$  where, necessarily, $\,g\,$ is an irreducible quadratic, whose coeff's can be computed by comparing terms.
Remark $ $ This easily generalizes, e.g. same shape as above for any prime $p\ $ (above is $\,p,a = 5,2)$ 
$\!\!\begin{align}\bmod p\!:\,\ f(x) &= x^p\! \!-a x^{p-1}\!+\!x^{p-2}\!+\!x^{p-3}\!+\cdots+\! x^2 + a\!+\!1\\[.2em]  
&= (x\!-\!2)(x\!-\!3)\cdots(x\!-\!p\!+\!1)g(x),\ \ \rm by\end{align}$
$\!\bmod x^{p-1}\!-\!1\!:\,\ f \equiv x^{p-2}+\cdots +x + 1 = (x^{p-1}\!-\!1)/(x\!-1\!)\ $ as above
A: Hint: If it factors nontrivially, one factor will have degree 1 (then it has a root in ${\Bbb Z}_5$) or one factor will have degree 2, by the degree formula. The irreducible polynomials of degree 2 in ${\Bbb Z}_5[x]$ can be enumerated.
A: You need to make it more aggressively.
Check that $2$, $3$ and $4$ are roots, which gives the factorization: 
$$x^5+3x^4+x^3+x^2+3\equiv x^5-2x^4+x^3+x^2-12=$$
$$=x^5-2x^4+x^3-2x^2+3x^2-6x+6x-12=(x-2)(x^4+x^2+3x+6)\equiv$$
$$\equiv(x-2)(x^4-9x^2-2x+6)=(x-2)(x^2(x-3)(x+3)-2(x-3))=$$
$$=(x-2)(x-3)(x^3+3x^2-2)\equiv(x-2)(x-3)(x^3-2x^2-32)=$$
$$=(x-2)(x-3)(x^3-4x^2+2x^2-32)=(x-2)(x-3)(x-4)(x^2+2x+8)=$$
$$=(x-2)(x-3)(x-4)((x+1)^2-3).$$
Easy to see that the quadratic factor is irreducible. 
