Dtjytyk

I can prove that $mathbb F_3[x]$ is a UFD, so $f(x)=x^{12}+x^{11}+cdots+x+1$ can be factored. And because neither 0, 1, nor 2 is a root of $f(x)$, all factors are more than 1 degrees.

But I don’t know how to factor $f(x)=x^{12}+x^{11}+cdots+x+1$, or as another simple example, $g(x)=x^4+x^3+x+2$.

How do I find out factorizations of $f(x)$ and $g(x)$ in $mathbb F_3[x]$?

Suppose $x$ is a root of $f$ in some extension field of $mathbb{F}_3$; then $x$ is a 13th root of 1. Now $mathbb{F}_{27}$ is the splitting field of $x^{27} - x$, and we see $x^{13} - 1$ divides $x^{27} - x$; therefore, each root of $f$ lies in $mathbb{F}_{27}$. It follows that each irreducible factor of $f$ has degree 3.

Furthermore, for such a root $x$, we have $N_{mathbb{F}_3}^{mathbb{F}_{27}}(x) = x cdot x^3 cdot x^9 = 1$ since the Galois group consists of the identity, the Frobenius morphism $x mapsto x^3$, and the square of the Frobenius morphism. Therefore, the irreducible factors would be of the form $x^3 + ax^2 + bx - 1$.

Conversely, for any element $y in mathbb{F}_{27} setminus mathbb{F}_3$ such that $N_{mathbb{F}_3}^{mathbb{F}_{27}}(y) = 1$, this implies $y^{13} = 1$; and since $y ne 1$, this implies $f(y) = 0$. Therefore, every irreducible polynomial of the form $x^3 + ax^2 + bx - 1$ is in fact a factor of $f(x)$.

Now, to follow a comment by Servaes: since $x^3 + ax^2 + bx - 1$ is not allowed to have either $x=1$ or $x=-1$ as a root, that means that $a+b ne 0$ and $a-b ne 2$. That restriction leaves us with only four possibilities: $(a,b) in { (0, -1), (1, 0), (1, 1), (-1, -1) }$. Each of these is in fact irreducible since it is a cubic polynomial of degree 3 with no root in $mathbb{F}_3$; and the product of these factors accounts for the full degree 12 of $f$.

In summary, we get
$$f(x) = (x^3 - x - 1) (x^3 + x^2 - 1) (x^3 + x^2 + x - 1) (x^3 - x^2 - x - 1).$$

Let $K$ be a splitting field of $f$, and note that $f$ has no roots in $Bbb{F}_3$ so in particular $KneqBbb{F}_3$. Because
$$(x-1)f(x)=x^{13}-1
qquadtext{ and }qquad
(x^{13}-1)(x^{13}-1)x=x^{27}-x,$$
where the latter splits over $Bbb{F}_{27}$, we see that $K$ is isomorphic to a subfield of $Bbb{F}_{27}$, and hence isomorphic to $Bbb{F}_{27}$ itself. This means the minimal polynomial of every root of $f$ has degree $3$, that is to say $f$ is a product of four irreducible cubic polynomials. Moreover, we see that $f$ is squarefree, so it is a product of four distinct monic irreducible cubic polynomials. There are only six such polynomials in $Bbb{F}_3$, so pick one and see whether it divides $f$.

For $g$ a similar but simpler approach works; it has no roots in $Bbb{F}_3$ so it is either irreducible or a product of two irreducible quadratics. There are only three irreducible quadratics in $Bbb{F}_3[x]$, so this is even easier to check. On the other hand, a brute force check shows that if
begin{eqnarray*}
x^4+x^3+x+2&=&(x^2+ax+b)(x^2+cx+d)\
&=&x^4+(a+c)x^3+(ac+b+d)x^2+(ad+bc)x+bd,
end{eqnarray*}
then $b=-d$ by comparing constant coefficients. Then the coefficient of $x^2$ shows that $ac=0$, so without loss of generality $a=0$, and then $c=1$ and $b=1$ and $d=2$ so
$$g(x)=(x^2+1)(x^2+x+2).$$

$$x^4+x^3+x+2=x^4+x(x^2+1)-1=(x^2+1)(x^2+x-1).$$
$$x^{12}+x^{11}+x^{10}+x^9+x^8+x^7+x^6+x^5+x^4+x^3+x^2+x+1=$$
$$=x^{12}+x^{11}-2x^{10}-8x^9-5x^8+7x^7+16x^6+7x^5-5x^4-8x^3-2x^2+x+1=$$
$$=(x^3-x-1)(x^3+x^2-1)(x^3+x^2+x-1)(x^3-x^2-x-1).$$