Factoring polynomials modulo 3

Question

Let $f(x) = x^5 + 2x^2 + 2x + 2 \in\mathbb Z_3[x]$. Then the irreducible factorization of $f(x)$ is $(x^2 +1)(x^3+2x+2)$ even though it does not have a root in $\mathbb Z_3$. How did we find that factorization? What am i missing here? I want to build an extension field over $\mathbb Z_3$.

Answer 1

It's easy to see that $f(x)$ has no root in $Z_3$, just by checking $x=0,1,2$, so if $f(x)$ did factor, it must factor as a degree 2 polynomial multiplied with a degree 3 polynomial. We can further deduce to:

$$f(x)=(x^2+ax+b)(x^3+cx^2+dx+e)$$ with each $a,b,c,d,e\in Z_3$. expanding this out gives:

$$x^5+2x^2+2x+2=x^5+(a+c)x^4+(a+b+d)x^3+(ad+bc+e)x^2+(ae+bd)x+be$$

So we now have the system:

$$a+c=0$$ $$a+b+d=0$$ $$ad+bc+e=2$$ $$ae+bd=2$$ $$be=2$$

So either $b=1$ and $e=2$ or the way around, and $c=-a$, guessing $b=2$ and $e=1$ gives:

$$a+d=1$$ $$ad-2a+1=2$$ $$a+2d=2$$

Subtracting the first from the third results in $d=1$, so that $a=0$, but this would make $1=2$ with the second equation, so really $b=1$ and $e=2$ and we actually now have:

$$a+d=2$$ $$ad+c=0$$ $$2a+d=2$$

and now subtracting the first from the third gives $a=0$, making $d=2$ and $c=0$, which completes the factorization.

Answer 2

You find this by trying to divide $f(x)$ by all possible irreducible polynomials of degree $2$ over ${\mathbb Z}_3$.

Since $f(x)$ has no root and it is of degree $5$, it is either irreducible or factors as a polynomial of degree $2$ times a polynomial of degree $3$. There are only 9 monic polynomials of degree $2$ over ${\mathbb Z}_3$ and only three of them are irreducible: $x^2 + 1$, $x^2 + x + 2$, $x^2 + 2x + 2$. Even if you don't know these or don't want to figure them out first, you can always try all $9$, discarding the ones that you immediately identify as reducible.