How to factorize the polynomial in the ring $\mathbb{Z}_5[x]$

Question

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?

Answer 1

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$.

Answer 2

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$.

Answer 3

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.

Answer 4

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.

Answer 5

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